#ident "$Id: sudoku.c,v 1.15 2008/03/25 17:41:55 pwh Exp $" /* * Sudoku Puzzle Solver. */ #include #include #include #include #include #include #include #include /* Use the ncurses library. */ #define PUZZLE_TITLE "Sudoku Solver" /* Useful character definitions. */ #define ESC 27 /* Escape character. */ #define HT 0x09 /* Horizontal tab. */ #define CR 0x0D /* Carriage return. */ #define DEL 0x7F /* Delete. */ /* Flag bits. */ #define BIG 0x1 #define DISPLAYED 0x2 /* Technique flags. */ #define NAKED_TUPLE_LEVEL 0xF #define HIDDEN_TUPLE_LEVEL 0xF0 #define CROSS_HATCH 0x100 #define CROSS_HATCH_2 0x200 #define MISSING_DIGIT 0x400 #define NAKED_TUPLE 0x800 #define HIDDEN_TUPLE 0x1000 #define SET_INTERSECTION 0x2000 #define WHAT_IF 0x4000 #define SET_NAKED_TUPLE_LEVEL(a,b) ((a)=((a)&~NAKED_TUPLE_LEVEL)|(b)) #define GET_NAKED_TUPLE_LEVEL(a) ((a)&NAKED_TUPLE_LEVEL) #define SET_HIDDEN_TUPLE_LEVEL(a,b) ((a)=((a)&~HIDDEN_TUPLE_LEVEL)|((b)<<4)) #define GET_HIDDEN_TUPLE_LEVEL(a) (((a)&HIDDEN_TUPLE_LEVEL)>>4) /* Test flag bits. */ #define isBig(a) ((a)->flags&BIG) #define isDisplayed(a) ((a)->flags&DISPLAYED) /* * Sudoku puzzle object. */ typedef struct { int y0; /* Upper left hand corner of game board. */ int x0; /* Upper left hand corner of game board. */ int flags; /* Puzzle big, displayed. */ int delay; int difficulty; int technique; char board [9][9]; short masks [9][9]; short rowMasks [9]; short columnMasks [9]; short blockMasks [3][3]; } PUZZLE; /* Puzzle solution function. */ static int solvePuzzle ( PUZZLE *puzzle ); static const char gameName[] = PUZZLE_TITLE; static const char instructions1[] = "Enter clues"; static const char instructions2[] = "'s' = solve"; static const char quit[] = "Quit (Y/N)? "; static const char thinking[] = "Thinking..."; static const char paused[] = "Paused..."; static const char stumped[] = "?Ambiguous?"; static const char noSolution[] = "No Solution!"; static const char solved[] = "Ta Daaaa!!!"; #define BIT_MASK 0x1FF #define SQUARE_1 0x1C0 #define SQUARE_2 0x038 #define SQUARE_3 0x007 #define ROW_1 SQUARE_1 #define ROW_2 SQUARE_2 #define ROW_3 SQUARE_3 #define COLUMN_1 0x124 #define COLUMN_2 0x092 #define COLUMN_3 0x049 static int digit2bit_array [32] = { 0x0001, 0x0002, 0x0004, 0x0008, 0x0010, 0x0020, 0x0040, 0x0080, 0x0100, 0x0200, 0x0400, 0x0800, 0x1000, 0x2000, 0x4000, 0x8000, 0x00010000, 0x00020000, 0x00040000, 0x00080000, 0x00100000, 0x00200000, 0x00400000, 0x00800000, 0x01000000, 0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000, 0x40000000, 0x80000000 }; static int digit2bit ( int digit ) { int bit = 0; if ( digit < 33 && digit > 0 ) bit = digit2bit_array [digit-1]; return ( bit ); } static int bit2digit ( int bit ) { int digit = 0; if ( bit & 0xFFFF0000 ) { /* 0xFFFF0000 */ if ( bit & 0xFF000000 ) { /* 0xFF000000 */ if ( bit & 0xF0000000 ) { /* 0xF0000000 */ if ( bit & 0xC0000000 ) { /* 0xC0000000 */ if ( bit == 0x80000000 ) /* 0x80000000 */ digit = 32; else if ( bit == 0x40000000 ) /* 0x40000000 */ digit = 31; } else if ( bit == 0x20000000 ) /* 0x20000000 */ digit = 30; else if ( bit == 0x10000000 ) /* 0x10000000 */ digit = 29; } else if ( bit & 0x0C000000 ) { /* 0x0C000000 */ if ( bit == 0x08000000 ) /* 0x08000000 */ digit = 28; else if ( bit == 0x04000000 ) /* 0x04000000 */ digit = 27; } else if ( bit == 0x02000000 ) /* 0x02000000 */ digit = 26; else if ( bit == 0x01000000 ) /* 0x01000000 */ digit = 25; } else if ( bit & 0x00F00000 ) { /* 0x00F00000 */ if ( bit & 0x00C00000 ) { /* 0x00C00000 */ if ( bit == 0x00800000 ) /* 0x00800000 */ digit = 24; else if ( bit == 0x00400000 ) /* 0x00400000 */ digit = 23; } else if ( bit == 0x00200000 ) /* 0x00200000 */ digit = 22; else if ( bit == 0x00100000 ) /* 0x00100000 */ digit = 21; } else if ( bit & 0x000C0000 ) { /* 0x000C0000 */ if ( bit == 0x00080000 ) /* 0x00080000 */ digit = 20; else if ( bit == 0x00040000 ) /* 0x00040000 */ digit = 19; } else if ( bit == 0x00020000 ) /* 0x00020000 */ digit = 18; else if ( bit == 0x00010000 ) /* 0x00010000 */ digit = 17; } else if ( bit & 0x0000FF00 ) { /* 0x0000FF00 */ if ( bit & 0x0000F000 ) { /* 0x0000F000 */ if ( bit & 0x0000C000 ) { /* 0x0000C000 */ if ( bit == 0x00008000 ) /* 0x00008000 */ digit = 16; else if ( bit == 0x00004000 ) /* 0x00004000 */ digit = 15; } else if ( bit == 0x00002000 ) /* 0x00002000 */ digit = 14; else if ( bit == 0x00001000 ) /* 0x00001000 */ digit = 13; } else if ( bit & 0x00000C00 ) { /* 0x00000C00 */ if ( bit == 0x00000800 ) /* 0x00000800 */ digit = 12; else if ( bit == 0x00000400 ) /* 0x00000400 */ digit = 11; } else if ( bit == 0x00000200 ) /* 0x00000200 */ digit = 10; else if ( bit == 0x00000100 ) /* 0x00000100 */ digit = 9; } else if ( bit & 0x000000F0 ) { /* 0x000000F0 */ if ( bit & 0x000000C0 ) { /* 0x000000C0 */ if ( bit == 0x00000080 ) /* 0x00000080 */ digit = 8; else if ( bit == 0x00000040 ) /* 0x00000040 */ digit = 7; } else if ( bit == 0x00000020 ) /* 0x00000020 */ digit = 6; else if ( bit == 0x00000010 ) /* 0x00000010 */ digit = 5; } else if ( bit & 0x0000000C ) { /* 0x0000000C */ if ( bit == 0x00000008 ) /* 0x00000008 */ digit = 4; else if ( bit == 0x00000004 ) /* 0x00000004 */ digit = 3; } else if ( bit == 0x00000002 ) /* 0x00000002 */ digit = 2; else if ( bit == 0x00000001 ) /* 0x00000001 */ digit = 1; return ( digit ); } static int countBits ( int bits ) { int count = 0; int mask = 1; while ( bits ) { if ( bits & mask ) { bits ^= mask; ++count; } mask <<= 1; } return ( count ); } static int confirm ( PUZZLE *puzzle, const char *message ) { int y = puzzle->y0 - 1; int x; int c; int stringLength = strlen ( message ); x = puzzle->x0 + ( ( isBig ( puzzle ) ? 19 : 13 ) - stringLength ) / 2; move ( y, x ); while ( *message ) addch ( *message++ ); refresh (); while ( ( c = getch () ) == ERR ); move ( y, 0 ); clrtoeol (); return ( c ); } static void displayCaptions ( PUZZLE *puzzle, const char *line1, const char *line2 ) { int y; const char *c; y = puzzle->y0 + ( isBig ( puzzle ) ? 20 : 14 ); if ( c = line1 ) { int stringLength; move ( y, 0 ); clrtoeol (); if ( stringLength = strlen ( c ) ) { int x; x = puzzle->x0 + ( ( isBig ( puzzle ) ? 19 : 13 ) - stringLength ) / 2; move ( y, x ); while ( *c ) addch ( *c++ ); } } ++y; if ( c = line2 ) { int stringLength; move ( y, 0 ); clrtoeol (); if ( stringLength = strlen ( c ) ) { int x; x = puzzle->x0 + ( ( isBig ( puzzle ) ? 19 : 13 ) - stringLength ) / 2; move ( y, x ); while ( *c ) addch ( *c++ ); } } move ( puzzle->y0 + 1, puzzle->x0 + 1 ); } static void displayEntry ( PUZZLE *puzzle, int i, int j, int entry ) { if ( isDisplayed ( puzzle ) ) { int y; int x; if ( isBig ( puzzle ) ) { x = ( j << 1 ) + 1; y = ( i << 1 ) + 1; } else { x = ( ( j << 2 ) + 3 ) / 3; y = ( ( i << 2 ) + 3 ) / 3; } if ( puzzle->delay ) { int c; timeout ( puzzle->delay ); if ( ( c = getch () ) != ERR ) { timeout ( -1 ); if ( c == 'q' || c == 'Q' ) { c = confirm ( puzzle, quit ); if ( c == 'y' || c == 'Y' ) { puzzle->flags = 0; puzzle->delay = 0; } } else { displayCaptions ( puzzle, paused, "" ); if ( ( c = getch () ) == 'q' || c == 'Q' ) { c = confirm ( puzzle, quit ); if ( c == 'y' || c == 'Y' ) { puzzle->flags = 0; puzzle->delay = 0; } else c = ' '; } else c = ' '; if ( c == ' ' ) displayCaptions ( puzzle, thinking, "" ); } } else timeout ( -1 ); } move ( puzzle->y0 + y, puzzle->x0 + x ); addch ( ( entry + '0' ) | A_UNDERLINE ); move ( puzzle->y0 + y, puzzle->x0 + x ); if ( puzzle->delay ) refresh (); } } static void deleteEntry ( PUZZLE *puzzle, int i, int j ) { int entry = puzzle->board [i][j]; if ( entry != 0 ) { int bit = digit2bit ( entry ); puzzle->rowMasks [i] |= bit; puzzle->columnMasks [j] |= bit; puzzle->blockMasks [i/3][j/3] |= bit; puzzle->board [i][j] = 0; } } static int makeEntry ( PUZZLE *puzzle, int i, int j, int entry ) { int status = 1; /* Is this a necessary entry? */ if ( entry != puzzle->board [i][j] ) { int bit = digit2bit ( entry ); status = 0; /* Is this a legal entry? */ if ( puzzle->rowMasks [i] & puzzle->columnMasks [j] & puzzle->blockMasks [i/3][j/3] & bit ) { deleteEntry ( puzzle, i, j ); status = 1; puzzle->rowMasks [i] ^= bit; puzzle->columnMasks [j] ^= bit; puzzle->blockMasks [i/3][j/3] ^= bit; puzzle->board [i][j] = entry; puzzle->masks [i][j] = 0; displayEntry ( puzzle, i, j, entry ); } } return ( status ); } static int enterClues ( PUZZLE *puzzle ) { int status = -1; int y = 1; int x = 1; int y_count = 0; int x_count = 0; while ( status < 0 ) { int c; switch ( c = getch () ) { case 's': /* Solve. */ case 'S': /* Solve. */ c = 0; status = 1; break; case 'q': /* Quit. */ case 'Q': /* Quit. */ case ESC: /* Quit. */ c = confirm ( puzzle, quit ); if ( c == 'y' || c == 'Y' ) { c = 0; status = 0; } break; case KEY_NPAGE: if ( isBig ( puzzle ) ) { if ( ( y += 6 ) > 17 ) y -= 18; } else { if ( ( y += 4 ) > 11 ) y -= 12; } break; case KEY_PPAGE: if ( isBig ( puzzle ) ) { if ( ( y -= 6 ) < 1 ) y += 18; } else { if ( ( y -= 4 ) < 1 ) y += 12; } break; case KEY_HOME: x = 1; break; case KEY_END: x = isBig ( puzzle ) ? 17 : 11; break; case KEY_DC: /* DEL */ break; default: if ( isdigit ( c ) && c != '0' ) { int i; int j; if ( isBig ( puzzle ) ) { i = ( y - 1 ) >> 1; j = ( x - 1 ) >> 1; } else { i = ( y * 3 ) >> 2; j = ( x * 3 ) >> 2; } if ( makeEntry ( puzzle, i, j, c - '0' ) ) { addch ( c | A_BOLD ); } else { beep (); break; } } else if ( isspace ( c ) || c == '-' ) { if ( c == HT ) { int remainder; if ( isBig ( puzzle ) ) remainder = 5 - ( x % 6 ); else remainder = 3 - ( x % 4 ); x_count = 2; x += remainder; } else if ( c == CR ) { x = isBig ( puzzle ) ? 17 : 11; x_count = 2; } else { int i; int j; if ( isBig ( puzzle ) ) { i = ( y - 1 ) >> 1; j = ( x - 1 ) >> 1; } else { i = ( y * 3 ) >> 2; j = ( x * 3 ) >> 2; } deleteEntry ( puzzle, i, j ); addch ( '-' ); } } else { c = 0; beep (); break; } case KEY_RIGHT: if ( isBig ( puzzle ) ) { if ( x == 17 ) x = 1; else { x += 2; break; } } else { if ( x == 11 ) { x = 1; x_count = 0; } else { x_count += 4; while ( x_count > 2 ) { x_count -= 3; x++; } break; } } case KEY_DOWN: if ( isBig ( puzzle ) ) { if ( y == 17 ) y = 1; else y += 2; } else { if ( y == 11 ) { y = 1; y_count = 0; } else { y_count += 4; while ( y_count > 2 ) { y_count -= 3; y++; } } } break; case KEY_BACKSPACE: case KEY_LEFT: if ( isBig ( puzzle ) ) { if ( x == 1 ) x = 17; else { x -= 2; break; } } else { if ( x == 1 ) { x = 11; x_count = 2; } else { x_count -= 4; while ( x_count < 0 ) { x_count += 3; --x; } break; } } case KEY_UP: if ( isBig ( puzzle ) ) { if ( y == 1 ) y = 17; else y -= 2; } else { if ( y == 1 ) { y_count = 2; y = 11; } else { y_count -= 4; while ( y_count < 0 ) { y_count += 3; --y; } } } break; } move ( puzzle->y0 + y, puzzle->x0 + x ); if ( c == KEY_BACKSPACE || c == KEY_DC ) { int i; int j; if ( isBig ( puzzle ) ) { i = ( y - 1 ) >> 1; j = ( x - 1 ) >> 1; } else { i = ( y * 3 ) >> 2; j = ( x * 3 ) >> 2; } deleteEntry ( puzzle, i, j ); addch ( '-' ); move ( puzzle->y0 + y, puzzle->x0 + x ); } refresh (); } return ( status ); } static void drawTitle ( PUZZLE *puzzle ) { int titleLen = strlen ( gameName ); int x; x = puzzle->x0 + ( ( isBig ( puzzle ) ? 19 : 13 ) - titleLen ) / 2; move ( puzzle->y0 - 2, x ); x = 0; while ( x < titleLen ) addch ( gameName [ x++] | A_BOLD | A_UNDERLINE ); } static PUZZLE *drawBoard ( void ) { PUZZLE *puzzle = NULL; int y; int x; getmaxyx ( stdscr, y, x ); if ( y < 18 || x < 14 ) { if ( ! isendwin () ) endwin (); fprintf ( stderr, "Your screen is not big enough to display the Sudoku puzzle.\n" ); } else if ( puzzle = malloc ( sizeof ( PUZZLE ) ) ) { int yBorder; int bigBox; int littleBox; puzzle->flags = ( y < 24 || x < 20 ) ? 0 : BIG; if ( isBig ( puzzle ) ) { puzzle->y0 = ( ( y - 20 ) >> 1 ); puzzle->x0 = ( ( x - 20 ) >> 1 ); yBorder = littleBox = 5; bigBox = 19; } else { puzzle->y0 = ( ( y - 14 ) >> 1 ); puzzle->x0 = ( ( x - 14 ) >> 1 ); yBorder = littleBox = 3; bigBox = 13; } clear (); drawTitle ( puzzle ); for ( y = 0; y < bigBox; ++y ) { int xBorder = littleBox; move ( puzzle->y0 + y, puzzle->x0 ); if ( yBorder == littleBox ) { for ( x = 0; x < bigBox; ++x ) { if ( xBorder == littleBox ) { int c = ACS_PLUS; if ( y == 0 ) { c = ACS_TTEE; if ( x == 0 ) c = ACS_ULCORNER; else if ( x == ( bigBox - 1 ) ) c = ACS_URCORNER; } else if ( y == ( bigBox - 1 ) ) { c = ACS_BTEE; if ( x == 0 ) c = ACS_LLCORNER; else if ( x == ( bigBox - 1 ) ) c = ACS_LRCORNER; } else { if ( x == 0 ) c = ACS_LTEE; else if ( x == ( bigBox - 1 ) ) c = ACS_RTEE; } addch ( c | A_BOLD ); xBorder = 0; } else { addch ( ACS_HLINE | A_BOLD ); ++xBorder; } } yBorder = 0; } else { for ( x = 0; x < bigBox; ++x ) { if ( xBorder == littleBox ) { addch ( ACS_VLINE | A_BOLD ); xBorder = 0; } else { int c = '-'; if ( isBig ( puzzle ) && ( ! ( x & 1 ) || ! ( y & 1 ) ) ) c = ' '; addch ( c ); ++xBorder; } } ++yBorder; } } displayCaptions ( puzzle, instructions1, instructions2 ); move ( puzzle->y0 + 1, puzzle->x0 + 1 ); refresh (); } return ( puzzle ); } static void closePuzzle ( PUZZLE *puzzle ) { if ( puzzle ) { if ( ! isendwin () ) endwin (); free ( puzzle ); } } static void copyPuzzle ( PUZZLE *src, PUZZLE *dest ) { int puzzleSize = sizeof (PUZZLE); char *p = ( char * ) src; char *q = ( char * ) dest; while ( puzzleSize-- ) *q++ = *p++; dest->flags = 0; dest->delay = 0; } static PUZZLE *openPuzzle ( int delay ) { PUZZLE *puzzle = NULL; struct stat st_buff; /* Check if standard out is a terminal. */ if ( fstat ( 1, &st_buff ) < 0 ) { perror ( "Standard out not available" ); /* Test if standard out is a terminal. */ } else if ( S_ISCHR ( st_buff.st_mode ) ) { if ( initscr () ) { cbreak (); timeout ( -1 ); noecho (); nonl (); intrflush ( stdscr, FALSE ); keypad ( stdscr, TRUE ); /* Draw the puzzle and allocate the object. */ if ( puzzle = drawBoard () ) { int i; int j; puzzle->technique = 0; puzzle->difficulty = 0; puzzle->delay = delay; for ( i = 0; i < 9; ++i ) { puzzle->rowMasks [i] = BIT_MASK; puzzle->columnMasks [i] = BIT_MASK; for ( j = 0; j < 9; ++j ) { puzzle->board [i][j] = 0; puzzle->masks [i][j] = BIT_MASK; } } for ( i = 0; i < 3; ++i ) for ( j = 0; j < 3; ++j ) puzzle->blockMasks [i][j] = BIT_MASK; if ( enterClues ( puzzle ) ) { puzzle->flags |= DISPLAYED; for ( i = 0; i < 9; ++i ) { for ( j = 0; j < 9; ++j ) { if ( puzzle->board [i][j] == 0 ) puzzle->masks [i][j] = ( puzzle->rowMasks [i] & puzzle->columnMasks [j] & puzzle->blockMasks [i/3][j/3] ); } } } else { closePuzzle ( puzzle ); puzzle = NULL; } } } else fprintf ( stderr, "Cannot take control of terminal.\n" ); } else fprintf ( stderr, "Standard out not a terminal" ); return ( puzzle ); } static int countUnsolved ( PUZZLE *puzzle ) { int unsolved = 0; int i; for ( i = 0; i < 9; ++i ) { int j; for ( j = 0; j < 9; ++j ) { if ( puzzle->board [i][j] == 0 ) ++unsolved; } } return ( unsolved ); } static void updateRowMasks ( PUZZLE *puzzle, int row, int entry ) { int column; int mask = ~digit2bit ( entry ); for ( column = 0; column < 9; ++column ) { puzzle->masks [row][column] &= mask; } } static void updateColumnMasks ( PUZZLE *puzzle, int column, int entry ) { int row; int mask = ~digit2bit ( entry ); for ( row = 0; row < 9; ++row ) { puzzle->masks [row][column] &= mask; } } static void updateBlockMasks ( PUZZLE *puzzle, int row, int column, int entry ) { int rowMax = row + 3 - ( row % 3 ); int columnMax = column + 3 - ( column % 3 ); int mask = ~digit2bit ( entry ); for ( row = rowMax - 3; row < rowMax; ++row ) { for ( column = columnMax - 3; column < columnMax; ++column ) { puzzle->masks [row][column] &= mask; } } } static int missingDigitScan ( PUZZLE *puzzle ) { int progress = 0; int i; puzzle->difficulty += 1; for ( i = 0; i < 9 && progress > -1; ++i ) { int j; for ( j = 0; j < 9 && progress > -1; ++j ) { if ( puzzle->board [i][j] == 0 ) { int solution; if ( solution = bit2digit ( puzzle->masks [i][j] ) ) { ++progress; makeEntry ( puzzle, i, j, solution ); updateRowMasks ( puzzle, i, solution ); updateColumnMasks ( puzzle, j, solution ); updateBlockMasks ( puzzle, i, j, solution ); } else if ( ! puzzle->masks [i][j] ) progress = -1; } } } if ( progress ) puzzle->technique |= MISSING_DIGIT; return ( progress ); } static int crossHatch ( int *masks ) { int progress = 0; int solutions [9]; int i; for ( i = 0; i < 9; ++i ) { int j; solutions [i] = masks [i]; for ( j = 0; j < 9; ++j ) if ( j != i ) solutions [i] &= ~masks [j]; } for ( i = 0; i < 9; ++i ) { if ( masks [i] = bit2digit ( solutions [i] ) ) ++progress; } return ( progress ); } static int getRowMasks ( PUZZLE *puzzle, int row, int *masks ) { int status = 0; if ( puzzle->rowMasks [row] ) { int mask = 0; int column; status = 1; /* Make masks for the row. */ for ( column = 0; column < 9; ++column ) { masks [column] = puzzle->masks [row][column]; mask |= masks [column]; } if ( mask != puzzle->rowMasks [row] ) status = -1; } return ( status ); } static int displayRowSolutions ( PUZZLE *puzzle, int row, int *solutions ) { int progress = 0; int column; /* Display the solutions. */ for ( column = 0; column < 9; ++column ) { if ( solutions [column] ) { if ( makeEntry ( puzzle, row, column, solutions [column] ) ) { ++progress; updateColumnMasks ( puzzle, column, solutions [column] ); updateBlockMasks ( puzzle, row, column, solutions [column] ); } } } return ( progress ); } static int getColumnMasks ( PUZZLE *puzzle, int column, int *masks ) { int status = 0; /* Make sure the column is not already filled. */ if ( puzzle->columnMasks [column] ) { int mask = 0; int row; status = 1; /* Make masks for the column. */ for ( row = 0; row < 9; ++row ) { masks [row] = puzzle->masks [row][column]; mask |= masks [row]; } if ( mask != puzzle->columnMasks [column] ) status = -1; } return ( status ); } static int displayColumnSolutions ( PUZZLE *puzzle, int column, int *solutions ) { int progress = 0; int row; /* Enter the results of cross hatching the column. */ for ( row = 0; row < 9; ++row ) { if ( solutions [row] ) { if ( makeEntry ( puzzle, row, column, solutions [row] ) ) { ++progress; updateRowMasks ( puzzle, row, solutions [row] ); updateBlockMasks ( puzzle, row, column, solutions [row] ); } } } return ( progress ); } static int getBlockMasks ( PUZZLE *puzzle, int i, int j, int *masks ) { int status = 0; /* Make sure the 3x3 block is not already full. */ if ( puzzle->blockMasks [i][j] ) { int rowMax = ( i + 1 ) * 3; int columnMax = ( j + 1 ) * 3; int k = 0; int mask = 0; int row; status = 1; /* Make masks for the 3x3 block. */ for ( row = rowMax - 3; row < rowMax; ++row ) { int column; for ( column = columnMax - 3; column < columnMax; ++column ) { masks [k] = puzzle->masks [row][column]; mask |= masks [k]; ++k; } } if ( mask != puzzle->blockMasks [i][j] ) status = -1; } return ( status ); } static int displayBlockSolutions ( PUZZLE *puzzle, int i, int j, int *solutions ) { int progress = 0; int rowMax = ( i + 1 ) * 3; int columnMax = ( j + 1 ) * 3; int k = 0; int row; for ( row = rowMax - 3; row < rowMax; ++row ) { int column; for ( column = columnMax - 3; column < columnMax; ++column ) { if ( solutions [k] ) { if ( makeEntry ( puzzle, row, column, solutions [k] ) ) { ++progress; updateRowMasks ( puzzle, row, solutions [k] ); updateColumnMasks ( puzzle, column, solutions [k] ); } } ++k; } } return ( progress ); } static int crossHatchScan ( PUZZLE *puzzle ) { int progress = 0; int i; puzzle->difficulty += 1; /* Cross hatch the 3x3 blocks. */ for ( i = 0; i < 3 && progress > -1; i++ ) { int j; for ( j = 0; j < 3 && progress > -1; j++ ) { int masks [9]; int status; if ( ( status = getBlockMasks ( puzzle, i, j, masks ) ) > 0 ) { if ( crossHatch ( masks ) ) { progress += displayBlockSolutions ( puzzle, i, j, masks ); } } else if ( status < 0 ) progress = -1; } } if ( ! progress ) { puzzle->difficulty += 1; /* Cross hatch the rows. */ for ( i = 0; i < 9 && progress > -1; ++i ) { int masks [9]; int status; if ( ( status = getRowMasks ( puzzle, i, masks ) ) > 0 ) { if ( crossHatch ( masks ) ) { progress += displayRowSolutions ( puzzle, i, masks ); } } else if ( status < 0 ) progress = -1; } /* Cross hatch the columns. */ for ( i = 0; i < 9 && progress > -1; ++i ) { int masks [9]; int status; if ( ( status = getColumnMasks ( puzzle, i, masks ) ) > 0 ) { if ( crossHatch ( masks ) ) { progress += displayColumnSolutions ( puzzle, i, masks ); } } else if ( status < 0 ) progress = -1; } if ( progress ) puzzle->technique |= CROSS_HATCH_2; } else puzzle->technique |= CROSS_HATCH; return ( progress ); } static int findRowTuple ( PUZZLE *puzzle, int row, int mask, int bitCount ) { int progress = 0; int tupleMask = 0; int tupleCount = 0; int tupleBit = 0x100; int exactCount = 0; int rowMax = row + 3 - ( row % 3 ); int columnMax = 0; int column; for ( column = 0; column < 9; ++column ) { int cellMask = puzzle->masks [row][column]; if ( mask & cellMask ) { ++tupleCount; tupleMask |= tupleBit; if ( ! ( ~mask & cellMask ) ) ++exactCount; } tupleBit >>= 1; } if ( exactCount == bitCount ) { tupleBit = 0x100; tupleMask = 0; for ( column = 0; column < 9; ++column ) { int cellMask = puzzle->masks [row][column]; if ( cellMask ) { if ( ! ( ~mask & cellMask ) ) tupleMask |= tupleBit; else if ( mask & cellMask ) { puzzle->masks [row][column] &= ~mask; ++progress; } } tupleBit >>= 1; } if ( bitCount > 1 ) { puzzle->technique |= NAKED_TUPLE; if ( GET_NAKED_TUPLE_LEVEL ( puzzle->technique ) < bitCount ) SET_NAKED_TUPLE_LEVEL ( puzzle->technique, bitCount ); } } else if ( tupleCount == bitCount ) { for ( column = 0; column < 9; ++column ) { int cellMask = puzzle->masks [row][column]; if ( ( mask & cellMask ) && ( ~mask & cellMask ) ) { puzzle->masks [row][column] &= mask; ++progress; } } if ( bitCount > 1 ) { puzzle->technique |= HIDDEN_TUPLE; if ( GET_HIDDEN_TUPLE_LEVEL ( puzzle->technique ) < bitCount ) SET_HIDDEN_TUPLE_LEVEL ( puzzle->technique, bitCount ); } } if ( bitCount < 4 ) { if ( ! ( tupleMask & ~SQUARE_1 ) ) columnMax = 3; else if ( ! ( tupleMask & ~SQUARE_2 ) ) columnMax = 6; else if ( ! ( tupleMask & ~SQUARE_3 ) ) columnMax = 9; if ( columnMax ) { int i; for ( i = rowMax - 3; i < rowMax; ++i ) { if ( i != row ) { for ( column = columnMax - 3; column < columnMax; ++column ) { if ( puzzle->masks [i][column] & mask ) { puzzle->masks [i][column] &= ~mask; ++progress; puzzle->technique |= SET_INTERSECTION; } } } } } } return ( progress ); } static int rowTuples ( PUZZLE *puzzle, int row, int mask, int bitCount, int skip ) { int progress = 0; int maskBits = countBits ( mask ); if ( maskBits > bitCount && skip < maskBits ) { int digitBit = 0x100; int skipped = 0; --maskBits; while ( ! progress && digitBit ) { if ( ( digitBit & mask ) && skipped++ == skip ) { int digitMask = mask ^ digitBit; if ( maskBits != bitCount ) progress += rowTuples ( puzzle, row, digitMask, bitCount, skip ); else progress += findRowTuple ( puzzle, row, digitMask, bitCount ); ++skip; } digitBit >>= 1; } } return ( progress ); } static int findColumnTuple ( PUZZLE *puzzle, int column, int mask, int bitCount ) { int progress = 0; int tupleCount = 0; int tupleMask = 0; int tupleBit = 0x100; int exactCount = 0; int rowMax = 0; int columnMax = column + 3 - ( column % 3 ); int row; for ( row = 0; row < 9; ++row ) { int cellMask = puzzle->masks [row][column]; if ( mask & cellMask ) { ++tupleCount; tupleMask |= tupleBit; if ( ! ( ~mask & cellMask ) ) ++exactCount; } tupleBit >>= 1; } if ( exactCount == bitCount ) { tupleMask = 0; tupleBit = 0x100; for ( row = 0; row < 9; ++row ) { int cellMask = puzzle->masks [row][column]; if ( cellMask ) { if ( ! ( ~mask & cellMask ) ) tupleMask |= tupleBit; else if ( mask & cellMask ) { puzzle->masks [row][column] &= ~mask; ++progress; } } tupleBit >>= 1; } if ( bitCount > 1 ) { if ( progress ) puzzle->technique |= NAKED_TUPLE; if ( GET_NAKED_TUPLE_LEVEL ( puzzle->technique ) < bitCount ) SET_NAKED_TUPLE_LEVEL ( puzzle->technique, bitCount ); } } else if ( tupleCount == bitCount ) { for ( row = 0; row < 9; ++row ) { int cellMask = puzzle->masks [row][column]; if ( ( mask & cellMask ) && ( ~mask & cellMask ) ) { puzzle->masks [row][column] &= mask; ++progress; } } if ( bitCount > 1 ) { if ( progress ) puzzle->technique |= HIDDEN_TUPLE; if ( GET_HIDDEN_TUPLE_LEVEL ( puzzle->technique ) < bitCount ) SET_HIDDEN_TUPLE_LEVEL ( puzzle->technique, bitCount ); } } if ( bitCount < 4 ) { if ( ! ( tupleMask & ~SQUARE_1 ) ) rowMax = 3; else if ( ! ( tupleMask & ~SQUARE_2 ) ) rowMax = 6; else if ( ! ( tupleMask & ~SQUARE_3 ) ) rowMax = 9; if ( rowMax ) { int j; for ( j = columnMax - 3; j < columnMax; ++j ) { if ( j != column ) { for ( row = rowMax - 3; row < rowMax; ++row ) { if ( puzzle->masks [row][j] & mask ) { puzzle->masks [row][j] &= ~mask; ++progress; puzzle->technique |= SET_INTERSECTION; } } } } } } return ( progress ); } static int columnTuples ( PUZZLE *puzzle, int column, int mask, int bitCount, int skip ) { int progress = 0; int maskBits = countBits ( mask ); if ( maskBits > bitCount && skip < maskBits ) { int digitBit = 0x100; int skipped = 0; --maskBits; while ( ! progress && digitBit ) { if ( ( digitBit & mask ) && skipped++ == skip ) { int digitMask = mask ^ digitBit; if ( maskBits != bitCount ) progress += columnTuples ( puzzle, column, digitMask, bitCount, skip ); else progress += findColumnTuple ( puzzle, column, digitMask, bitCount ); ++skip; } digitBit >>= 1; } } return ( progress ); } static findBlockTuple ( PUZZLE *puzzle, int top, int left, int mask, int bitCount ) { int progress = 0; int rowMax = ( top + 1 ) * 3; int columnMax = ( left + 1 ) * 3; int tupleCount = 0; int tupleMask = 0; int tupleBit = 0x100; int exactCount = 0; int i = -1; int j = -1; int row; for ( row = rowMax - 3; row < rowMax; ++row ) { int column; for ( column = columnMax - 3; column < columnMax; ++column ) { int cellMask = puzzle->masks [row][column]; if ( mask & cellMask ) { ++tupleCount; tupleMask |= tupleBit; if ( ! ( ~mask & cellMask ) ) ++exactCount; } tupleBit >>= 1; } } if ( exactCount == bitCount ) { tupleMask = 0; tupleBit = 0x100; for ( row = rowMax - 3; row < rowMax; ++row ) { int column; for ( column = columnMax - 3; column < columnMax; ++column ) { int cellMask = puzzle->masks [row][column]; if ( cellMask ) { if ( ! ( ~mask & cellMask ) ) tupleMask |= tupleBit; else if ( mask & cellMask ) { puzzle->masks [row][column] &= ~mask; ++progress; } } tupleBit >>= 1; } } if ( bitCount > 1 ) { if ( progress ) puzzle->technique |= NAKED_TUPLE; if ( GET_NAKED_TUPLE_LEVEL ( puzzle->technique ) < bitCount ) SET_NAKED_TUPLE_LEVEL ( puzzle->technique, bitCount ); } } else if ( tupleCount == bitCount ) { for ( row = rowMax - 3; row < rowMax; ++row ) { int column; for ( column = columnMax - 3; column < columnMax; ++column ) { int cellMask = puzzle->masks [row][column]; if ( ( mask & cellMask ) && ( ~mask & cellMask ) ) { puzzle->masks [row][column] &= mask; ++progress; } } } if ( bitCount > 1 ) { if ( progress ) puzzle->technique |= HIDDEN_TUPLE; if ( GET_HIDDEN_TUPLE_LEVEL ( puzzle->technique ) < bitCount ) SET_HIDDEN_TUPLE_LEVEL ( puzzle->technique, bitCount ); } } if ( bitCount < 4 ) { if ( ! ( tupleMask & ~ROW_1 ) ) i = rowMax - 3; else if ( ! ( tupleMask & ~ROW_2 ) ) i = rowMax - 2; else if ( ! ( tupleMask & ~ROW_3 ) ) i = rowMax - 1; else if ( ! ( tupleMask & ~COLUMN_1 ) ) j = columnMax - 3; else if ( ! ( tupleMask & ~COLUMN_2 ) ) j = columnMax - 2; else if ( ! ( tupleMask & ~COLUMN_3 ) ) j = columnMax - 1; if ( i > -1 ) { int jMax = columnMax - 3; for ( j = 0; j < jMax; ++j ) { if ( puzzle->masks [i][j] & mask ) { puzzle->masks [i][j] &= ~mask; ++progress; puzzle->technique |= SET_INTERSECTION; } } for ( j = columnMax; j < 9; ++j ) { if ( puzzle->masks [i][j] & mask ) { puzzle->masks [i][j] &= ~mask; ++progress; puzzle->technique |= SET_INTERSECTION; } } } else if ( j > -1 ) { int iMax = rowMax - 3; for ( i = 0; i < iMax; ++i ) { if ( puzzle->masks [i][j] & mask ) { puzzle->masks [i][j] &= ~mask; ++progress; puzzle->technique |= SET_INTERSECTION; } } for ( i = rowMax; i < 9; ++i ) { if ( puzzle->masks [i][j] & mask ) { puzzle->masks [i][j] &= ~mask; ++progress; puzzle->technique |= SET_INTERSECTION; } } } } return ( progress ); } static int blockTuples ( PUZZLE *puzzle, int top, int left, int mask, int bitCount, int skip ) { int progress = 0; int maskBits = countBits ( mask ); if ( maskBits > bitCount && skip < maskBits ) { int digitBit = 0x100; int skipped = 0; --maskBits; while ( digitBit ) { if ( ( digitBit & mask ) && skipped++ == skip ) { int digitMask = mask ^ digitBit; if ( maskBits != bitCount ) progress += blockTuples ( puzzle, top, left, digitMask, bitCount, skip ); else progress += findBlockTuple ( puzzle, top, left, digitMask, bitCount ); ++skip; } digitBit >>= 1; } } return ( progress ); } static int tuplesAnalysis ( PUZZLE *puzzle ) { int progress = 0; int bitCount = 1; int i; while ( ! progress && bitCount < 9 ) { puzzle->difficulty += 1; for ( i = 0; i < 9; ++i ) { int mask = puzzle->rowMasks [i]; if ( mask ) progress += rowTuples ( puzzle, i, mask, bitCount, 0 ); } for ( i = 0; i < 9; ++i ) { int mask = puzzle->columnMasks [i]; if ( mask ) progress += columnTuples ( puzzle, i, mask, bitCount, 0 ); } for ( i = 0; i < 3; ++i ) { int j; for ( j = 0; j < 3; ++j ) { int mask = puzzle->blockMasks [i][j]; if ( mask ) progress += blockTuples ( puzzle, i, j, mask, bitCount, 0 ); } } ++bitCount; } return ( progress ); } static int contradictions ( PUZZLE *puzzle ) { int progress = 0; int bitCount = 2; puzzle->difficulty += 1; while ( ! progress ) { int row; int minBitCount = 9; for ( row = 0; ! progress && row < 9; row++ ) { int column; for ( column = 0; ! progress && column < 9; column++ ) { int bits = 0; if ( puzzle->masks [row][column] && ( bits = countBits ( puzzle->masks [row][column] ) ) == bitCount ) { int bit = 0x100; int ambiguous = 0; int mask = puzzle->masks [row][column]; while ( bit ) { if ( bit & mask ) { PUZZLE puzzle2; int entry = bit2digit ( bit ); int unsolved; copyPuzzle ( puzzle, &puzzle2 ); makeEntry ( &puzzle2, row, column, entry ); updateRowMasks ( &puzzle2, row, entry ); updateColumnMasks ( &puzzle2, column, entry ); updateBlockMasks ( &puzzle2, row, column, entry ); if ( ( unsolved = solvePuzzle ( &puzzle2 ) ) < 0 ) { puzzle->masks [row][column] ^= bit; puzzle->technique = puzzle2.technique; ++progress; break; } else if ( unsolved || ambiguous ) { progress = -1; break; } else ++ambiguous; } bit >>= 1; } } else { if ( bits > bitCount && bits < minBitCount ) minBitCount = bits; } } } bitCount = minBitCount; } if ( progress > 0 ) puzzle->technique |= WHAT_IF; return ( progress ); } static int solvePuzzle ( PUZZLE *puzzle ) { int unsolved; int progress = 1; int i; if ( isDisplayed ( puzzle ) && puzzle->delay ) { displayCaptions ( puzzle, thinking, "" ); refresh (); } unsolved = countUnsolved ( puzzle ); while ( unsolved && progress > 0 ) { if ( ( progress = crossHatchScan ( puzzle ) ) || ( progress = missingDigitScan ( puzzle ) ) ) { if ( progress > 0 ) unsolved -= progress; else { unsolved = -1; progress = 0; } } else if ( ! ( progress = tuplesAnalysis ( puzzle ) ) ) progress = contradictions ( puzzle ); } if ( isDisplayed ( puzzle ) ) { if ( unsolved ) { if ( puzzle->delay ) { timeout ( puzzle->delay ); if ( getch () != ERR ) { displayCaptions ( puzzle, paused, "" ); timeout ( -1 ); getch (); } else timeout ( -1 ); } if ( unsolved > 0 ) displayCaptions ( puzzle, stumped, "" ); else displayCaptions ( puzzle, noSolution, "" ); } else displayCaptions ( puzzle, solved, "" ); beep (); while ( ( i = getch () ) == ERR ); } return ( unsolved ); } static char * tupleNames [] = { "pair", "triplet", "quadruplet", "quintuplet", "sextuplet", "septuplet", "octuplet" }; static char tupleNameBuffer [100]; static char *printTuple ( int tuple ) { char *tupleName = tupleNameBuffer; if ( tuple > 1 && tuple < 9 ) tupleName = tupleNames [tuple-2]; else sprintf ( tupleNameBuffer, "%d", tuple ); return ( tupleName ); } void printHelp ( char *programName ) { fprintf ( stderr, "\nUse: %s [-afsnhi]\n\nWhere:\n", programName ); fprintf ( stderr, "\t-a Displays only the analysis and difficuly score.\n" ); fprintf ( stderr, "\t-f Fast solution.\n" ); fprintf ( stderr, "\t-s Slow solution.\n" ); fprintf ( stderr, "\t-n No delay solution.\n" ); fprintf ( stderr, "\t-h Help screen.\n" ); fprintf ( stderr, "\t-i Instruction screen.\n" ); } void printInstructions ( void ) { fprintf ( stderr, "\nEnter clues (digits 1-9). Use arrow keys,\n" ); fprintf ( stderr, "space, backspace, tab and enter keys to\n" ); fprintf ( stderr, "position the cursor. Press 's' to end\n" ); fprintf ( stderr, "entering clues and start the solution\nlogic.\n" ); fprintf ( stderr, "\nDuring the solution stage, press any key\n" ); fprintf ( stderr, "to pause and then press any key to resume.\n" ); fprintf ( stderr, "Press 'q' at any time to quit.\n" ); } #define DEFAULT_DELAY 1000 #define FAST_DELAY 500 #define SLOW_DELAY 2000 int main ( int argc, char **argv ) { int status = 1; PUZZLE *puzzle; char *programName; char *revision; int delay = DEFAULT_DELAY; int analysis = 0; int warning = 0; int help = 0; programName = *argv; revision = strdup ( "$Revision: 1.15 $" ); revision += 1; revision [ strlen ( revision ) - 1 ] = '\0'; while ( *++argv ) { if ( **argv == '-' ) { int index = 1; while ( argv [0][index] ) { switch ( argv [0][index] ) { case 'a': if ( delay != DEFAULT_DELAY ) { if ( ! ( warning & 2 ) ) { fprintf ( stderr, "Warning - speed setting has no effect when analysis option selected.\n" ); warning |= 2; } } analysis = 1; break; case 'f': if ( analysis ) { if ( ! ( warning & 2 ) ) { fprintf ( stderr, "Warning - speed setting has no effect when analysis option selected.\n" ); warning |= 2; } } else if ( delay == DEFAULT_DELAY ) delay = FAST_DELAY; else if ( ! ( warning & 1 ) ) { warning |= 1; fprintf ( stderr, "Warning - speed already set, discarding last speed setting.\n" ); } break; case 's': if ( analysis ) { if ( ! ( warning & 2 ) ) { fprintf ( stderr, "Warning - speed setting has no effect when analysis option selected.\n" ); warning |= 2; } } else if ( delay == DEFAULT_DELAY ) delay = SLOW_DELAY; else if ( ! ( warning & 1 ) ) { warning |= 1; fprintf ( stderr, "Warning - speed already set, discarding last speed setting.\n" ); } break; case 'n': if ( analysis ) { if ( ! ( warning & 2 ) ) { fprintf ( stderr, "Warning - speed setting has no effect when analysis option selected.\n" ); warning |= 2; } } else if ( delay == DEFAULT_DELAY ) delay = 0; else if ( ! ( warning & 1 ) ) { warning |= 1; fprintf ( stderr, "Warning - speed already set, discarding last speed setting.\n" ); } break; case 'h': help |= 1; break; case 'i': help |= 2; break; default: warning += 4; fprintf ( stderr, "Unknown option letter (-%c) ignored.\n", argv [0][index] ); break; } ++index; } } else fprintf ( stderr, "Illegal command line parameter (%s) ignored.\n", *argv ); } if ( warning ) sleep ( ( ( warning + 3 ) >> 1 ) + 1 ); if ( help ) { fprintf ( stderr, "%s\n%s\n", PUZZLE_TITLE, revision ); if ( help & 1 ) printHelp ( programName ); if ( help & 2 ) printInstructions (); status = 0; } else if ( puzzle = openPuzzle ( delay ) ) { int technique = 0; int difficulty = 0; if ( analysis ) { puzzle->flags = 0; puzzle->delay = 0; } status = solvePuzzle ( puzzle ); if ( ! status ) { difficulty = puzzle->difficulty; technique = puzzle->technique; } closePuzzle ( puzzle ); if ( ! status ) { fprintf ( stdout, "Solution techniques used:\n" ); if ( technique & CROSS_HATCH ) fprintf ( stdout, "\tBlock cross hatch scan\n" ); if ( technique & CROSS_HATCH_2 ) fprintf ( stdout, "\tRow/column cross hatch scan\n" ); if ( technique & MISSING_DIGIT ) fprintf ( stdout, "\tMissing digit scan\n" ); if ( technique & SET_INTERSECTION ) fprintf ( stdout, "\tRegion intersection analysis\n" ); if ( technique & NAKED_TUPLE ) fprintf ( stdout, "\tNaked %s analysis\n", printTuple ( GET_NAKED_TUPLE_LEVEL ( technique ) ) ); if ( technique & HIDDEN_TUPLE ) fprintf ( stdout, "\tHidden %s analysis\n", printTuple ( GET_HIDDEN_TUPLE_LEVEL ( technique ) ) ); if ( technique & WHAT_IF ) fprintf ( stdout, "\tWhat if analysis\n" ); fprintf ( stdout, "Difficulty score = %d\n", difficulty ); } else if ( analysis ) { if ( status < 0 ) fprintf ( stdout, "No solution possible.\n" ); else fprintf ( stdout, "Multiple solutions possible.\n" ); } } return ( status ); }