#include #include #include int solve(char pieces[9][7], char *puzzle[9], char used[9], int sequence, int number_of_solutions); int check_puzzle(char *puzzle[9]); void debug_print_puzzle(char *puzzle[9]); int main() { #ifdef TARGET_RT_MAC_CFM FILE *stream = fopen("input", "r"); #else FILE *stream = stdin; #endif int number_of_puzzles; fscanf(stream, "%d", &number_of_puzzles); while (number_of_puzzles-- > 0) { int index, index2; char chr, pieces[9][7], used[9] = { 0 }, *puzzle[9] = { NULL }; for (index = 0; index < 9; index++) { for (index2 = 0; index2 < 4; index2++) { while (isspace(chr = fgetc(stream))) ; pieces[index][index2] = chr; } memcpy(&pieces[index][4], &pieces[index][0], 3); } printf("%d\n", solve(pieces, puzzle, used, 0, 0)); } return 0; } int solve(char pieces[9][7], char *puzzle[9], char used[9], int sequence, int number_of_solutions) { static int place_sequence[] = { 4, 1, 5, 2, 7, 8, 3, 6, 0 }; int piece, direction; if (sequence >= 9) return number_of_solutions + 1; for (piece = 0; piece < 9; piece++) { if (used[piece]) continue; used[piece] = 1; for (direction = 0; direction < 4; direction++) { puzzle[place_sequence[sequence]] = &pieces[piece][direction]; if (check_puzzle(puzzle)) number_of_solutions = solve(pieces, puzzle, used, sequence + 1, number_of_solutions); puzzle[place_sequence[sequence]] = NULL; } used[piece] = 0; } return number_of_solutions; } int check_puzzle(char *puzzle[9]) { // debug_print_puzzle(puzzle); #define generate_one_check(piece1, direction1, piece2, direction2) \ if (puzzle[piece1] && puzzle[piece2]) { \ char chr1 = puzzle[piece1][direction1], chr2 = puzzle[piece2][direction2]; \ if (chr1 == chr2 || (chr1 != toupper(chr2) && chr1 != tolower(chr2))) \ return 0; \ } generate_one_check(0, 1, 1, 3); generate_one_check(0, 2, 3, 0); generate_one_check(1, 1, 2, 3); generate_one_check(1, 2, 4, 0); generate_one_check(2, 2, 5, 0); generate_one_check(3, 1, 4, 3); generate_one_check(3, 2, 6, 0); generate_one_check(4, 1, 5, 3); generate_one_check(4, 2, 7, 0); generate_one_check(5, 2, 8, 0); generate_one_check(6, 1, 7, 3); generate_one_check(7, 1, 8, 3); return 1; #undef generate_one_check } void debug_print_puzzle(char *puzzle[9]) { int index; for (index = 0; index < 9; index++) printf("[%.4s] ", (puzzle[index] ? puzzle[index] : "----")); printf("\n"); }