/*********************************************************************
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 <stdio.h>
#include <stdlib.h>

#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<chigh; ++i)
if(leastc[i] == b1 || leastc[i] == b2) leastc[i] = b3;
cn = b3;
}
}

if(!cn) {
if(chigh >= 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<chigh; ++i) {
if(!csize[i]) continue;
#if DEBUG
printf("hole %d%c\n", csize[i], (atbottom[i] ? '+' : ' '));
#endif
if(!atbottom[i] && csize[i]%6) 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(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 */