A Software Algorithm for Solving Sudoku Puzzles

The classic Sudoku game is a number puzzle involving a grid of 81 squares, divided into into nine blocks, each containing nine squares.

French newspapers featured variations of the puzzles in the 19th century, but modern sudoku only started to become popularised in 1986 by the Japanese puzzle company Nikoli, under the name Sudoku, a contraction of the full name of the puzzle meaning single number in Japanese.

The simple rules of this game define the algorithm for solving the puzzle. Their simplicity should make a software solver possible, so I thought I would give it a try.

There are just 3 rules to Sudoku.

1. Each row must have the numbers 1-9 occurring just once.
2. Each column must have the numbers 1-9 occurring just once.
3. Each nine box sub-grid must have the numbers 1-9 occurring just once.

The puzzle setter provides a partially completed grid for the puzzler to solve. Every properly constructed puzzle has just one correct solution.

To solve a puzzle, we need to consider what needs to be done for any configuration of a board. At any time during the solving sequence, the rules are repeatedly applied until there are no more moves. At this point the puzzle is either solved, in which case there are no more possible moves, or a possible solution is tried for one of the unsolved squares. One of 2 situations will result:

• If the ‘guess’ was correct, the recursive versions of the board will result in a final solution.
• If the ‘guess’ is incorrect, then recursive versions of the board will result in a violation to the rules, no possible solution and the need to try a different value for the unsolved square.

This essentially defines a recursive software algorithm to exhaustively search for  a solution.

1. Apply the rules until they cannot generate any more solutions.
2. Guess a solution for an unknown square.
3. Recursively test this new configuration (ie, apply these rules to a copy of the new configuration.

Programmatically (in C), the resulting control code can be found in the SolveBoard function in the code C console style application below.

Sudoku.h source file

```#include <stdio.h>
#include <stdlib.h>

#define MAX_ELEMENT 9
#define SUBGRID_SIZE 3
#define EMPTY_CELL 0

#define STATUS_ERROR 0
#define STATUS_COMPLETE 1
#define STATUS_MOREMOVES 2

typedef struct _cell
{
unsigned short usValue; /* the current value */
} TCELL, *PTCELL;```

Sudoku.c source file

```#include "sudoku.h"

// Convert a mask of possible values into a printable string.
// The string is assembled in the buffer passed to the function.
{
char cBuf[10];
int i;

*pc = '\0';
for (i=0; i<MAX_ELEMENT; i++)
{
{
sprintf(cBuf, "%d ", i+1);
strcat(pc, cBuf);
}
}

return(pc);
}

void PrintBoard(PTCELL pBoard, int nPass, int nShowMask)
// Print the board passed to the function.
// Simple text format representing the puzzle board is written to stdout.
{
int i, j;
PTCELL pCell;
char cBuf[100];
int nEmptyCells = 0;

// NULL Pointer - No solution possible
if (NULL == pBoard)
{
printf("\nNo Valid solution found!\n\n");
return;
}

if (nPass == 0)
printf("\nSTARTING\n========\n\n", nPass);
else if (nPass > 0)
printf("\nPASS %02d\n=======\n\n", nPass);
else
printf("\nFIRST SOLUTION\n=============\n\n", nPass);

// Board elements
for (i=0, pCell=pBoard; i<MAX_ELEMENT; i++)
{
// do the separator if appropriate
if ((i != 0) && ((i % 3) == 0))
{
int k;

for(k=0; k<(MAX_ELEMENT/3); k++)
{
printf("-------");
printf("%s", (k!=(MAX_ELEMENT/3)-1 ? "+" : ""));
}
printf("\n");
}

// Print the board cells
for (j=0; j<MAX_ELEMENT; j++, pCell+=sizeof(TCELL))
{
printf("%s ", ((j!=0) && ((j%3)==0) ? " |" : ""));
if (pCell->usValue != EMPTY_CELL)
printf("%d", pCell->usValue);
else
{
printf(".");
nEmptyCells++;
}
}
printf("\n");
}

// If we need to show the possible values for incomplete cells, then
// print them out after the board (ie, here).
if ((nShowMask > 0) && (nEmptyCells > 0))
{
printf("\n\nPossible Values:\n");
for (i=0, pCell=pBoard; i<MAX_ELEMENT; i++)
{
for (j=0; j<MAX_ELEMENT; j++, pCell+=sizeof(TCELL))
{
if (EMPTY_CELL == pCell->usValue)
}
}
}
printf("\n");

return;
}

void InputBoard(PTCELL pBoard)
// Read the initial board position from standard input, although it can be from
// a redirected file (recommended).
// Text is organised as numbers separated by white space. No input checking is
// performed and it is assumed that MAX_ELEMENT*MAX_ELEMENT values will be
// available. Where a value is missing, the EMPTY_CELL value (0) should be
// used as a place holder.
{
int i, j;
PTCELL pCell;

// initialise first mask - each cell could can be value
for (i=0; i<MAX_ELEMENT; i++)

// now read in the values
for (i=0, pCell=pBoard; i<MAX_ELEMENT; i++)
{
for (j=0; j<MAX_ELEMENT; j++, pCell+=sizeof(TCELL))
{
scanf("%d", &k);
pCell->usValue = (unsigned short)k;
//printf("Read [%d,%d]: %d\n", i, j, pCell->usValue);
}
scanf("\n");
}
return;
}

// Count how many valid values are in each mask value.
// Counts the bits turned on and returns that count.
{
int nCount = 0;
int i;

for (i=0; i<MAX_ELEMENT; i++)
{
nCount++;
}
return (nCount);
}

// Converts a mask to a value.
// This only looks for the first value in the mask and returns the number that
// is the equivalent for that mask.
{
int i;

;

i = ((i<MAX_ELEMENT) ? i+1 : EMPTY_CELL);
return(i);
}

unsigned short CreateNewMask(PTCELL pBoard, int nRow, int nCol)
// For the given cell, work out what numeric values are valid for the cell.
// Exploits the fact that the number must be unique for each row, column
// and block of 3x3.
{
int i, j;
int nRowStart = nRow - (nRow % SUBGRID_SIZE);
int nColStart = nCol - (nCol % SUBGRID_SIZE);
PTCELL pCell;

// Note: uMask is built up as the mask of existing values (ie, the value it
// the current element CANNOT be. What is returned will be the logical
// inverse (ie, the value(s) it CAN be).

// For the value to be unique in the row, need to check all the columns
// for that row
for (j = 0, pCell = pBoard + (nRow*MAX_ELEMENT*sizeof(TCELL));
j < MAX_ELEMENT;
j++, pCell += sizeof(TCELL))
{
//printf("Row %d check, col %d, value %d\n", nRow, j, pCell->usValue);
if (EMPTY_CELL != pCell->usValue)
}

// For the value to be unique in the column, check all rows at that
// column position
for (i = 0, pCell = pBoard + (nCol*sizeof(TCELL));
i < MAX_ELEMENT;
i++, pCell += MAX_ELEMENT * sizeof(TCELL))
{
//printf("Col %d check, Row %d, value %d\n", nCol, i, pCell->usValue);
if (EMPTY_CELL != pCell->usValue)
}

// Unique in the block of 3x3
for (i = 0; i < SUBGRID_SIZE; i++)
{
for (j = 0, pCell = pBoard + ((nRowStart+i)*MAX_ELEMENT*sizeof(TCELL)) + (nColStart*sizeof(TCELL));
j < SUBGRID_SIZE;
j++, pCell += sizeof(TCELL))
{
//printf("Block [%d,%d] check [%d,%d], value %d\n", nRowStart, nColStart, i, j, pCell->usValue);
if (EMPTY_CELL != pCell->usValue)
}
}
}

int MakeMoves(PTCELL pBoard)
// For each cell on the board, check what possible values can be put in that
// cell. If there is just one number, then change the cell to that. Otherwise
// move on to the next cell.
// The number of changes is counted so that we can control (away from this
// function) how iften it should be called. There is no point calling the
// function when there were no changes made in the previous pass.
{
int nCountChanges = 0;
int i, j;
PTCELL pCell;

for (i=0, pCell=pBoard; i<MAX_ELEMENT; i++)
{
for (j=0; j<MAX_ELEMENT; j++, pCell+=sizeof(TCELL))
{
if (EMPTY_CELL == pCell->usValue) // not set yet
{
{
nCountChanges++; // one more change made
}
}
}
}
return(nCountChanges);
}

PTCELL MakeBoard(PTCELL pBoard)
// Create a new puzzle board and, if pBoard not null, copy an existing board
// to the new board.
{
#define _BOARD_SIZE (10*MAX_ELEMENT*MAX_ELEMENT*sizeof(TCELL))

PTCELL p = (PTCELL)malloc(_BOARD_SIZE);

if (p != NULL)
{
if (NULL == pBoard)
memset(p, '\0', _BOARD_SIZE);
else
memcpy(p, pBoard, _BOARD_SIZE);
}

#undef _BOARD_SIZE
return(p);
}

int BoardStatus(PTCELL pBoard)
// Return the board status to decide if there are any valid moves left or we
// have completed the board.
{
int i, j;
PTCELL pCell;

for (i=0, pCell=pBoard; i<MAX_ELEMENT; i++)
{
for (j=0; j<MAX_ELEMENT; j++, pCell+=sizeof(TCELL))
{
if (EMPTY_CELL == pCell->usValue)
{
return(STATUS_MOREMOVES);
else
return(STATUS_ERROR);
}
}
}
return (STATUS_COMPLETE);
}

PTCELL FindFirstMove(PTCELL pBoard)
// Find the first cell that has a valid move in it.
{
int i, j;
PTCELL pCell;

// now read in the values
for (i=0, pCell=pBoard; i<MAX_ELEMENT; i++)
{
for (j=0; j<MAX_ELEMENT; j++, pCell+=sizeof(TCELL))
{
{
return(pCell);
}
}
}
return(NULL);
}

PTCELL SolveBoard(PTCELL pBoard, int nLevel)
// Recursively solve the board
{
PTCELL pDoneBoard = NULL;

// First use deductive logic to place all the possible values on the board
// and keep doing this until we have not changed any cells
while (MakeMoves(pBoard) != 0)
; // do nothing

// PrintBoard(pBoard, nLevel, 0);

// Now check the board status and act accordingly
switch (BoardStatus(pBoard))
{
case STATUS_COMPLETE:
// If the board is completed, return the completed board to the caller
pDoneBoard = pBoard;
break;

case STATUS_MOREMOVES:
// If there are more moves, find the first one and test each possibility
// This is a BFI approach (exhaustive search)
{
PTCELL pNewBoard = NULL; // board copy
PTCELL pFirstMove = FindFirstMove(pBoard); // pointer to cell with first available move
PTCELL pNewCell = NULL;
int i;

// For each available move in the first available cell
for (i=0; i<MAX_ELEMENT && NULL == pDoneBoard; i++)
{
{
// Copy the board
pNewBoard = MakeBoard(pBoard);

// Make the move
pNewCell = (pFirstMove - pBoard + pNewBoard); // pointer maths
pNewCell->usValue = i+1;

//PrintBoard(pNewBoard, nLevel, 0);

// Solve it recursively
pDoneBoard = SolveBoard(pNewBoard, ++nLevel);
}
}
}
break;

default:
// No more moves or other error, return NULL to indicate dead end
free(pBoard); // This board is dead - clean up memory
pDoneBoard = NULL;
break;
}

return(pDoneBoard);
}

main()
{
int nPasses = 0;
PTCELL pBoard = MakeBoard(NULL);

// Get the initial board and print it out
InputBoard(pBoard);
PrintBoard(pBoard, nPasses++, 0);
// Solve the board
pBoard = SolveBoard(pBoard, 1);
// print the best result obtained
PrintBoard(pBoard, -1, 1);
// clean up and exit
free(pBoard);

return;
}```

An example of a very difficult to solve puzzle (with 0 denoting and empty or unknown cell), is shown below.

```0 9 0 3 0 0 0 0 0
0 6 5 0 0 0 2 0 0
4 2 0 0 0 0 0 1 0
0 0 9 0 8 0 5 0 2
0 0 0 0 4 0 0 0 0
8 0 3 0 7 0 9 0 0
0 8 0 0 0 0 0 2 6
0 0 4 0 0 0 1 3 0
0 0 0 0 0 9 0 5 0```

Running this puzzle through the software very quickly result in the following output:

```STARTING
========
. 9 . | 3 . . | . . .
. 6 5 | . . . | 2 . .
4 2 . | . . . | . 1 .
-------+-------+-------
. . 9 | . 8 . | 5 . 2
. . . | . 4 . | . . .
8 . 3 | . 7 . | 9 . .
-------+-------+-------
. 8 . | . . . | . 2 6
. . 4 | . . . | 1 3 .
. . . | . . 9 | . 5 .

FIRST SOLUTION
=============
7 9 1 | 3 5 2 | 6 8 4
3 6 5 | 8 1 4 | 2 9 7
4 2 8 | 6 9 7 | 3 1 5
-------+-------+-------
6 7 9 | 1 8 3 | 5 4 2
5 1 2 | 9 4 6 | 8 7 3
8 4 3 | 2 7 5 | 9 6 1
-------+-------+-------
9 8 7 | 5 3 1 | 4 2 6
2 5 4 | 7 6 8 | 1 3 9
1 3 6 | 4 2 9 | 7 5 8```