/* * Copyright (c) 2005 by Stan Chesnutt. All rights reserved. */ #include #include #include #include #define SIZE_PIECE_ARRAY (12 * 8) typedef unsigned long long uint64; static int offsets[SIZE_PIECE_ARRAY]; static uint64 shifted_pieces[SIZE_PIECE_ARRAY]; static int piece_placed[12]; static int placed_piece_orient[12]; static char * board_str = " |" " |" " |X"; static char * piece_codes = "XIVTUSWPLRYZ"; static int board_limit[12] = { // 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60 /* X I V T U S W P L R Y Z */ 20, 57, 20, 20, 38, 20, 20, 39, 40, 20, 39, 39 }; static char * pieces[SIZE_PIECE_ARRAY] = { " X " "XXX " " X ", NULL, NULL, NULL, NULL, NULL, NULL, NULL, "IIIII " " " " ", NULL, NULL, NULL, NULL, NULL, NULL, NULL, "VVV " "V " "V ", "VVV " " V " " V ", "V " "V " "VVV ", " V " " V " "VVV ", NULL, NULL, NULL, NULL, "TTT " " T " " T ", "T " "TTT " "T ", " T " " T " "TTT ", " T " "TTT " " T ", NULL, NULL, NULL, NULL, "U U " "UUU " " ", "UU " "U " "UU ", "UUU " "U U " " ", "UU " " U " "UU ", NULL, NULL, NULL, NULL, "SS " " S " " SS ", " SS " " S " "SS ", " S " "SSS " "S ", "S " "SSS " " S ", NULL, NULL, NULL, NULL, "W " "WW " " WW ", " W " " WW " "WW ", "WW " " WW " " W ", " WW " "WW " "W ", NULL, NULL, NULL, NULL, "PP " "PP " "P ", "PP " "PP " " P ", "PPP " "PP " " ", "PPP " " PP " " ", "P " "PP " "PP ", " P " "PP " "PP ", "PP " "PPP " " ", " PP " "PPP " " ", "LLLL " " L " " ", "LLLL " "L " " ", "L " "LLLL " " ", " L " "LLLL " " ", NULL, NULL, NULL, NULL, " R " "RRR " " R ", " R " "RRR " "R ", "RR " " RR " " R ", " RR " "RR " " R ", " R " "RRR " " R ", "R " "RRR " " R ", " R " "RR " " RR ", " R " " RR " "RR ", "YYYY " " Y " " ", "YYYY " " Y " " ", " Y " "YYYY " " ", " Y " "YYYY " " ", NULL, NULL, NULL, NULL, "ZZZ " " ZZ " " ", " ZZZ " "ZZ " " ", "ZZ " " ZZZ " " ", " ZZ " "ZZZ " " ", NULL, NULL, NULL, NULL }; /* * Compute the offset of the piece. The offset is the number of * shift operations necessary to place the first occupied square * at the beginning of the mask word */ static int compute_offset (const char * piece) { int result = 0; if (piece != NULL) { while (piece[result] == ' ') result = result + 1; } return(result); } static void display_board(void) { int i; char display[64]; for (i = 0; i < 64; i++) display[i] = ' '; for (i = 0; i < 12; i++) { int offset = piece_placed[i]; if (offset != -1) { int orient = placed_piece_orient[i]; uint64 shifted_piece = shifted_pieces[i * 8 + orient] << offset; int j; for (j = 0; j < 3; j++) { int k; for (k = 0; k < 21; k++) { if ((shifted_piece & 1) != 0) display[j * 21 + k] = piece_codes[i]; shifted_piece = shifted_piece >> 1; } } } } for (i = 0; i < 3; i++) { int j; for (j = 0; j < 20; j++) { putchar(display[i * 21 + j]); } putchar('\n'); } putchar('\n'); } /* static */ void display_piece (const int offset, const uint64 shifted_piece, const char ch) { uint64 piece = shifted_piece << offset; int i, j; for (i = 0; i < 3; i++) { for (j = 0; j < 21; j++) { if ((piece & 1) == 1) putchar(ch); else putchar('.'); piece = piece >> 1; } putchar('\n'); } putchar('\n'); } static uint64 compute_shifted_piece (const int offset, const char *piece) { uint64 result = (uint64) 0; uint64 mask = (uint64) 1; int i = offset; if (piece == NULL) return((uint64) -1); while (piece[i] != '\0') { if (piece[i] != ' ') result = result | mask; mask = mask << 1; i++; } return(result); } static void emplace (uint64 board, int count, int offset) { int i; /* * If we've already placed all pieces, then no need to do any work */ if (count == 12) { display_board(); return; } /* * Find next unoccupied spot */ while (((((uint64) 1) << offset) & board) != 0) { offset++; assert(offset != 63); } for (i = 0; i < 12; i++) { if (piece_placed[i] == -1) { /* * Iterate through all 8 potential orientations */ int j; /* * Early escape: if there's no way this piece can fit, * then it isn't worth trying it, and there's also no way * that it will fit after other pieces have been added. * So, stop this step immediately. */ if (offset > board_limit[i]) return; for (j = 0; j < 8; j++) { uint64 piece = shifted_pieces[i * 8 + j]; uint64 shifted_piece = piece << offset; /* * See if the piece has retained its integrity This * value should be zero if the piece hasn't been * shifted off the other side */ uint64 test1 = (shifted_piece >> offset) ^ piece; uint64 masked_board = board | shifted_piece; /* * See if placing this piece of this board impacts * squares that have already been filled. The result * should be zero. */ uint64 test2 = (masked_board ^ shifted_piece) ^ board; if ((test2 | test1) == (uint64) 0) { /* * The piece was successfully placed */ piece_placed[i] = offset; placed_piece_orient[i] = j; emplace(masked_board, count + 1, offset); piece_placed[i] = -1; } } } } } int main(int argc, char * argv[]) { int i; for (i = 0; i < SIZE_PIECE_ARRAY; i++) { char * piece = pieces[i]; if (piece != NULL) assert(strlen(piece) == 63); offsets[i] = compute_offset(piece); shifted_pieces[i] = compute_shifted_piece(offsets[i], piece); } for (i = 0; i < 12; i++) piece_placed[i] = -1; emplace(compute_shifted_piece(0, board_str), 0, 0); exit(0); }