A Software Algorithm for Solving Sudoku Puzzles

Soduko Puzzle
Soduko Puzzle

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

#define EMPTY_MASK 0
#define SetMask(i) ((unsigned short)(1<<(i)))
#define ResetMask(i) ((unsigned short)~(1<<(i)))

typedef struct _cell
{
  unsigned short usValue; /* the current value */
  unsigned short usMask; /* mask of possible values */
} TCELL, *PTCELL;

Sudoku.c source file

#include "sudoku.h"

char* MaskValueString(char *pc, unsigned short uMask)
// 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++)
  {
    if (EMPTY_MASK != (SetMask(i) & uMask))
    {
      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;
  }

  // Header
  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("[%d,%d]: %s\n", i, j, MaskValueString(cBuf, pCell->usMask));
      }
    }
  }
  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;
  unsigned short usInitMask = EMPTY_MASK;
  PTCELL pCell;
 
  // initialise first mask - each cell could can be value
  for (i=0; i<MAX_ELEMENT; i++)
    usInitMask |= SetMask(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;
      pCell->usMask = ((k==0) ? usInitMask : EMPTY_MASK);
      //printf("Read [%d,%d]: %d\n", i, j, pCell->usValue);
    }
    scanf("\n");
  }
  return;
}

int CountMask(unsigned short uMask)
// 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++)
  {
    if (EMPTY_MASK != (SetMask(i) & uMask))
    nCount++;
  }
 return (nCount);
}

int Mask2Value(unsigned short uMask)
// 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;
 
  for (i=0; (i<MAX_ELEMENT) && (EMPTY_MASK == (SetMask(i) & uMask)); 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;

  unsigned short uMask = 0;
  // 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)
      uMask |= SetMask(pCell->usValue-1);
  }

  // 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)
      uMask |= SetMask(pCell->usValue-1);
  }

  // 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)
      uMask |= SetMask(pCell->usValue-1);
  }
 }
  return(~uMask);
}

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
      {
        pCell->usMask = CreateNewMask(pBoard, i, j); // check possibles
        //printf("New Mask [%d,%d]: 0x%x (%d)\n", i, j, pCell->usMask, CountMask(pCell->usMask));
        if (CountMask(pCell->usMask) == 1) // we found the value!
        {
          //printf("New Value [%d,%d]: %d\n", i, j, Mask2Value(pCell->usMask));
          pCell->usValue = (unsigned short)Mask2Value(pCell->usMask);
          pCell->usMask = EMPTY_MASK;
          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)
      {
        if (EMPTY_MASK != pCell->usMask)
          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))
    {
      //printf("Checking [%d,%d]: Value %d, Mask 0x%x\n", i, j, pCell->usValue, pCell->usMask);
      if ((EMPTY_CELL == pCell->usValue) && (EMPTY_MASK != pCell->usMask))
      {
        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++)
      {
        if ((SetMask(i) & pFirstMove->usMask) != 0)
        {
          // Copy the board
          pNewBoard = MakeBoard(pBoard);
 
          // Make the move
          pNewCell = (pFirstMove - pBoard + pNewBoard); // pointer maths
          pNewCell->usValue = i+1;
          pNewCell->usMask = EMPTY_MASK;
 
         //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
Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s