/********************************************************************* Pack the 35 hexominoes into a right isosceles triangle. They won't tile a rectangle due to the checkerboard argument. 11 pieces have an excess or deficiency of 2 white squares, +2 or -2, yet in a rectangle the total excess is 0. But things work out in a triangle. *********************************************************************/ #include #include #define DEBUG 0 #define PERFORM 0 /********************************************************************* First solution under the current algorithm. 24m24s A AB ABS ABSS ABSSC ABBSCC DGGICEE DGGICEUU DDGICEUUU DFGIIEEHUL DFFNIWWHHL4 KFNNWWWHHL44 KFFNMMWHLLL4O KKKNNMVV5544O9 KTTTQMVVV55OO99 2TTTQMMV5577OO99 222QQQPJJJJ777393 Z2YYQPPPP1J876333X Z2ZYRRRP11J886663XX ZZZYYYRRR11188866XXX *********************************************************************/ /* power of 2 for efficiency */ static char board[22][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 */ /* I might use this some day, first piece. */ static const char startpiece[] = { 1,2,3,3,6,8,9,19,24,33,35,0}; static const char startorient[] = { 1,7,14,15,31,44,50,108,134,198,214,0}; static char pheight[216]; /* flipp triangle and look for asymmetry */ static int tflip(void) { return (board[1][1] > board[20][20]); } 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(row=1; row<=20; ++row) { for(col=1; col<=row; ++col) 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 > x) ++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 > x) { 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 < 20) atbottom[cn] = 1; goto top; done: x = x0, y = y0; top2: if(++y > x) { 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= 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(tflip()) { ; /* skip this one */ } else { ++nsols; if(!countflag) showBoard(); exit(0); } } 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; 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: trixsol [-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; int j; for(j=0; j<10; j+=2) if(s[j] > h) h = s[j]; pheight[i] = h; } for(i=0; i<22; ++i) { board[0][i] = -1; board[21][i] = -1; board[i][0] = -1; board[i][21] = -1; } for(i=1; i<=20; ++i) board[i][i+1] = -1; place(1, 0, 0); if(countflag) printf("%d solutions\n", nsols); exit(0); } /* main */