source code
/* The Computer Language Benchmarks Game
* http://benchmarksgame.alioth.debian.org/
*
* contributed by Christian Vosteen
*/
#include <stdlib.h>
#include <stdio.h>
#define TRUE 1
#define FALSE 0
/* The board is a 50 cell hexagonal pattern. For . . . . .
* maximum speed the board will be implemented as . . . . .
* 50 bits, which will fit into a 64 bit long long . . . . .
* int. . . . . .
* . . . . .
* I will represent 0's as empty cells and 1's . . . . .
* as full cells. . . . . .
* . . . . .
* . . . . .
* . . . . .
*/
unsigned long long board = 0xFFFC000000000000ULL;
/* The puzzle pieces must be specified by the path followed
* from one end to the other along 12 hexagonal directions.
*
* Piece 0 Piece 1 Piece 2 Piece 3 Piece 4
*
* O O O O O O O O O O O O O O O
* O O O O O O O
* O O O
*
* Piece 5 Piece 6 Piece 7 Piece 8 Piece 9
*
* O O O O O O O O O O O O O
* O O O O O O O O O
* O O O
*
* I had to make it 12 directions because I wanted all of the
* piece definitions to fit into the same size arrays. It is
* not possible to define piece 4 in terms of the 6 cardinal
* directions in 4 moves.
*/
#define E 0
#define ESE 1
#define SE 2
#define S 3
#define SW 4
#define WSW 5
#define W 6
#define WNW 7
#define NW 8
#define N 9
#define NE 10
#define ENE 11
#define PIVOT 12
char piece_def[10][4] = {
{ E, E, E, SE},
{ SE, E, NE, E},
{ E, E, SE, SW},
{ E, E, SW, SE},
{ SE, E, NE, S},
{ E, E, SW, E},
{ E, SE, SE, NE},
{ E, SE, SE, W},
{ E, SE, E, E},
{ E, E, E, SW}
};
/* To minimize the amount of work done in the recursive solve function below,
* I'm going to allocate enough space for all legal rotations of each piece
* at each position on the board. That's 10 pieces x 50 board positions x
* 12 rotations. However, not all 12 rotations will fit on every cell, so
* I'll have to keep count of the actual number that do.
* The pieces are going to be unsigned long long ints just like the board so
* they can be bitwise-anded with the board to determine if they fit.
* I'm also going to record the next possible open cell for each piece and
* location to reduce the burden on the solve function.
*/
unsigned long long pieces[10][50][12];
int piece_counts[10][50];
char next_cell[10][50][12];
/* Returns the direction rotated 60 degrees clockwise */
char rotate(char dir) {
return (dir + 2) % PIVOT;
}
/* Returns the direction flipped on the horizontal axis */
char flip(char dir) {
return (PIVOT - dir) % PIVOT;
}
/* Returns the new cell index from the specified cell in the
* specified direction. The index is only valid if the
* starting cell and direction have been checked by the
* out_of_bounds function first.
*/
char shift(char cell, char dir) {
switch(dir) {
case E:
return cell + 1;
case ESE:
if((cell / 5) % 2)
return cell + 7;
else
return cell + 6;
case SE:
if((cell / 5) % 2)
return cell + 6;
else
return cell + 5;
case S:
return cell + 10;
case SW:
if((cell / 5) % 2)
return cell + 5;
else
return cell + 4;
case WSW:
if((cell / 5) % 2)
return cell + 4;
else
return cell + 3;
case W:
return cell - 1;
case WNW:
if((cell / 5) % 2)
return cell - 6;
else
return cell - 7;
case NW:
if((cell / 5) % 2)
return cell - 5;
else
return cell - 6;
case N:
return cell - 10;
case NE:
if((cell / 5) % 2)
return cell - 4;
else
return cell - 5;
case ENE:
if((cell / 5) % 2)
return cell - 3;
else
return cell - 4;
default:
return cell;
}
}
/* Returns wether the specified cell and direction will land outside
* of the board. Used to determine if a piece is at a legal board
* location or not.
*/
char out_of_bounds(char cell, char dir) {
char i;
switch(dir) {
case E:
return cell % 5 == 4;
case ESE:
i = cell % 10;
return i == 4 || i == 8 || i == 9 || cell >= 45;
case SE:
return cell % 10 == 9 || cell >= 45;
case S:
return cell >= 40;
case SW:
return cell % 10 == 0 || cell >= 45;
case WSW:
i = cell % 10;
return i == 0 || i == 1 || i == 5 || cell >= 45;
case W:
return cell % 5 == 0;
case WNW:
i = cell % 10;
return i == 0 || i == 1 || i == 5 || cell < 5;
case NW:
return cell % 10 == 0 || cell < 5;
case N:
return cell < 10;
case NE:
return cell % 10 == 9 || cell < 5;
case ENE:
i = cell % 10;
return i == 4 || i == 8 || i == 9 || cell < 5;
default:
return FALSE;
}
}
/* Rotate a piece 60 degrees clockwise */
void rotate_piece(int piece) {
int i;
for(i = 0; i < 4; i++)
piece_def[piece][i] = rotate(piece_def[piece][i]);
}
/* Flip a piece along the horizontal axis */
void flip_piece(int piece) {
int i;
for(i = 0; i < 4; i++)
piece_def[piece][i] = flip(piece_def[piece][i]);
}
/* Convenience function to quickly calculate all of the indices for a piece */
void calc_cell_indices(char *cell, int piece, char index) {
cell[0] = index;
cell[1] = shift(cell[0], piece_def[piece][0]);
cell[2] = shift(cell[1], piece_def[piece][1]);
cell[3] = shift(cell[2], piece_def[piece][2]);
cell[4] = shift(cell[3], piece_def[piece][3]);
}
/* Convenience function to quickly calculate if a piece fits on the board */
int cells_fit_on_board(char *cell, int piece) {
return (!out_of_bounds(cell[0], piece_def[piece][0]) &&
!out_of_bounds(cell[1], piece_def[piece][1]) &&
!out_of_bounds(cell[2], piece_def[piece][2]) &&
!out_of_bounds(cell[3], piece_def[piece][3]));
}
/* Returns the lowest index of the cells of a piece.
* I use the lowest index that a piece occupies as the index for looking up
* the piece in the solve function.
*/
char minimum_of_cells(char *cell) {
char minimum = cell[0];
minimum = cell[1] < minimum ? cell[1] : minimum;
minimum = cell[2] < minimum ? cell[2] : minimum;
minimum = cell[3] < minimum ? cell[3] : minimum;
minimum = cell[4] < minimum ? cell[4] : minimum;
return minimum;
}
/* Calculate the lowest possible open cell if the piece is placed on the board.
* Used to later reduce the amount of time searching for open cells in the
* solve function.
*/
char first_empty_cell(char *cell, char minimum) {
char first_empty = minimum;
while(first_empty == cell[0] || first_empty == cell[1] ||
first_empty == cell[2] || first_empty == cell[3] ||
first_empty == cell[4])
first_empty++;
return first_empty;
}
/* Generate the unsigned long long int that will later be anded with the
* board to determine if it fits.
*/
unsigned long long bitmask_from_cells(char *cell) {
unsigned long long piece_mask = 0ULL;
int i;
for(i = 0; i < 5; i++)
piece_mask |= 1ULL << cell[i];
return piece_mask;
}
/* Record the piece and other important information in arrays that will
* later be used by the solve function.
*/
void record_piece(int piece, int minimum, char first_empty,
unsigned long long piece_mask) {
pieces[piece][minimum][piece_counts[piece][minimum]] = piece_mask;
next_cell[piece][minimum][piece_counts[piece][minimum]] = first_empty;
piece_counts[piece][minimum]++;
}
/* Fill the entire board going cell by cell. If any cells are "trapped"
* they will be left alone.
*/
void fill_contiguous_space(char *board, int index) {
if(board[index] == 1)
return;
board[index] = 1;
if(!out_of_bounds(index, E))
fill_contiguous_space(board, shift(index, E));
if(!out_of_bounds(index, SE))
fill_contiguous_space(board, shift(index, SE));
if(!out_of_bounds(index, SW))
fill_contiguous_space(board, shift(index, SW));
if(!out_of_bounds(index, W))
fill_contiguous_space(board, shift(index, W));
if(!out_of_bounds(index, NW))
fill_contiguous_space(board, shift(index, NW));
if(!out_of_bounds(index, NE))
fill_contiguous_space(board, shift(index, NE));
}
/* To thin the number of pieces, I calculate if any of them trap any empty
* cells at the edges. There are only a handful of exceptions where the
* the board can be solved with the trapped cells. For example: piece 8 can
* trap 5 cells in the corner, but piece 3 can fit in those cells, or piece 0
* can split the board in half where both halves are viable.
*/
int has_island(char *cell, int piece) {
char temp_board[50];
char c;
int i;
for(i = 0; i < 50; i++)
temp_board[i] = 0;
for(i = 0; i < 5; i++)
temp_board[((int)cell[i])] = 1;
i = 49;
while(temp_board[i] == 1)
i--;
fill_contiguous_space(temp_board, i);
c = 0;
for(i = 0; i < 50; i++)
if(temp_board[i] == 0)
c++;
if(c == 0 || (c == 5 && piece == 8) || (c == 40 && piece == 8) ||
(c % 5 == 0 && piece == 0))
return FALSE;
else
return TRUE;
}
/* Calculate all six rotations of the specified piece at the specified index.
* We calculate only half of piece 3's rotations. This is because any solution
* found has an identical solution rotated 180 degrees. Thus we can reduce the
* number of attempted pieces in the solve algorithm by not including the 180-
* degree-rotated pieces of ONE of the pieces. I chose piece 3 because it gave
* me the best time ;)
*/
void calc_six_rotations(char piece, char index) {
char rotation, cell[5];
char minimum, first_empty;
unsigned long long piece_mask;
for(rotation = 0; rotation < 6; rotation++) {
if(piece != 3 || rotation < 3) {
calc_cell_indices(cell, piece, index);
if(cells_fit_on_board(cell, piece) && !has_island(cell, piece)) {
minimum = minimum_of_cells(cell);
first_empty = first_empty_cell(cell, minimum);
piece_mask = bitmask_from_cells(cell);
record_piece(piece, minimum, first_empty, piece_mask);
}
}
rotate_piece(piece);
}
}
/* Calculate every legal rotation for each piece at each board location. */
void calc_pieces(void) {
char piece, index;
for(piece = 0; piece < 10; piece++) {
for(index = 0; index < 50; index++) {
calc_six_rotations(piece, index);
flip_piece(piece);
calc_six_rotations(piece, index);
}
}
}
/* Calculate all 32 possible states for a 5-bit row and all rows that will
* create islands that follow any of the 32 possible rows. These pre-
* calculated 5-bit rows will be used to find islands in a partially solved
* board in the solve function.
*/
#define ROW_MASK 0x1F
#define TRIPLE_MASK 0x7FFF
char all_rows[32] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31};
int bad_even_rows[32][32];
int bad_odd_rows[32][32];
int bad_even_triple[32768];
int bad_odd_triple[32768];
int rows_bad(char row1, char row2, int even) {
/* even is referring to row1 */
int i, in_zeroes, group_okay;
char block, row2_shift;
/* Test for blockages at same index and shifted index */
if(even)
row2_shift = ((row2 << 1) & ROW_MASK) | 0x01;
else
row2_shift = (row2 >> 1) | 0x10;
block = ((row1 ^ row2) & row2) & ((row1 ^ row2_shift) & row2_shift);
/* Test for groups of 0's */
in_zeroes = FALSE;
group_okay = FALSE;
for(i = 0; i < 5; i++) {
if(row1 & (1 << i)) {
if(in_zeroes) {
if(!group_okay)
return TRUE;
in_zeroes = FALSE;
group_okay = FALSE;
}
} else {
if(!in_zeroes)
in_zeroes = TRUE;
if(!(block & (1 << i)))
group_okay = TRUE;
}
}
if(in_zeroes)
return !group_okay;
else
return FALSE;
}
/* Check for cases where three rows checked sequentially cause a false
* positive. One scenario is when 5 cells may be surrounded where piece 5
* or 7 can fit. The other scenario is when piece 2 creates a hook shape.
*/
int triple_is_okay(char row1, char row2, char row3, int even) {
if(even) {
/* There are four cases:
* row1: 00011 00001 11001 10101
* row2: 01011 00101 10001 10001
* row3: 011?? 00110 ????? ?????
*/
return ((row1 == 0x03) && (row2 == 0x0B) && ((row3 & 0x1C) == 0x0C)) ||
((row1 == 0x01) && (row2 == 0x05) && (row3 == 0x06)) ||
((row1 == 0x19) && (row2 == 0x11)) ||
((row1 == 0x15) && (row2 == 0x11));
} else {
/* There are two cases:
* row1: 10011 10101
* row2: 10001 10001
* row3: ????? ?????
*/
return ((row1 == 0x13) && (row2 == 0x11)) ||
((row1 == 0x15) && (row2 == 0x11));
}
}
void calc_rows(void) {
int row1, row2, row3;
int result1, result2;
for(row1 = 0; row1 < 32; row1++) {
for(row2 = 0; row2 < 32; row2++) {
bad_even_rows[row1][row2] = rows_bad(row1, row2, TRUE);
bad_odd_rows[row1][row2] = rows_bad(row1, row2, FALSE);
}
}
for(row1 = 0; row1 < 32; row1++) {
for(row2 = 0; row2 < 32; row2++) {
for(row3 = 0; row3 < 32; row3++) {
result1 = bad_even_rows[row1][row2];
result2 = bad_odd_rows[row2][row3];
if(result1 == FALSE && result2 == TRUE
&& triple_is_okay(row1, row2, row3, TRUE))
bad_even_triple[row1+(row2*32)+(row3*1024)] = FALSE;
else
bad_even_triple[row1+(row2*32)+(row3*1024)] = result1 || result2;
result1 = bad_odd_rows[row1][row2];
result2 = bad_even_rows[row2][row3];
if(result1 == FALSE && result2 == TRUE
&& triple_is_okay(row1, row2, row3, FALSE))
bad_odd_triple[row1+(row2*32)+(row3*1024)] = FALSE;
else
bad_odd_triple[row1+(row2*32)+(row3*1024)] = result1 || result2;
}
}
}
}
/* Calculate islands while solving the board.
*/
int boardHasIslands(char cell) {
/* Too low on board, don't bother checking */
if(cell >= 40)
return FALSE;
int current_triple = (board >> ((cell / 5) * 5)) & TRIPLE_MASK;
if((cell / 5) % 2)
return bad_odd_triple[current_triple];
else
return bad_even_triple[current_triple];
}
/* The recursive solve algorithm. Try to place each permutation in the upper-
* leftmost empty cell. Mark off available pieces as it goes along.
* Because the board is a bit mask, the piece number and bit mask must be saved
* at each successful piece placement. This data is used to create a 50 char
* array if a solution is found.
*/
short avail = 0x03FF;
char sol_nums[10];
unsigned long long sol_masks[10];
signed char solutions[2100][50];
int solution_count = 0;
int max_solutions = 2100;
void record_solution(void) {
int sol_no, index;
unsigned long long sol_mask;
for(sol_no = 0; sol_no < 10; sol_no++) {
sol_mask = sol_masks[sol_no];
for(index = 0; index < 50; index++) {
if(sol_mask & 1ULL) {
solutions[solution_count][index] = sol_nums[sol_no];
/* Board rotated 180 degrees is a solution too! */
solutions[solution_count+1][49-index] = sol_nums[sol_no];
}
sol_mask = sol_mask >> 1;
}
}
solution_count += 2;
}
void solve(int depth, int cell) {
int piece, rotation, max_rots;
unsigned long long *piece_mask;
short piece_no_mask;
if(solution_count >= max_solutions)
return;
while(board & (1ULL << cell))
cell++;
for(piece = 0; piece < 10; piece++) {
piece_no_mask = 1 << piece;
if(!(avail & piece_no_mask))
continue;
avail ^= piece_no_mask;
max_rots = piece_counts[piece][cell];
piece_mask = pieces[piece][cell];
for(rotation = 0; rotation < max_rots; rotation++) {
if(!(board & *(piece_mask + rotation))) {
sol_nums[depth] = piece;
sol_masks[depth] = *(piece_mask + rotation);
if(depth == 9) {
/* Solution found!!!!!11!!ONE! */
record_solution();
avail ^= piece_no_mask;
return;
}
board |= *(piece_mask + rotation);
if(!boardHasIslands(next_cell[piece][cell][rotation]))
solve(depth + 1, next_cell[piece][cell][rotation]);
board ^= *(piece_mask + rotation);
}
}
avail ^= piece_no_mask;
}
}
/* qsort comparator - used to find first and last solutions */
int solution_sort(const void *elem1, const void *elem2) {
signed char *char1 = (signed char *) elem1;
signed char *char2 = (signed char *) elem2;
int i = 0;
while(i < 50 && char1[i] == char2[i])
i++;
return char1[i] - char2[i];
}
/* pretty print a board in the specified hexagonal format */
void pretty(signed char *b) {
int i;
for(i = 0; i < 50; i += 10) {
printf("%c %c %c %c %c \n %c %c %c %c %c \n", b[i]+'0', b[i+1]+'0',
b[i+2]+'0', b[i+3]+'0', b[i+4]+'0', b[i+5]+'0', b[i+6]+'0',
b[i+7]+'0', b[i+8]+'0', b[i+9]+'0');
}
printf("\n");
}
int main(int argc, char **argv) {
if(argc > 1)
max_solutions = atoi(argv[1]);
calc_pieces();
calc_rows();
solve(0, 0);
printf("%d solutions found\n\n", solution_count);
qsort(solutions, solution_count, 50 * sizeof(signed char), solution_sort);
pretty(solutions[0]);
pretty(solutions[solution_count-1]);
return 0;
}