1// +build ignore
2
3/*
4Redistribution and use in source and binary forms, with or without
5modification, are permitted provided that the following conditions are met:
6
7 * Redistributions of source code must retain the above copyright
8 notice, this list of conditions and the following disclaimer.
9
10 * Redistributions in binary form must reproduce the above copyright
11 notice, this list of conditions and the following disclaimer in the
12 documentation and/or other materials provided with the distribution.
13
14 * Neither the name of "The Computer Language Benchmarks Game" nor the
15 name of "The Computer Language Shootout Benchmarks" nor the names of
16 its contributors may be used to endorse or promote products derived
17 from this software without specific prior written permission.
18
19THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
23LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29POSSIBILITY OF SUCH DAMAGE.
30*/
31
32/* The Computer Language Benchmarks Game
33 * http://shootout.alioth.debian.org/
34 *
35 * contributed by Christian Vosteen
36 */
37
38#include <stdlib.h>
39#include <stdio.h>
40#define TRUE 1
41#define FALSE 0
42
43/* The board is a 50 cell hexagonal pattern. For . . . . .
44 * maximum speed the board will be implemented as . . . . .
45 * 50 bits, which will fit into a 64 bit long long . . . . .
46 * int. . . . . .
47 * . . . . .
48 * I will represent 0's as empty cells and 1's . . . . .
49 * as full cells. . . . . .
50 * . . . . .
51 * . . . . .
52 * . . . . .
53 */
54
55unsigned long long board = 0xFFFC000000000000ULL;
56
57/* The puzzle pieces must be specified by the path followed
58 * from one end to the other along 12 hexagonal directions.
59 *
60 * Piece 0 Piece 1 Piece 2 Piece 3 Piece 4
61 *
62 * O O O O O O O O O O O O O O O
63 * O O O O O O O
64 * O O O
65 *
66 * Piece 5 Piece 6 Piece 7 Piece 8 Piece 9
67 *
68 * O O O O O O O O O O O O O
69 * O O O O O O O O O
70 * O O O
71 *
72 * I had to make it 12 directions because I wanted all of the
73 * piece definitions to fit into the same size arrays. It is
74 * not possible to define piece 4 in terms of the 6 cardinal
75 * directions in 4 moves.
76 */
77
78#define E 0
79#define ESE 1
80#define SE 2
81#define S 3
82#define SW 4
83#define WSW 5
84#define W 6
85#define WNW 7
86#define NW 8
87#define N 9
88#define NE 10
89#define ENE 11
90#define PIVOT 12
91
92char piece_def[10][4] = {
93 { E, E, E, SE},
94 { SE, E, NE, E},
95 { E, E, SE, SW},
96 { E, E, SW, SE},
97 { SE, E, NE, S},
98 { E, E, SW, E},
99 { E, SE, SE, NE},
100 { E, SE, SE, W},
101 { E, SE, E, E},
102 { E, E, E, SW}
103};
104
105
106/* To minimize the amount of work done in the recursive solve function below,
107 * I'm going to allocate enough space for all legal rotations of each piece
108 * at each position on the board. That's 10 pieces x 50 board positions x
109 * 12 rotations. However, not all 12 rotations will fit on every cell, so
110 * I'll have to keep count of the actual number that do.
111 * The pieces are going to be unsigned long long ints just like the board so
112 * they can be bitwise-anded with the board to determine if they fit.
113 * I'm also going to record the next possible open cell for each piece and
114 * location to reduce the burden on the solve function.
115 */
116unsigned long long pieces[10][50][12];
117int piece_counts[10][50];
118char next_cell[10][50][12];
119
120/* Returns the direction rotated 60 degrees clockwise */
121char rotate(char dir) {
122 return (dir + 2) % PIVOT;
123}
124
125/* Returns the direction flipped on the horizontal axis */
126char flip(char dir) {
127 return (PIVOT - dir) % PIVOT;
128}
129
130
131/* Returns the new cell index from the specified cell in the
132 * specified direction. The index is only valid if the
133 * starting cell and direction have been checked by the
134 * out_of_bounds function first.
135 */
136char shift(char cell, char dir) {
137 switch(dir) {
138 case E:
139 return cell + 1;
140 case ESE:
141 if((cell / 5) % 2)
142 return cell + 7;
143 else
144 return cell + 6;
145 case SE:
146 if((cell / 5) % 2)
147 return cell + 6;
148 else
149 return cell + 5;
150 case S:
151 return cell + 10;
152 case SW:
153 if((cell / 5) % 2)
154 return cell + 5;
155 else
156 return cell + 4;
157 case WSW:
158 if((cell / 5) % 2)
159 return cell + 4;
160 else
161 return cell + 3;
162 case W:
163 return cell - 1;
164 case WNW:
165 if((cell / 5) % 2)
166 return cell - 6;
167 else
168 return cell - 7;
169 case NW:
170 if((cell / 5) % 2)
171 return cell - 5;
172 else
173 return cell - 6;
174 case N:
175 return cell - 10;
176 case NE:
177 if((cell / 5) % 2)
178 return cell - 4;
179 else
180 return cell - 5;
181 case ENE:
182 if((cell / 5) % 2)
183 return cell - 3;
184 else
185 return cell - 4;
186 default:
187 return cell;
188 }
189}
190
191/* Returns wether the specified cell and direction will land outside
192 * of the board. Used to determine if a piece is at a legal board
193 * location or not.
194 */
195char out_of_bounds(char cell, char dir) {
196 char i;
197 switch(dir) {
198 case E:
199 return cell % 5 == 4;
200 case ESE:
201 i = cell % 10;
202 return i == 4 || i == 8 || i == 9 || cell >= 45;
203 case SE:
204 return cell % 10 == 9 || cell >= 45;
205 case S:
206 return cell >= 40;
207 case SW:
208 return cell % 10 == 0 || cell >= 45;
209 case WSW:
210 i = cell % 10;
211 return i == 0 || i == 1 || i == 5 || cell >= 45;
212 case W:
213 return cell % 5 == 0;
214 case WNW:
215 i = cell % 10;
216 return i == 0 || i == 1 || i == 5 || cell < 5;
217 case NW:
218 return cell % 10 == 0 || cell < 5;
219 case N:
220 return cell < 10;
221 case NE:
222 return cell % 10 == 9 || cell < 5;
223 case ENE:
224 i = cell % 10;
225 return i == 4 || i == 8 || i == 9 || cell < 5;
226 default:
227 return FALSE;
228 }
229}
230
231/* Rotate a piece 60 degrees clockwise */
232void rotate_piece(int piece) {
233 int i;
234 for(i = 0; i < 4; i++)
235 piece_def[piece][i] = rotate(piece_def[piece][i]);
236}
237
238/* Flip a piece along the horizontal axis */
239void flip_piece(int piece) {
240 int i;
241 for(i = 0; i < 4; i++)
242 piece_def[piece][i] = flip(piece_def[piece][i]);
243}
244
245/* Convenience function to quickly calculate all of the indices for a piece */
246void calc_cell_indices(char *cell, int piece, char index) {
247 cell[0] = index;
248 cell[1] = shift(cell[0], piece_def[piece][0]);
249 cell[2] = shift(cell[1], piece_def[piece][1]);
250 cell[3] = shift(cell[2], piece_def[piece][2]);
251 cell[4] = shift(cell[3], piece_def[piece][3]);
252}
253
254/* Convenience function to quickly calculate if a piece fits on the board */
255int cells_fit_on_board(char *cell, int piece) {
256 return (!out_of_bounds(cell[0], piece_def[piece][0]) &&
257 !out_of_bounds(cell[1], piece_def[piece][1]) &&
258 !out_of_bounds(cell[2], piece_def[piece][2]) &&
259 !out_of_bounds(cell[3], piece_def[piece][3]));
260}
261
262/* Returns the lowest index of the cells of a piece.
263 * I use the lowest index that a piece occupies as the index for looking up
264 * the piece in the solve function.
265 */
266char minimum_of_cells(char *cell) {
267 char minimum = cell[0];
268 minimum = cell[1] < minimum ? cell[1] : minimum;
269 minimum = cell[2] < minimum ? cell[2] : minimum;
270 minimum = cell[3] < minimum ? cell[3] : minimum;
271 minimum = cell[4] < minimum ? cell[4] : minimum;
272 return minimum;
273}
274
275/* Calculate the lowest possible open cell if the piece is placed on the board.
276 * Used to later reduce the amount of time searching for open cells in the
277 * solve function.
278 */
279char first_empty_cell(char *cell, char minimum) {
280 char first_empty = minimum;
281 while(first_empty == cell[0] || first_empty == cell[1] ||
282 first_empty == cell[2] || first_empty == cell[3] ||
283 first_empty == cell[4])
284 first_empty++;
285 return first_empty;
286}
287
288/* Generate the unsigned long long int that will later be anded with the
289 * board to determine if it fits.
290 */
291unsigned long long bitmask_from_cells(char *cell) {
292 unsigned long long piece_mask = 0ULL;
293 int i;
294 for(i = 0; i < 5; i++)
295 piece_mask |= 1ULL << cell[i];
296 return piece_mask;
297}
298
299/* Record the piece and other important information in arrays that will
300 * later be used by the solve function.
301 */
302void record_piece(int piece, int minimum, char first_empty,
303 unsigned long long piece_mask) {
304 pieces[piece][minimum][piece_counts[piece][minimum]] = piece_mask;
305 next_cell[piece][minimum][piece_counts[piece][minimum]] = first_empty;
306 piece_counts[piece][minimum]++;
307}
308
309
310/* Fill the entire board going cell by cell. If any cells are "trapped"
311 * they will be left alone.
312 */
313void fill_contiguous_space(char *board, int index) {
314 if(board[index] == 1)
315 return;
316 board[index] = 1;
317 if(!out_of_bounds(index, E))
318 fill_contiguous_space(board, shift(index, E));
319 if(!out_of_bounds(index, SE))
320 fill_contiguous_space(board, shift(index, SE));
321 if(!out_of_bounds(index, SW))
322 fill_contiguous_space(board, shift(index, SW));
323 if(!out_of_bounds(index, W))
324 fill_contiguous_space(board, shift(index, W));
325 if(!out_of_bounds(index, NW))
326 fill_contiguous_space(board, shift(index, NW));
327 if(!out_of_bounds(index, NE))
328 fill_contiguous_space(board, shift(index, NE));
329}
330
331
332/* To thin the number of pieces, I calculate if any of them trap any empty
333 * cells at the edges. There are only a handful of exceptions where the
334 * the board can be solved with the trapped cells. For example: piece 8 can
335 * trap 5 cells in the corner, but piece 3 can fit in those cells, or piece 0
336 * can split the board in half where both halves are viable.
337 */
338int has_island(char *cell, int piece) {
339 char temp_board[50];
340 char c;
341 int i;
342 for(i = 0; i < 50; i++)
343 temp_board[i] = 0;
344 for(i = 0; i < 5; i++)
345 temp_board[((int)cell[i])] = 1;
346 i = 49;
347 while(temp_board[i] == 1)
348 i--;
349 fill_contiguous_space(temp_board, i);
350 c = 0;
351 for(i = 0; i < 50; i++)
352 if(temp_board[i] == 0)
353 c++;
354 if(c == 0 || (c == 5 && piece == 8) || (c == 40 && piece == 8) ||
355 (c % 5 == 0 && piece == 0))
356 return FALSE;
357 else
358 return TRUE;
359}
360
361
362/* Calculate all six rotations of the specified piece at the specified index.
363 * We calculate only half of piece 3's rotations. This is because any solution
364 * found has an identical solution rotated 180 degrees. Thus we can reduce the
365 * number of attempted pieces in the solve algorithm by not including the 180-
366 * degree-rotated pieces of ONE of the pieces. I chose piece 3 because it gave
367 * me the best time ;)
368 */
369 void calc_six_rotations(char piece, char index) {
370 char rotation, cell[5];
371 char minimum, first_empty;
372 unsigned long long piece_mask;
373
374 for(rotation = 0; rotation < 6; rotation++) {
375 if(piece != 3 || rotation < 3) {
376 calc_cell_indices(cell, piece, index);
377 if(cells_fit_on_board(cell, piece) && !has_island(cell, piece)) {
378 minimum = minimum_of_cells(cell);
379 first_empty = first_empty_cell(cell, minimum);
380 piece_mask = bitmask_from_cells(cell);
381 record_piece(piece, minimum, first_empty, piece_mask);
382 }
383 }
384 rotate_piece(piece);
385 }
386}
387
388/* Calculate every legal rotation for each piece at each board location. */
389void calc_pieces(void) {
390 char piece, index;
391
392 for(piece = 0; piece < 10; piece++) {
393 for(index = 0; index < 50; index++) {
394 calc_six_rotations(piece, index);
395 flip_piece(piece);
396 calc_six_rotations(piece, index);
397 }
398 }
399}
400
401
402
403/* Calculate all 32 possible states for a 5-bit row and all rows that will
404 * create islands that follow any of the 32 possible rows. These pre-
405 * calculated 5-bit rows will be used to find islands in a partially solved
406 * board in the solve function.
407 */
408#define ROW_MASK 0x1F
409#define TRIPLE_MASK 0x7FFF
410char all_rows[32] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
411 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31};
412int bad_even_rows[32][32];
413int bad_odd_rows[32][32];
414int bad_even_triple[32768];
415int bad_odd_triple[32768];
416
417int rows_bad(char row1, char row2, int even) {
418 /* even is referring to row1 */
419 int i, in_zeroes, group_okay;
420 char block, row2_shift;
421 /* Test for blockages at same index and shifted index */
422 if(even)
423 row2_shift = ((row2 << 1) & ROW_MASK) | 0x01;
424 else
425 row2_shift = (row2 >> 1) | 0x10;
426 block = ((row1 ^ row2) & row2) & ((row1 ^ row2_shift) & row2_shift);
427 /* Test for groups of 0's */
428 in_zeroes = FALSE;
429 group_okay = FALSE;
430 for(i = 0; i < 5; i++) {
431 if(row1 & (1 << i)) {
432 if(in_zeroes) {
433 if(!group_okay)
434 return TRUE;
435 in_zeroes = FALSE;
436 group_okay = FALSE;
437 }
438 } else {
439 if(!in_zeroes)
440 in_zeroes = TRUE;
441 if(!(block & (1 << i)))
442 group_okay = TRUE;
443 }
444 }
445 if(in_zeroes)
446 return !group_okay;
447 else
448 return FALSE;
449}
450
451/* Check for cases where three rows checked sequentially cause a false
452 * positive. One scenario is when 5 cells may be surrounded where piece 5
453 * or 7 can fit. The other scenario is when piece 2 creates a hook shape.
454 */
455int triple_is_okay(char row1, char row2, char row3, int even) {
456 if(even) {
457 /* There are four cases:
458 * row1: 00011 00001 11001 10101
459 * row2: 01011 00101 10001 10001
460 * row3: 011?? 00110 ????? ?????
461 */
462 return ((row1 == 0x03) && (row2 == 0x0B) && ((row3 & 0x1C) == 0x0C)) ||
463 ((row1 == 0x01) && (row2 == 0x05) && (row3 == 0x06)) ||
464 ((row1 == 0x19) && (row2 == 0x11)) ||
465 ((row1 == 0x15) && (row2 == 0x11));
466 } else {
467 /* There are two cases:
468 * row1: 10011 10101
469 * row2: 10001 10001
470 * row3: ????? ?????
471 */
472 return ((row1 == 0x13) && (row2 == 0x11)) ||
473 ((row1 == 0x15) && (row2 == 0x11));
474 }
475}
476
477
478void calc_rows(void) {
479 int row1, row2, row3;
480 int result1, result2;
481 for(row1 = 0; row1 < 32; row1++) {
482 for(row2 = 0; row2 < 32; row2++) {
483 bad_even_rows[row1][row2] = rows_bad(row1, row2, TRUE);
484 bad_odd_rows[row1][row2] = rows_bad(row1, row2, FALSE);
485 }
486 }
487 for(row1 = 0; row1 < 32; row1++) {
488 for(row2 = 0; row2 < 32; row2++) {
489 for(row3 = 0; row3 < 32; row3++) {
490 result1 = bad_even_rows[row1][row2];
491 result2 = bad_odd_rows[row2][row3];
492 if(result1 == FALSE && result2 == TRUE
493 && triple_is_okay(row1, row2, row3, TRUE))
494 bad_even_triple[row1+(row2*32)+(row3*1024)] = FALSE;
495 else
496 bad_even_triple[row1+(row2*32)+(row3*1024)] = result1 || result2;
497
498 result1 = bad_odd_rows[row1][row2];
499 result2 = bad_even_rows[row2][row3];
500 if(result1 == FALSE && result2 == TRUE
501 && triple_is_okay(row1, row2, row3, FALSE))
502 bad_odd_triple[row1+(row2*32)+(row3*1024)] = FALSE;
503 else
504 bad_odd_triple[row1+(row2*32)+(row3*1024)] = result1 || result2;
505 }
506 }
507 }
508}
509
510
511
512/* Calculate islands while solving the board.
513 */
514int boardHasIslands(char cell) {
515 /* Too low on board, don't bother checking */
516 if(cell >= 40)
517 return FALSE;
518 int current_triple = (board >> ((cell / 5) * 5)) & TRIPLE_MASK;
519 if((cell / 5) % 2)
520 return bad_odd_triple[current_triple];
521 else
522 return bad_even_triple[current_triple];
523}
524
525
526/* The recursive solve algorithm. Try to place each permutation in the upper-
527 * leftmost empty cell. Mark off available pieces as it goes along.
528 * Because the board is a bit mask, the piece number and bit mask must be saved
529 * at each successful piece placement. This data is used to create a 50 char
530 * array if a solution is found.
531 */
532short avail = 0x03FF;
533char sol_nums[10];
534unsigned long long sol_masks[10];
535signed char solutions[2100][50];
536int solution_count = 0;
537int max_solutions = 2100;
538
539void record_solution(void) {
540 int sol_no, index;
541 unsigned long long sol_mask;
542 for(sol_no = 0; sol_no < 10; sol_no++) {
543 sol_mask = sol_masks[sol_no];
544 for(index = 0; index < 50; index++) {
545 if(sol_mask & 1ULL) {
546 solutions[solution_count][index] = sol_nums[sol_no];
547 /* Board rotated 180 degrees is a solution too! */
548 solutions[solution_count+1][49-index] = sol_nums[sol_no];
549 }
550 sol_mask = sol_mask >> 1;
551 }
552 }
553 solution_count += 2;
554}
555
556void solve(int depth, int cell) {
557 int piece, rotation, max_rots;
558 unsigned long long *piece_mask;
559 short piece_no_mask;
560
561 if(solution_count >= max_solutions)
562 return;
563
564 while(board & (1ULL << cell))
565 cell++;
566
567 for(piece = 0; piece < 10; piece++) {
568 piece_no_mask = 1 << piece;
569 if(!(avail & piece_no_mask))
570 continue;
571 avail ^= piece_no_mask;
572 max_rots = piece_counts[piece][cell];
573 piece_mask = pieces[piece][cell];
574 for(rotation = 0; rotation < max_rots; rotation++) {
575 if(!(board & *(piece_mask + rotation))) {
576 sol_nums[depth] = piece;
577 sol_masks[depth] = *(piece_mask + rotation);
578 if(depth == 9) {
579 /* Solution found!!!!!11!!ONE! */
580 record_solution();
581 avail ^= piece_no_mask;
582 return;
583 }
584 board |= *(piece_mask + rotation);
585 if(!boardHasIslands(next_cell[piece][cell][rotation]))
586 solve(depth + 1, next_cell[piece][cell][rotation]);
587 board ^= *(piece_mask + rotation);
588 }
589 }
590 avail ^= piece_no_mask;
591 }
592}
593
594
595/* qsort comparator - used to find first and last solutions */
596int solution_sort(const void *elem1, const void *elem2) {
597 signed char *char1 = (signed char *) elem1;
598 signed char *char2 = (signed char *) elem2;
599 int i = 0;
600 while(i < 50 && char1[i] == char2[i])
601 i++;
602 return char1[i] - char2[i];
603}
604
605
606/* pretty print a board in the specified hexagonal format */
607void pretty(signed char *b) {
608 int i;
609 for(i = 0; i < 50; i += 10) {
610 printf("%c %c %c %c %c \n %c %c %c %c %c \n", b[i]+'0', b[i+1]+'0',
611 b[i+2]+'0', b[i+3]+'0', b[i+4]+'0', b[i+5]+'0', b[i+6]+'0',
612 b[i+7]+'0', b[i+8]+'0', b[i+9]+'0');
613 }
614 printf("\n");
615}
616
617int main(int argc, char **argv) {
618 if(argc > 1)
619 max_solutions = atoi(argv[1]);
620 calc_pieces();
621 calc_rows();
622 solve(0, 0);
623 printf("%d solutions found\n\n", solution_count);
624 qsort(solutions, solution_count, 50 * sizeof(signed char), solution_sort);
625 pretty(solutions[0]);
626 pretty(solutions[solution_count-1]);
627 return 0;
628}
View as plain text