Being a programmer, I decided it would be more fun to program my computer to solve the puzzle. I spent a couple of hours on it, and came up with a nice result. I'll share the result below, along with some observations about the program and the puzzle.
First, here's a link to the puzzle: http://www.palmettopuzzleworks.net/
You can buy it directly through Etsy for $20.
Before I delve into my program, let me start by suggesting that this might make a great programming assignment. It's a very well-defined problem, but with a number of subtleties to watch out for.
So let me show you my solution. My intuition was that this would be a computationally complex problem, and it looked like a good fit regardless, so my language of choice was C.
The first thing to do is define the data structures. I've found that in the vast majority of problems, the data structures drive the code. If you have the wrong data structures, you'll never get a good solution, but with the right data structures, the code mostly flows into place.
As you can see in the picture, the board is an 11x11 grid with some spaces filled in. That makes the board an easy two-dimensional array. The largest piece fits in a 4x5 grid, so I created a three-dimensional array for the pieces initialized to a 1 for the spots that are filled and a 0 for the squares not occupied. Thinking ahead, I'm going to have to rotate each piece, so I need to use a square for each piece, not just a rectangle, so each piece is a 5x5 grid.
int grid[11][11]; int pieces[9][5][5] = { // first four pieces are "big" and take four rows { { 0,1,1,0,0 }, { 0,1,1,1,0 }, { 1,1,1,1,1 }, { 0,1,0,0,0 }, { 0,0,0,0,0 } }, { { 1,1,1,0,0 }, { 0,1,1,1,0 }, { 1,1,1,0,0 }, { 0,1,0,0,0 }, { 0,0,0,0,0 } }, { { 0,1,0,0,0 }, { 0,1,1,1,0 }, { 0,1,1,1,1 }, { 1,1,1,1,0 }, { 0,0,0,0,0 } }, { { 0,1,0,0,0 }, { 1,1,1,1,0 }, { 0,1,1,1,1 }, { 0,1,0,1,0 }, { 0,0,0,0,0 } }, // remaining five pieces take three rows { { 0,1,1,1,0 }, { 1,1,1,0,0 }, { 1,1,1,0,0 }, { 0,0,0,0,0 }, { 0,0,0,0,0 } }, { { 1,1,1,1,0 }, { 1,1,1,0,0 }, { 1,0,1,0,0 }, { 0,0,0,0,0 }, { 0,0,0,0,0 } }, { { 1,1,1,0,0 }, { 1,1,1,1,0 }, { 1,0,1,0,0 }, { 0,0,0,0,0 }, { 0,0,0,0,0 } }, { { 0,1,1,1,0 }, { 1,1,1,0,0 }, { 1,0,1,0,0 }, { 0,0,0,0,0 }, { 0,0,0,0,0 } }, { { 1,1,0,0,0 }, { 1,1,1,1,0 }, { 0,1,1,0,0 }, { 0,0,0,0,0 }, { 0,0,0,0,0 } } };
Initializing the grid is pretty simple: a zero represents an open space, a number indicates a piece (1 through 9), and another constant represents the border (10). Because the border is more filled than open, the code fills the borders, then opens up the spaces where a piece can intrude.
#define BORDER 10 void init_border(void) { // Set grid to zero memset(grid,0,sizeof(grid)); // Border defaults to blocked for(int i=0;i<11;++i) { grid[0][i] = grid[i][0] = grid[10][i] = grid[i][10] = BORDER; } // Clear spots grid[0][2] = grid[0][4] = grid[0][8] = 0; grid[10][1] = grid[10][4] = grid[10][6] = grid[10][8] = 0; grid[3][0] = grid[5][0] = grid[8][0] = 0; grid[1][10] = grid[5][10] = grid[7][10] = grid[9][10] = 0; }
Now here we come to the key trick to make the whole thing work. I have to try each piece in four different rotations. If I rotate the pieces on the fly, the program will be spending most of its time doing rotations. That's not a good idea for something that is already likely to be quite computationally intensive. So why not save the work and just do it once? This raises one subtlety to the problem: The pieces all fit in a 5x5 grid, but have at least one row or column empty. The solving code will want to assume that the top row and left column are non-empty, so each rotation has to also shift to make that happen. With that explained, there's nothing particularly fancy about the code, though I'll admit that on the first run, it mangled the pieces by doing some reflections as well as rotations.
int all_pieces[9][4][5][5]; void init_rotations(void) { for (int piece=0; piece<9; ++piece) { for (int rotation=0; rotation<4; ++rotation ) { if ( rotation == 0 ) { for ( int r=0;r<5;++r ) { for ( int c=0;c<5;++c ) { all_pieces[piece][rotation][r][c] = pieces[piece][r][c]; } } } else { for ( int r=0;r<5;++r ) { for ( int c=0;c<5;++c ) { all_pieces[piece][rotation][4-c][r] = all_pieces[piece][rotation-1][r][c]; } } } } } // Now shift rotations to all be in the upper-left (no all-zero rows or all-zero columns for (int piece=0; piece<9; ++piece) { for (int rotation=1; rotation<4; ++rotation ) { for ( int i=0; i<5; ++i ) { if ( all_pieces[piece][rotation][0][i] ) goto next; // Something in the first row } for ( int r=0;r<4;++r ) { for ( int c=0;c<5;++c ) { all_pieces[piece][rotation][r][c] = all_pieces[piece][rotation][r+1][c]; } } for ( int c=0;c<5;++c ) { all_pieces[piece][rotation][4][c] = 0; } --rotation; continue; next: ; } } for (int piece=0; piece<9; ++piece) { for (int rotation=1; rotation<4; ++rotation ) { for ( int i=0; i<5; ++i ) { if ( all_pieces[piece][rotation][i][0] ) goto next2; // Something in the first column } for ( int r=0;r<5;++r ) { for ( int c=0;c<4;++c ) { all_pieces[piece][rotation][r][c] = all_pieces[piece][rotation][r][c+1]; } } for ( int r=0;r<5;++r ) { all_pieces[piece][rotation][r][4] = 0; } --rotation; continue; next2: ; } } }
Before writing the code to try all the combinations and find the solution, I need to be able to display the board. I also need to be able to display the pieces to check that I've coded and rotated them correctly. This is a place where spending a few minutes extra to have nice readable output can save a lot of time in understanding the results. Using a graphics toolkit or generating HTML would be overkill for this problem. Simple printing to the console would be fine, but tossing in some ANSI color codes to make the pieces easier to visualize would be well worth the effort. Fortunately, I have a handy set of ANSI color code defines:
#define _CN "\033[m" // Reset to default color and attributes #define _CRED "\033[1;31m" // Set text to bold red #define _Cred "\033[31m" // Set text to red #define _C_red "\033[4;31m" // Set text to underlined and red #define _C_RED "\033[4;1;31m" // Set text to underline and bold red #define _Bred "\033[41m" // Set background to red #define _CGRN "\033[1;32m" #define _Cgrn "\033[32m" #define _C_grn "\033[4;32m" #define _C_GRN "\033[4;1;32m" #define _Bgrn "\033[42m" #define _CYEL "\033[1;33m" #define _Cyel "\033[33m" #define _C_yel "\033[4;33m" #define _C_YEL "\033[4;1;33m" #define _Byel "\033[43m" #define _CBLU "\033[1;34m" #define _Cblu "\033[34m" #define _C_blu "\033[4;34m" #define _C_BLU "\033[4;1;34m" #define _Bblu "\033[44m" #define _CMAG "\033[1;35m" #define _Cmag "\033[35m" #define _C_mag "\033[4;35m" #define _C_MAG "\033[4;1;35m" #define _Bmag "\033[45m" #define _CCYN "\033[1;36m" #define _Ccyn "\033[36m" #define _C_cyn "\033[4;36m" #define _C_CYN "\033[4;1;36m" #define _Bcyn "\033[46m" #define _CWHT "\033[1;37m" #define _Cwht "\033[37m" #define _C_wht "\033[4;37m" #define _C_WHT "\033[4;1;37m" #define _Bwht "\033[47m" #define _CBLK "\033[1;30m" #define _Cblk "\033[30m" #define _C_blk "\033[4;30m" #define _C_BLK "\033[4;1;30m" #define _Bblk "\033[40m" /* * ANSI attribute strings */ #define _A_BOLD "\033[1m" // Leave color and underline-status as-is, set BOLD #define _A_UNDER "\033[4m" // Leave color and bold-status as-is, set UNDERLINE #define _A_BOLD_UNDER "\033[1;4m" // Just an optimized version of _A_BOLD _A_UNDER
So using those defines to display the grid and the pieces is fairly straightforward. You'll notice that I take advantage of C's string concatenation--any two strings separated only by whitespace are treated as a single string.
void display_grid(void) { printf(_Bblk" "_CN"\n"); for (int row=0;row<11;++row) { printf(_Bblk" "_CN); for (int col=0;col<11;++col) { char c; c = grid[row][col] + '0'; switch(grid[row][col]) { case 0: c=' '; printf(_Bwht); break; case 1: printf(_Bcyn); break; case 2: case 3: printf(_Bblu); break; case 4: case 5: printf(_Bmag); break; case 6: case 7: printf(_Byel); break; case 8: printf(_Bred); break; case 9: printf(_Bgrn); break; case BORDER: c=' '; printf(_Bblk); break; } printf("%c"_CN,c); } printf(_Bblk" "_CN"\n"); } printf(_Bblk" "_CN"\n"); printf("\n"); } void display_pieces(void) { for (int piece=0;piece<9;++piece) { printf("Piece %d rotations\n",piece+1); for (int row=0;row<5;++row) { for (int rotation=0;rotation<4;++rotation) { for (int col=0;col<5;++col) { char c; c = all_pieces[piece][rotation][row][col] ? '1' + piece : ' '; switch(all_pieces[piece][rotation][row][col] * (piece+1)) { case 0: c=' '; printf(_Bwht); break; case 1: printf(_Bcyn); break; case 2: case 3: printf(_Bblu); break; case 4: case 5: printf(_Bmag); break; case 6: case 7: printf(_Byel); break; case 8: printf(_Bred); break; case 9: printf(_Bgrn); break; default: printf("invalid"); break; } printf("%c"_CN,c); } printf(" "); } printf("\n"); } } }
With the above code, I have all that is needed to display the pre-rotated pieces (which proved vital for debugging mangled rotations) and the game board with any pieces placed in it. Starting out, it looks like:
Piece 1 rotations 11 1 1 1 111 11 11111 1111 11111 111 111 111 1 1111 11 11 1 1 Piece 2 rotations 222 2 2 2 2 222 222 222 2222 222 2222 222 222 2 2 2 222 2 Piece 3 rotations 3 3 3333 3 333 333 3333 3333 3333 333 333 333 3333 3333 3 333 3 3 Piece 4 rotations 4 4 4 4 4 4444 444 4444 4444 4444 44 4444 44 4 4 4444 4 444 4 4 Piece 5 rotations 555 5 555 55 555 555 555 555 555 555 555 555 55 5 Piece 6 rotations 6666 6 6 6 666 666 666 666 66 6 6 66 6666 666 666 6 Piece 7 rotations 777 7 7 7 777 7777 777 7777 77 7 7 77 777 777 777 7 Piece 8 rotations 888 8 8 8 88 888 888 888 88 8 8 88 888 888 88 8 Piece 9 rotations 99 9 99 99 9999 99 9999 999 99 999 99 99 99 9 Empty board
So the the code to actually go through the placements feels anticlimactic at this point. It simply marches through the puzzle, trying every possible combination in much the way I would do if I were doing an exhaustive search by hand. Here's the complete program:
/* * Find the solution or solutions to The Infuriater * * By Preston Crow * * gcc -std=c99 -W -Wall puzzle.c -o puzzle -O3 && puzzle */ #include <stdio.h> #include <stdlib.h> #include <string.h> #define _CN "\033[m" // Reset to default color and attributes #define _CRED "\033[1;31m" // Set text to bold red #define _Cred "\033[31m" // Set text to red #define _C_red "\033[4;31m" // Set text to underlined and red #define _C_RED "\033[4;1;31m" // Set text to underline and bold red #define _Bred "\033[41m" // Set background to red #define _CGRN "\033[1;32m" #define _Cgrn "\033[32m" #define _C_grn "\033[4;32m" #define _C_GRN "\033[4;1;32m" #define _Bgrn "\033[42m" #define _CYEL "\033[1;33m" #define _Cyel "\033[33m" #define _C_yel "\033[4;33m" #define _C_YEL "\033[4;1;33m" #define _Byel "\033[43m" #define _CBLU "\033[1;34m" #define _Cblu "\033[34m" #define _C_blu "\033[4;34m" #define _C_BLU "\033[4;1;34m" #define _Bblu "\033[44m" #define _CMAG "\033[1;35m" #define _Cmag "\033[35m" #define _C_mag "\033[4;35m" #define _C_MAG "\033[4;1;35m" #define _Bmag "\033[45m" #define _CCYN "\033[1;36m" #define _Ccyn "\033[36m" #define _C_cyn "\033[4;36m" #define _C_CYN "\033[4;1;36m" #define _Bcyn "\033[46m" #define _CWHT "\033[1;37m" #define _Cwht "\033[37m" #define _C_wht "\033[4;37m" #define _C_WHT "\033[4;1;37m" #define _Bwht "\033[47m" #define _CBLK "\033[1;30m" #define _Cblk "\033[30m" #define _C_blk "\033[4;30m" #define _C_BLK "\033[4;1;30m" #define _Bblk "\033[40m" /* * ANSI attribute strings */ #define _A_BOLD "\033[1m" // Leave color and underline-status as-is, set BOLD #define _A_UNDER "\033[4m" // Leave color and bold-status as-is, set UNDERLINE #define _A_BOLD_UNDER "\033[1;4m" // Just an optimized version of _A_BOLD _A_UNDER int grid[11][11]; int pieces[9][5][5] = { // first four pieces are "big" and take four rows { { 0,1,1,0,0 }, { 0,1,1,1,0 }, { 1,1,1,1,1 }, { 0,1,0,0,0 }, { 0,0,0,0,0 } }, { { 1,1,1,0,0 }, { 0,1,1,1,0 }, { 1,1,1,0,0 }, { 0,1,0,0,0 }, { 0,0,0,0,0 } }, { { 0,1,0,0,0 }, { 0,1,1,1,0 }, { 0,1,1,1,1 }, { 1,1,1,1,0 }, { 0,0,0,0,0 } }, { { 0,1,0,0,0 }, { 1,1,1,1,0 }, { 0,1,1,1,1 }, { 0,1,0,1,0 }, { 0,0,0,0,0 } }, // remaining five pieces take three rows { { 0,1,1,1,0 }, { 1,1,1,0,0 }, { 1,1,1,0,0 }, { 0,0,0,0,0 }, { 0,0,0,0,0 } }, { { 1,1,1,1,0 }, { 1,1,1,0,0 }, { 1,0,1,0,0 }, { 0,0,0,0,0 }, { 0,0,0,0,0 } }, { { 1,1,1,0,0 }, { 1,1,1,1,0 }, { 1,0,1,0,0 }, { 0,0,0,0,0 }, { 0,0,0,0,0 } }, { { 0,1,1,1,0 }, { 1,1,1,0,0 }, { 1,0,1,0,0 }, { 0,0,0,0,0 }, { 0,0,0,0,0 } }, { { 1,1,0,0,0 }, { 1,1,1,1,0 }, #if 0 { 0,1,1,0,0 }, #else { 1,1,1,0,0 }, #endif { 0,0,0,0,0 }, { 0,0,0,0,0 } } }; int all_pieces[9][4][5][5]; int place[9][3]; // rotation,row,col for the piece #define BORDER 10 void init_border(void) { // Set grid to zero memset(grid,0,sizeof(grid)); // Border defaults to blocked for(int i=0;i<11;++i) { grid[0][i] = grid[i][0] = grid[10][i] = grid[i][10] = BORDER; } // Clear spots grid[0][2] = grid[0][4] = grid[0][8] = 0; grid[10][1] = grid[10][4] = grid[10][6] = grid[10][8] = 0; grid[3][0] = grid[5][0] = grid[8][0] = 0; grid[1][10] = grid[5][10] = grid[7][10] = grid[9][10] = 0; } void init_rotations(void) { for (int piece=0; piece<9; ++piece) { for (int rotation=0; rotation<4; ++rotation ) { if ( rotation == 0 ) { for ( int r=0;r<5;++r ) { for ( int c=0;c<5;++c ) { all_pieces[piece][rotation][r][c] = pieces[piece][r][c]; } } } else { for ( int r=0;r<5;++r ) { for ( int c=0;c<5;++c ) { all_pieces[piece][rotation][4-c][r] = all_pieces[piece][rotation-1][r][c]; } } } } } // Now shift rotations to all be in the upper-left (no all-zero rows or all-zero columns for (int piece=0; piece<9; ++piece) { for (int rotation=1; rotation<4; ++rotation ) { for ( int i=0; i<5; ++i ) { if ( all_pieces[piece][rotation][0][i] ) goto next; // Something in the first row } for ( int r=0;r<4;++r ) { for ( int c=0;c<5;++c ) { all_pieces[piece][rotation][r][c] = all_pieces[piece][rotation][r+1][c]; } } for ( int c=0;c<5;++c ) { all_pieces[piece][rotation][4][c] = 0; } --rotation; continue; next: ; } } for (int piece=0; piece<9; ++piece) { for (int rotation=1; rotation<4; ++rotation ) { for ( int i=0; i<5; ++i ) { if ( all_pieces[piece][rotation][i][0] ) goto next2; // Something in the first column } for ( int r=0;r<5;++r ) { for ( int c=0;c<4;++c ) { all_pieces[piece][rotation][r][c] = all_pieces[piece][rotation][r][c+1]; } } for ( int r=0;r<5;++r ) { all_pieces[piece][rotation][r][4] = 0; } --rotation; continue; next2: ; } } } void display_grid(void) { printf(_Bblk" "_CN"\n"); for (int row=0;row<11;++row) { printf(_Bblk" "_CN); for (int col=0;col<11;++col) { char c; c = grid[row][col] + '0'; switch(grid[row][col]) { case 0: c=' '; printf(_Bwht); break; case 1: printf(_Bcyn); break; case 2: case 3: printf(_Bblu); break; case 4: case 5: printf(_Bmag); break; case 6: case 7: printf(_Byel); break; case 8: printf(_Bred); break; case 9: printf(_Bgrn); break; case BORDER: c=' '; printf(_Bblk); break; } printf("%c"_CN,c); } printf(_Bblk" "_CN"\n"); } printf(_Bblk" "_CN"\n"); printf("\n"); } void display_pieces(void) { for (int piece=0;piece<9;++piece) { printf("Piece %d rotations\n",piece+1); for (int row=0;row<5;++row) { for (int rotation=0;rotation<4;++rotation) { for (int col=0;col<5;++col) { char c; c = all_pieces[piece][rotation][row][col] ? '1' + piece : ' '; switch(all_pieces[piece][rotation][row][col] * (piece+1)) { case 0: c=' '; printf(_Bwht); break; case 1: printf(_Bcyn); break; case 2: case 3: printf(_Bblu); break; case 4: case 5: printf(_Bmag); break; case 6: case 7: printf(_Byel); break; case 8: printf(_Bred); break; case 9: printf(_Bgrn); break; default: printf("invalid"); break; } printf("%c"_CN,c); } printf(" "); } printf("\n"); } } } void remove_piece(int piece) { for (int row=0;row<11;++row) { for (int col=0;col<11;++col) { if ( grid[row][col] == piece+1 ) { grid[row][col] = 0; } } } } int place_piece_here(int piece,int rotation,int row,int col) { for ( int r=0; r<5; ++r ) { for ( int c=0; c<5; ++c ) { if ( all_pieces[piece][rotation][r][c] ) { if ( r+row >= 11 || c+col >=11 ) return 0; // Off the grid if ( grid[r+row][c+col] ) return 0; // Spot full } } } // Yes, it goes here; put it in the grid for ( int r=0; r<5; ++r ) { for ( int c=0; c<5; ++c ) { if ( all_pieces[piece][rotation][r][c] ) { grid[r+row][c+col] = piece+1; } } } return 1; } // Place a piece if possible; return true if placed int place_piece(int piece) { for ( int rotation=place[piece][0]; rotation<4; ++rotation,place[piece][1]=0,place[piece][2]=0 ) { for ( int row=place[piece][1]; row<9; ++row,place[piece][2]=0 ) { for ( int col=place[piece][2]; col<9; ++col ) { if ( place_piece_here(piece,rotation,row,col) ) { place[piece][0]=rotation; place[piece][1]=row; place[piece][2]=col; return 1; } } } } return 0; } int main(int argc,char *argv[]) { (void)argc;(void)argv; init_border(); init_rotations(); display_pieces(); printf("Empty board\n"); display_grid(); int solutions=0; for (int i=0; i<9; ++i ) { if ( place_piece(i) ) { if ( i == 8 ) { ++solutions; printf("Solution %d found:\n",solutions); display_grid(); remove_piece(i); } else { if ( i >=7 && 0 ) // debug { printf("Placed %d pieces:\n",i+1); display_grid(); } if ( i != 8 ) { for ( int j=0;j<3; ++j) place[i+1][j]=0; } continue; } } if ( i == 0 ) { if ( !solutions ) { printf("Failed to solve puzzle\n"); } break; } //printf("Can't place piece %d; remove piece %d\n",i+1,i); // Advance the previous piece --i; remove_piece(i); // printf("piece %d was at rot,row,col %d,%d,%d\n",i+1,place[i][0],place[i][1],place[i][2]); ++place[i][2]; // Go back one more as the loop will increment --i; // printf("piece %d was at rot,row,col %d,%d,%d\n",i+1,place[i][0],place[i][1],place[i][2]); } //display_grid(); return 0; }
Now much to my surprise, once I had debugged it, it ran quite fast. I had guessed that it might run for hours before finding the solution, but it ran to completion in under a minute. The biggest surprise was that it found not one, but eight solutions! I shared my results with the creator of the puzzle. He said he had also used a computer to verify that there was only one solution, but apparently his program had a bug. He has made a slight change to the puzzle, so if you buy it now, it will have one unique solution.
In case you're interested in buying and playing with the puzzle yourself, I won't spoil it by posting the solution here. It's simple enough to run the program if you want to see them.
And a note on copyright: While I hold the copyright on all my posts, including the above code, in my opinion, the ANSI color code defines are simple and obvious enough that they can hardly be considered copyrightable, so feel free to use them.
