/********************************************************************* Pack the 35 hexominoes into a rhombus minus a ssquare in the middle. *********************************************************************/ #include #include #include #define DEBUG 0 #define PERFORM 0 /********************************************************************* First solution under the current algorithm. 0.18 seconds P NPPPP QNNNNPZZZ QQQQ44N4Z1Z66 IIIIQUU444Z116SSS CCCCCIIUUUM111669SSSW BBBBBCHHFFXUMMMM699888WWW AAAAAABHHHHFXX*OOM998833WWRRR DDDDDGGJFFXXXLOO9Y8553RRR DGGGGJKFLLLLOYYY55333 JJJJKEEEELOYTTT55 KKKEVVE72YTTT KVVV77222 V7722 7 *********************************************************************/ /* power of 2 for efficiency */ static char board[31][32]; static char shapes[217][16] = { {0x1,1,0,1,0,2,0,3,0,4,0,5}, {0x7f,1,1,0,2,0,3,0,4,0,5,0}, {0x1,2,0,1,0,2,0,3,0,4,1,4}, {0x1,2,0,1,0,2,0,3,0,4,1,0}, {0x7,2,1,0,1,1,1,2,1,3,1,4}, {0x53,2,1,0,1,-1,1,-2,1,-3,1,-4}, {0x71,2,0,1,1,0,2,0,3,0,4,0}, {0x7f,2,1,0,2,0,3,0,4,0,4,1}, {0x7f,2,1,0,2,0,3,0,4,0,4,-1}, {0x71,2,0,1,1,1,2,1,3,1,4,1}, {0x1,3,0,1,0,2,0,3,0,4,1,3}, {0x1,3,0,1,0,2,0,3,0,4,1,1}, {0x3,3,1,0,1,1,1,2,1,3,1,-1}, {0x43,3,1,0,1,-1,1,-2,1,-3,1,1}, {0x47,3,1,0,2,0,3,0,4,0,1,1}, {0x7f,3,1,0,2,0,3,0,4,0,3,1}, {0x53,3,1,0,2,0,3,0,4,0,1,-1}, {0x7f,3,1,0,2,0,3,0,4,0,3,-1}, {0x1,4,0,1,0,2,0,3,0,4,1,2}, {0x3,4,1,0,1,1,1,2,1,-1,1,-2}, {0x7f,4,1,0,2,0,3,0,4,0,2,1}, {0x7f,4,1,0,2,0,3,0,4,0,2,-1}, {0x1,5,0,1,0,2,0,3,1,0,1,3}, {0x7,5,1,0,1,1,1,2,1,3,0,3}, {0x71,5,0,1,1,0,2,0,3,0,3,1}, {0x71,5,0,1,1,1,2,1,3,1,3,0}, {0x1,6,0,1,0,2,0,3,1,0,1,2}, {0x1,6,0,1,0,2,0,3,1,1,1,3}, {0x7,6,1,0,1,1,1,2,1,3,0,2}, {0x3,6,1,0,1,1,1,2,1,-1,0,2}, {0x71,6,0,1,1,0,2,0,3,0,2,1}, {0x47,6,1,0,2,0,3,0,1,1,3,1}, {0x53,6,1,0,2,0,3,0,1,-1,3,-1}, {0x71,6,0,1,1,1,2,1,3,1,2,0}, {0x1,7,0,1,0,2,0,3,1,0,1,1}, {0x1,7,0,1,0,2,0,3,1,2,1,3}, {0x31,7,1,0,1,1,1,2,1,3,0,1}, {0x51,7,1,0,1,1,1,-1,1,-2,0,1}, {0x71,7,0,1,1,0,2,0,3,0,1,1}, {0x7f,7,1,0,2,0,3,0,2,1,3,1}, {0x7f,7,1,0,2,0,3,0,2,-1,3,-1}, {0x71,7,0,1,1,1,2,1,3,1,1,0}, {0x1,8,0,1,0,2,0,3,1,1,1,2}, {0x11,8,1,0,1,1,1,2,1,-1,0,1}, {0x47,8,1,0,2,0,3,0,1,1,2,1}, {0x53,8,1,0,2,0,3,0,1,-1,2,-1}, {0x1,9,0,1,0,2,0,3,1,0,1,-1}, {0x1,9,0,1,0,2,0,3,1,3,1,4}, {0x31,9,0,1,1,1,1,2,1,3,1,4}, {0x51,9,0,1,1,0,1,-1,1,-2,1,-3}, {0x47,9,1,0,1,1,2,1,3,1,4,1}, {0x53,9,1,0,1,-1,2,-1,3,-1,4,-1}, {0x7f,9,1,0,2,0,3,0,3,1,4,1}, {0x7f,9,1,0,2,0,3,0,3,-1,4,-1}, {0x1,10,0,1,0,2,0,3,1,0,2,0}, {0x1,10,0,1,0,2,0,3,1,3,2,3}, {0x7f,10,1,0,2,0,2,1,2,2,2,3}, {0x7f,10,1,0,2,0,2,-1,2,-2,2,-3}, {0x7f,10,1,0,2,0,3,0,3,1,3,2}, {0x7f,10,1,0,2,0,3,0,3,-1,3,-2}, {0x41,10,1,0,2,0,3,0,0,1,0,2}, {0x41,10,0,1,0,2,1,2,2,2,3,2}, {0x1,11,0,1,0,2,0,3,1,1,2,1}, {0x1,11,0,1,0,2,0,3,1,2,2,2}, {0x7f,11,1,0,2,0,2,1,2,2,2,-1}, {0x7f,11,1,0,2,0,2,-1,2,-2,2,1}, {0x7f,11,1,0,2,0,3,0,2,1,2,2}, {0x7f,11,1,0,2,0,3,0,2,-1,2,-2}, {0x7,11,1,0,2,0,3,0,1,1,1,2}, {0x53,11,1,0,2,0,3,0,1,-1,1,-2}, {0x41,12,0,1,0,2,1,1,2,1,3,1}, {0x7f,12,1,0,2,0,3,0,3,1,3,-1}, {0x7,12,1,0,1,1,1,2,1,3,2,0}, {0x53,12,1,0,1,-1,1,-2,1,-3,2,0}, {0x71,13,0,1,1,1,2,1,3,1,3,2}, {0x71,13,0,1,1,0,2,0,3,0,3,-1}, {0x7,13,1,0,1,1,1,2,1,3,2,3}, {0x53,13,1,0,1,-1,1,-2,1,-3,2,-3}, {0x71,14,0,1,1,1,2,1,3,1,2,2}, {0x71,14,0,1,1,0,2,0,3,0,2,-1}, {0x53,14,1,0,2,0,3,0,3,1,1,-1}, {0x47,14,1,0,2,0,3,0,3,-1,1,1}, {0x7,14,1,0,1,1,1,2,1,3,2,2}, {0x53,14,1,0,1,-1,1,-2,1,-3,2,-2}, {0x3,14,1,0,1,1,1,2,1,-1,2,2}, {0x43,14,1,0,1,1,1,-1,1,-2,2,-2}, {0x31,15,0,1,1,1,2,1,3,1,1,2}, {0x51,15,0,1,1,0,2,0,3,0,1,-1}, {0x7f,15,1,0,2,0,3,0,3,1,2,-1}, {0x7f,15,1,0,2,0,3,0,3,-1,2,1}, {0x7,15,1,0,1,1,1,2,1,3,2,1}, {0x53,15,1,0,1,-1,1,-2,1,-3,2,-1}, {0x3,15,1,0,1,1,1,2,1,-1,2,-1}, {0x43,15,1,0,1,1,1,-1,1,-2,2,1}, {0x3,16,1,-1,1,0,1,1,1,2,2,1}, {0x43,16,1,-1,1,-2,1,0,1,1,2,-1}, {0x47,16,1,0,2,0,3,0,1,1,2,-1}, {0x53,16,1,0,2,0,3,0,2,1,1,-1}, {0x3,17,1,-1,1,0,1,1,1,2,2,0}, {0x43,17,1,-1,1,-2,1,0,1,1,2,0}, {0x43,17,1,0,2,0,3,0,1,1,1,-1}, {0x7f,17,1,0,2,0,3,0,2,1,2,-1}, {0x41,18,0,1,0,2,1,0,1,-1,1,-2}, {0x41,18,0,1,0,2,1,2,1,3,1,4}, {0x7f,18,1,0,2,0,2,1,3,1,4,1}, {0x7f,18,1,0,2,0,2,-1,3,-1,4,-1}, {0x41,19,0,1,0,2,1,-1,1,0,1,1}, {0x41,19,0,1,0,2,1,1,1,2,1,3}, {0x47,19,1,0,2,0,1,1,2,1,3,1}, {0x53,19,1,0,2,0,1,-1,2,-1,3,-1}, {0x71,20,0,1,1,0,1,1,2,0,2,1}, {0x41,20,0,1,0,2,1,0,1,1,1,2}, {0x71,21,0,1,1,0,1,1,2,0,2,-1}, {0x71,21,0,1,1,0,1,1,2,1,2,2}, {0x31,21,0,1,1,1,1,2,2,1,2,2}, {0x51,21,0,1,1,0,1,-1,2,0,2,-1}, {0x31,21,0,1,1,0,1,1,1,2,2,2}, {0x51,21,0,1,1,0,1,1,1,-1,2,-1}, {0x7,21,1,0,1,1,1,2,2,1,2,2}, {0x53,21,1,0,1,-1,1,-2,2,-1,2,-2}, {0x51,22,0,1,1,0,1,1,2,0,1,-1}, {0x31,22,0,1,1,0,1,1,2,1,1,2}, {0x43,22,1,-1,1,0,1,1,2,0,2,1}, {0x43,22,1,-1,1,0,1,1,2,0,2,-1}, {0x51,23,0,1,1,0,1,1,2,1,1,-1}, {0x31,23,0,1,1,0,1,1,2,0,1,2}, {0x41,23,0,1,1,0,1,1,2,1,0,2}, {0x41,23,0,1,1,1,2,1,0,2,1,2}, {0x47,23,1,0,2,0,1,1,2,1,2,-1}, {0x53,23,1,0,2,0,2,1,1,-1,2,-1}, {0x7,23,1,0,1,1,1,2,2,0,2,1}, {0x53,23,1,0,1,-1,1,-2,2,0,2,-1}, {0x41,24,0,1,0,2,1,1,1,2,2,2}, {0x53,24,1,0,1,-1,2,0,2,-1,2,-2}, {0x47,24,1,0,1,1,2,0,2,1,2,2}, {0x41,24,0,1,0,2,1,0,1,1,2,0}, {0x41,25,0,1,0,2,1,2,2,2,2,3}, {0x41,25,0,1,0,2,1,0,2,0,2,-1}, {0x7,25,1,0,1,1,1,2,2,2,3,2}, {0x53,25,1,0,1,-1,1,-2,2,-2,3,-2}, {0x71,25,0,1,1,0,2,0,2,-1,2,-2}, {0x71,25,0,1,1,1,2,1,2,2,2,3}, {0x7f,25,1,0,2,0,2,1,2,2,3,2}, {0x7f,25,1,0,2,0,2,-1,2,-2,3,-2}, {0x41,26,0,1,0,2,1,2,2,2,2,1}, {0x41,26,0,1,0,2,1,0,2,0,2,1}, {0xb,26,1,0,2,0,2,1,2,2,1,2}, {0x6d,26,1,0,2,0,2,-1,2,-2,1,-2}, {0x41,26,0,1,0,2,1,0,2,0,1,2}, {0x41,26,0,1,0,2,1,0,1,2,2,2}, {0x71,26,0,1,1,1,2,1,2,0,2,-1}, {0x71,26,0,1,1,0,2,0,2,1,2,2}, {0x41,27,0,1,0,2,1,0,2,0,1,-1}, {0x41,27,0,1,0,2,1,2,2,2,1,3}, {0x43,27,1,-1,1,0,1,1,2,1,3,1}, {0x43,27,1,-1,1,0,1,1,2,-1,3,-1}, {0x53,27,1,0,2,0,1,-1,2,1,2,2}, {0x47,27,1,0,2,0,1,1,2,-1,2,-2}, {0x7f,27,1,0,2,0,2,1,2,2,3,1}, {0x7f,27,1,0,2,0,2,-1,2,-2,3,-1}, {0x7,28,1,0,1,1,1,2,2,1,3,1}, {0x53,28,1,0,1,-1,1,-2,2,-1,3,-1}, {0x31,28,0,1,1,1,2,1,1,2,1,3}, {0x51,28,0,1,1,0,2,0,1,-1,1,-2}, {0x7f,28,1,0,2,-1,2,0,2,1,3,1}, {0x7f,28,1,0,2,-1,2,0,2,1,3,-1}, {0x7,28,1,0,1,1,1,2,2,0,2,-1}, {0x53,28,1,0,1,-1,1,-2,2,0,2,1}, {0x41,29,0,1,0,2,1,1,2,1,2,2}, {0x41,29,0,1,0,2,1,1,2,1,2,0}, {0x7,29,1,0,1,1,1,2,0,2,2,0}, {0x7,29,1,0,1,1,1,2,0,2,2,2}, {0x71,29,0,1,1,0,2,0,2,-1,2,1}, {0x71,29,0,1,1,1,2,1,2,0,2,2}, {0x7,29,1,0,1,1,1,2,2,0,2,2}, {0x53,29,1,0,1,-1,1,-2,2,0,2,-2}, {0x41,30,0,1,0,2,1,0,1,2,1,3}, {0x41,30,0,1,0,2,1,0,1,2,1,-1}, {0x31,30,0,1,1,1,1,2,1,3,0,3}, {0x7,30,1,0,1,1,1,2,0,2,0,3}, {0x71,30,0,1,1,0,2,0,2,1,3,1}, {0x71,30,0,1,1,1,2,1,2,0,3,0}, {0x53,30,1,0,1,-1,2,-1,3,-1,3,0}, {0x47,30,1,0,1,1,2,1,3,1,3,0}, {0x7,31,1,0,1,1,1,2,0,2,2,1}, {0x51,31,0,1,1,0,1,-1,2,0,2,1}, {0x31,31,0,1,1,1,1,2,2,0,2,1}, {0x43,31,1,-1,1,0,1,1,2,1,2,-1}, {0x7,32,1,0,1,1,1,2,2,2,2,3}, {0x53,32,1,0,1,-1,1,-2,2,-2,2,-3}, {0x71,32,0,1,1,0,2,0,2,-1,3,-1}, {0x71,32,0,1,1,1,2,1,2,2,3,2}, {0x51,32,0,1,1,0,1,-1,1,-2,2,-2}, {0x31,32,0,1,1,1,1,2,1,3,2,3}, {0x47,32,1,0,1,1,2,1,3,1,3,2}, {0x53,32,1,0,1,-1,2,-1,3,-1,3,-2}, {0x51,33,0,1,1,0,1,-1,1,-2,2,-1}, {0x31,33,0,1,1,1,1,2,1,3,2,2}, {0x47,33,1,0,1,1,2,1,3,1,2,2}, {0x53,33,1,0,1,-1,2,-1,3,-1,2,-2}, {0x43,33,1,-1,1,0,1,1,2,1,2,2}, {0x43,33,1,-1,1,0,1,1,2,-1,2,-2}, {0x47,33,1,0,1,1,2,0,2,-1,3,-1}, {0x53,33,1,0,1,-1,2,0,2,1,3,1}, {0x41,34,0,1,0,2,1,2,1,3,2,3}, {0x41,34,0,1,0,2,1,0,1,-1,2,-1}, {0x51,34,0,1,1,0,1,-1,2,-1,3,-1}, {0x31,34,0,1,1,1,1,2,2,2,3,2}, {0x47,34,1,0,1,1,2,1,2,2,2,3}, {0x53,34,1,0,1,-1,2,-1,2,-2,2,-3}, {0x7f,34,1,0,2,0,2,1,3,1,3,2}, {0x7f,34,1,0,2,0,2,-1,3,-1,3,-2}, {0x31,35,0,1,1,1,1,2,2,2,2,3}, {0x51,35,0,1,1,0,1,-1,2,-1,2,-2}, {0x47,35,1,0,1,1,2,1,2,2,3,2}, {0x53,35,1,0,1,-1,2,-1,2,-2,3,-2}, {0} }; /* uneven: 3 6 12 14 17 19 22 24 27 29 33 */ static char pheight[216]; char used[35+1]; int level; int nsols; char countflag, dispflag; int lvt, lvc; /* print solution */ static void showBoard(void) { int row, col; static const char displetter[] = " ABCDEFGHIJKLMNOPQRSTUVWXYZ123456789*"; for(col=1; col<=15; ++col) { for(row=1; row<=29; ++row) { if(board[row][col] < 0) { if(dispflag) printf(" "); continue; } putchar(displetter[board[row][col]]); } putchar(dispflag ? '\n' : '|'); } putchar('\n'); fflush(stdout); } static void nextLocation(int *xp, int *yp) { int x, y; x = *xp, y = *yp; top: if(++y > 15) ++x, y = 1; if(board[x][y]) goto top; *xp = x, *yp = y; } static char leastc[128]; static char atbottom[128]; static int csize[128]; static int component(int x0, int y0, int h) { int cn, b1, b2, b3; int x, y; int clow, chigh; int i; clow = chigh = 40; x = x0, y = y0; top: if(++y > 15) { if(++x > h) goto done; y = 1; } if(board[x][y]) goto top; cn = 0; b1 = board[x][y-1]; b2 = board[x-1][y]; if(b1 >= 40) b1 = cn = leastc[b1]; if(b2 >= 40) { b2 = leastc[b2]; if(!cn) cn = b2; if(cn != b2) { b3 = b1; if(b2 < b1) b3 = b2; for(i=clow; i= 120) { fprintf(stderr, "component number too high\n"); exit(1); } cn = chigh; leastc[cn] = cn; atbottom[cn] = 0; csize[cn] = 0; ++chigh; } /* cn now the least number of its component, so far */ board[x][y] = cn; if(h == x && h < 29) atbottom[cn] = 1; goto top; done: x = x0, y = y0; top2: if(++y > 15) { if(++x > h) goto done2; y = 1; } if(board[x][y] < 40) goto top2; ++csize[leastc[board[x][y]]]; board[x][y] = 0; goto top2; done2: for(i=clow; i board[29][8]) return 1; if(board[15][1] > board[15][15]) return 1; return 0; } /* place a piece in the board; recursive */ static void place(int x, int y, int h1) { int i; char piece; const char *s; int shapelist, shapemask; /* find best location */ nextLocation(&x, &y); shapelist = 1; if(board[x][y+1]) { shapelist = 2; if(board[x+1][y-1]) { shapelist = 3; if(board[x+1][y+1]) shapelist = 4; } } else if(board[x][y+2]) { shapelist = 5; if(board[x+1][y-1]) shapelist = 6; } else if(board[x][y+3]) shapelist = 7; shapemask = (1 << (shapelist-1)); ++level; #if PERFORM /* rough measure of performance */ lvt += level; lvc++; if(lvc == 100000) { printf("%d\n", 10*lvt/lvc); lvc = lvt = 0; } #endif for(i=0; (s = shapes[i])[0]; ++i) { if(!(*s & shapemask)) continue; ++s; piece = *s++; if(used[piece]) continue; if(board[x + s[0]][y + s[1]]) continue; if(board[x + s[2]][y + s[3]]) continue; if(board[x + s[4]][y + s[5]]) continue; if(board[x + s[6]][y + s[7]]) continue; if(board[x + s[8]][y + s[9]]) continue; /* place the piece */ #if DEBUG if(level >= 1) { printf("placing piece %d[%d] at square %d,%d, level %d\n", piece, i, x, y, level); getchar(); } #endif used[piece] = 1; board[x][y] = piece; board[x+s[0]][y+s[1]] = piece; board[x+s[2]][y+s[3]] = piece; board[x+s[4]][y+s[5]] = piece; board[x+s[6]][y+s[7]] = piece; board[x+s[8]][y+s[9]] = piece; if(level == 35) { if(squareFlip()) { ; /* skip this one */ } else { ++nsols; if(!countflag && nsols % 1000 == 0) showBoard(); } } else { int h2 = h1; if(x + pheight[i] > h2) h2 = x + pheight[i]; if(!component(x, y, h2)) place(x, y, h2); } /* remove piece */ used[piece] = 0; board[x][y] = 0; board[x+s[0]][y+s[1]] = 0; board[x+s[2]][y+s[3]] = 0; board[x+s[4]][y+s[5]] = 0; board[x+s[6]][y+s[7]] = 0; board[x+s[8]][y+s[9]] = 0; } --level; } /* place */ void main(int argc, char **argv) { int i, j; if(argc > 1) { if(argv[1][0] == '-') { if(argv[1][1] == 'c') countflag = 1; if(argv[1][1] == 'd') dispflag = 1; ++argv, --argc; } } if(argc > 1) { fprintf(stderr, "usage: sqxsol [-c|-d]\n"); exit(1); } /* the height of each piece */ for(i=0; shapes[i][0]; ++i) { int h = 0; const char *s = shapes[i] + 2; for(j=0; j<10; j+=2) if(s[j] > h) h = s[j]; pheight[i] = h; } memset(board, -1, sizeof(board)); for(i=1; i<=15; ++i) { for(j=0; j+j