/* hexsol.c: find all solutions to the hex puzzle (pentomino packings */

#include <stdio.h>

/* column order is more efficient */
char board[8*12] = {
-1,-1,-1,-1,-1,-1,-1,-1,
-1,0,0,0,0,0,0,-1,
-1,0,0,0,0,0,0,-1,
-1,0,0,0,0,0,0,-1,
-1,0,0,0,0,0,0,-1,
-1,0,0,0,0,0,0,-1,
-1,0,0,0,0,0,0,-1,
-1,0,0,0,0,0,0,-1,
-1,0,0,0,0,0,0,-1,
-1,0,0,0,0,0,0,-1,
-1,0,0,0,0,0,0,-1,
-1,-1,-1,-1,-1,-1,-1,-1,
};

char shapes[][5] = {
{1, 7,8,9,16},
{2, 1,2,3,4},
{2, 8,16,24,32},
{3, 1,2,8,16},
{3, 1,2,10,18},
{3, 8,14,15,16},
{3, 8,16,17,18},
{3, 1,2,-6,-14},
{4, 1,2,9,17},
{4, 6,7,8,16},
{4, 8,15,16,17},
{4, 8,9,10,16},
{4, 1,-6,2,10},
{5, 1,2,8,10},
{5, 1,9,16,17},
{5, 2,8,9,10},
{5, 1,8,16,17},
{5,8,7,6,-2},
{6, 1,7,8,15},
{6, 1,9,10,18},
{6, 7,8,14,15},
{6, 8,9,17,18},
{6, 1,-7,8,7},
{6, 1,-7,-6,-14},
{6, 8,1,-7,-6},
{7, 1,8,15,16},
{7, 8,9,10,18},
{7, 1,9,17,18},
{7, 6,7,8,14},
{7, 8,1,2,-6},
{8, 1,2,3,8},
{8, 1,9,17,25},
{8, 5,6,7,8},
{8, 8,16,24,25},
{8, 8,9,10,11},
{8, 1,8,16,24},
{8, 1,2,3,11},
{8, 8,16,23,24},
{8, 1,2,3,-5},
{9, 1,2,8,9},
{9, 1,8,9,17},
{9, 1,7,8,9},
{9, 8,9,16,17},
{9, 1,8,9,10},
{9, 1,8,9,16},
{9, 1,2,9,10},
{9, 7,8,15,16},
{9, 1,2,-7,-6},
{9, 1,-7,8,9},
{10, 1,2,3,9},
{10, 7,8,16,24},
{10, 6,7,8,9},
{10, 8,16,17,24},
{10, 1,2,3,10},
{10, 8,15,16,24},
{10, 7,8,9,10},
{10, 8,9,16,24},
{10, 1,2,3,-7},
{10, 1,2,3,-6},
{10, 1,-7,9,17},
{11, 1,9,10,11},
{11, 7,8,15,23},
{11, 1,2,10,11},
{11, 8,15,16,23},
{11, 1,2,7,8},
{11, 8,9,17,25},
{11, 1,6,7,8},
{11, 8,16,17,25},
{11, 1,2,-6,-5},
{11, 1,-7,-6,-5},
{11, 1,-7,8,16},
{12, 1,9,10,17},
{12, 6,7,8,15},
{12, 7,8,16,17},
{12, 7,8,9,15},
{12, 1,7,8,16},
{12, 7,8,9,17},
{12, 8,9,15,16},
{12, 8,9,10,17},
{12, 1,2,9,-6},
{12, 1,2,10,-7},
{12, 1,2,8,-7},
{12, 1,-7,-6,9},
{12, 1,-7,9,10},
{0, 0,0,0,0},
};

/* valid positions for the cross */
/* prevents reflections and rotations */
int cross_pos[7] = { 11, 18, 19, 26, 27, 34, 35 };

char used[13];
int level;
int nsols;
char countflag, dispflag;


static void cross(int top) ;
static void place() ;
static int findloc() ;
static int test(int loc, int pattern) ;


void main(int argc, char **argv)
{
short i;

if(argc > 1) {
if(argv[1][0] == '-') {
if(argv[1][1] == 'c') countflag = 1;
if(argv[1][1] == 'd') dispflag = 1;
}
}

level = 1;
nsols = 0;
for(i=1; i<13; ++i) used[i] = 0;

for(i=0; i<7; ++i)
cross(cross_pos[i]);

if(countflag)
printf("%d solutions\n", nsols);
exit(0);
} /* main */

/* position the cross, and go */
static void cross(int top)
{
short i;
int piece;

piece = shapes[0][0];
used[piece] = 1;
for(i=1; i<5; ++i)
board[top + shapes[0][i]] = piece;
board[top] = piece;

place();

for(i=1; i<5; ++i)
board[top + shapes[0][i]] = 0;
board[top] = 0;
used[piece] = 0;
} /* cross */

/* place a piece in the board; recursive */
static void place()
{
short i, loc;
char piece;

/* find best location */
loc = findloc();
if(!loc) return; /* square that no piece fits into */
++level;

for(i=1; shapes[i][0]; ++i) {
if(!test(loc, i)) continue;

/* place the piece */
piece = shapes[i][0];
#ifdef DEBUG
printf("placing piece %d[%d] at square %d, level %d\n", piece, i, loc, level);
#endif
used[piece] = 1;
board[loc] = piece;
board[loc + shapes[i][1]] = piece;
board[loc + shapes[i][2]] = piece;
board[loc + shapes[i][3]] = piece;
board[loc + shapes[i][4]] = piece;

if(level == 12) {
static int row, col;

++nsols;
/* print solution */
if(!countflag) {
for(col=1; col<7; ++col) {
if(dispflag) putchar('\t');
for(row=1; row<11; ++row)
putchar('A'-1 + board[8*row + col]);
if(dispflag) putchar('\n');
}
putchar('\n');
if(dispflag) putchar('\n');
}
} else place();

/* remove piece */
used[piece] = 0;
board[loc] = 0;
board[loc + shapes[i][1]] = 0;
board[loc + shapes[i][2]] = 0;
board[loc + shapes[i][3]] = 0;
board[loc + shapes[i][4]] = 0;
}

--level;
} /* place */

static int findloc()
{
short i, j;
short count, bestcount, bestloc;

bestcount = 30000;

for(i=9; i<8*12-9; ++i) {
if(board[i]) continue;
if(!board[i-1]) continue;
if(!board[i-8]) continue;
if(board[i+1]) goto ok;
if(board[i-7]) goto ok;
if(!board[i-15]) continue;

ok:
count = 0;
for(j=1; shapes[j][0]; ++j) {
if(!test(i, j)) continue;
if(++count >= bestcount) goto next_shape; /* forget it */
}
bestcount = count, bestloc = i;
next_shape: ;
}

if(bestcount == 0) bestloc = 0;
return bestloc;
} /* findloc */

static int test(int loc, int pattern)
{
char *s, *b;
char piece;

s = shapes[pattern];
piece = *s++;
if(used[piece]) return 0;

b = board + loc;
if(b[*s++]) return 0;
if(b[*s++]) return 0;
if(b[*s++]) return 0;
if(b[*s]) return 0;
return 1;
} /* test */