#ident "$Id: sudoku.c,v 1.20 2009/07/30 16:58:40 pwh Exp $"
/*
* Sudoku Puzzle Solver.
*/
#include <stdio.h>
#include <stdlib.h>
#include <sys/stat.h>
#include <unistd.h>
#include <errno.h>
#include <string.h>
#include <ctype.h>
#include <curses.h> /* 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
#define bitIndex16(x) ((int)b2dLookup[((((x)&0xFFFF)*0xBCD)>>12)&0xF])
#define bit2digit(x) ((x)&&(x)==((x)&-(x))?((unsigned)(x)>0xFFFF?\
bitIndex16((x)>>16)+16:bitIndex16(x)):0)
#define digit2bit(x) ((x)>0&&(x)<33?d2bLookup[(x)-1]:0)
static char b2dLookup [] = { ( char ) 1, ( char ) 2, ( char ) 3,
( char ) 11, ( char ) 15, ( char ) 4,
( char ) 12, ( char ) 6, ( char ) 16,
( char ) 10, ( char ) 14, ( char ) 5,
( char ) 9, ( char ) 13, ( char ) 8,
( char ) 7 };
static int d2bLookup [] = { 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 countBits ( unsigned int bits )
{
bits -= ( bits >> 1 ) & 0x55555555;
bits = ( bits & 0x33333333 ) + ( ( bits >> 2 ) & 0x33333333 );
bits = ( bits + ( bits >> 4 ) ) & 0xF0F0F0F;
bits += ( bits >> 8 );
return ( ( bits + ( bits >> 16 ) ) & 0xFF );
}
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 > 0 ) 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 > 0 ) puzzle->technique |= CROSS_HATCH_2;
} else if ( progress > 0 ) 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.20 $" );
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 );
}
A special word of thanks to Eric for drawing my attention to this web page of bit twiddling hacks. I made a few changes to my bit twiddling routines based on what I learned there.
Last updated: Friday, September 04, 2009 08:42:36 AM