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