Sudoku is a number puzzle consisting of a 9 x 9 grid , and rules of filling the grid with numbers ranging from 1 to 9 such that  every row, column, and sub grid of size 3×3 contains exactly one instance of the digits from 1 to 9.  for example below figure shows one instance of sudoku problem having some cells already filled with some numbers from 1 to 9.

sudoko
Below is the backtracking strategy to solve the problem.
     (1) Find row, col of an unassigned cell
         If there is none, return true
     (2) For digits from 1 to 9
         if there is no conflict for digit at row,col
          assign digit to row,col and recursively try fill in rest of grid

Here no conflict means the same number is not present in current row, current column and current 3X3 sub grid.
     (3) if recursion successful, return true
     (4) if !successful, remove digit and try another
     (5) if all digits have been tried and nothing worked, return false to trigger backtracking

Here is c++ implementation of above logic:

#include<stdio.h>
#include<iostream>

#define N 9
// UNASSIGNED is used for empty cells in sudoku grid
#define UNASSIGNED 0
#define false 0
#define true 1

int SolveSudoku (int grid[N][N]);
int FindUnassignedLocation (int grid[N][N], int &row, int &col);
int NoConflicts (int grid[N][N], int row, int col, int num);
int UsedInRow (int grid[N][N], int row, int num);
int UsedInCol (int grid[N][N], int col, int num);
int UsedInBox (int grid[N][N], int boxStartRow, int boxStartCol, int num);

/*  print grid  */
void printSolution(int grid[N][N])
{
    int row,col;
    for (row = 0; row < N; row++)
    {
       for (col = 0; col < N; col++)
             printf("%d ", grid[row][col]);
        printf("\n");
    }
}

int
main ()
{
  // 0 means unassigned cells
  int grid[N][N] = {
  {0, 0, 5, 3, 0, 0, 0, 0, 0},
  {8, 0, 0, 0, 0, 0, 0, 2, 0},
  {0, 7, 0, 0, 1, 0, 5, 0, 0},
  {4, 0, 0, 0, 0, 5, 3, 0, 0},
  {0, 1, 0, 0, 7, 0, 0, 0, 6},
  {0, 0, 3, 2, 0, 0, 0, 8, 0},
  {0, 6, 0, 5, 0, 0, 0, 0, 9},
  {0, 0, 4, 0, 0, 0, 0, 3, 0},
  {0, 0, 0, 0, 0, 9, 7, 0, 0}
  };
  if (SolveSudoku (grid) == true)
    printSolution (grid);
  else
    printf ("No solution found");

  return 0;
}

/*
* Function: SolveSudoku
* ---------------------
* Takes a partially filled-in grid and attempts to assign values to all
* unassigned locations in such a way to meet the requirements for Sudoku
* solution (non-duplication across rows, columns, and boxes). The function
* operates via recursive backtracking: it finds an unassigned location with
* the grid and then considers all digits from 1 to 9 in a loop. If a digit
* is found that has no existing conflicts, tentatively assign it and recur
* to attempt to fill in rest of grid. If this was successful, the puzzle is
* solved. If not, unmake that decision and try again. If all digits have
* been examined and none worked out, return false to backtrack to previous
* decision point.
*/
int SolveSudoku (int grid[N][N])
{
  int row, col;
  if (!FindUnassignedLocation (grid, row, col))
    return true;        // success!
  int num=1;
  for (num = 1; num <= 9; num++)
    {
// consider digits 1 to 9
      if (NoConflicts (grid, row, col, num))
    {
// if looks promising,
      grid[row][col] = num;
// make tentative assignment
      if (SolveSudoku (grid))
        return true;
// recur, if success, yay!
      grid [row][col] = UNASSIGNED;
// failure, unmake & try again
    }
    }
  return false;
// this triggers backtracking
}

/*
* Function: FindUnassignedLocation
* --------------------------------
* Searches the grid to find an entry that is still unassigned. If found,
* the reference parameters row, col will be set the location that is
* unassigned, and true is returned. If no unassigned entries remain, false
* is returned.
*/
int
FindUnassignedLocation (int grid[N][N], int &row, int &col)
{
  for (row = 0; row < N; row++)
    for (col = 0; col < N; col++)
      if (grid [row][col] == UNASSIGNED)
    return true;
  return false;
}

/*
* Function: NoConflicts
* ---------------------
* Returns a intean which indicates whether it will be legal to assign
* num to the given row,col location. As assignment is legal if it that
* number is not already used in the row, col, or box*/

int NoConflicts (int grid[N][N], int row, int col, int num)
{
  return !UsedInRow (grid, row, num) && !UsedInCol (grid, col, num)
    && !UsedInBox (grid, row - row % 3, col - col % 3, num);
}

/*
* Function: UsedInRow
* -------------------
* Returns a intean which indicates whether any assigned entry
* in the specified row matches the given number.
*/
int
UsedInRow (int grid[N][N], int row, int num)
{
  int col;
  for (col = 0; col < N; col++)
    if (grid[row][col] == num)
      return true;
  return false;
}

/*
* Function: UsedInCol
* -------------------
* Returns a intean which indicates whether any assigned entry
* in the specified column matches the given number.
*/
int
UsedInCol (int grid[N][N], int col, int num)
{
  int row;
  for (row = 0; row < N; row++)
    if (grid [row][col] == num)
      return true;
  return false;
}

/*
* Function: UsedInBox
* -------------------
* Returns a intean which indicates whether any assigned entry
* within the specified 3x3 box matches the given number.
*/
int
UsedInBox (int grid[N][N], int boxStartRow, int boxStartCol, int num)
{
  int row,col;
  for (row = 0; row < 3; row++)
    for (col = 0; col < 3; col++)
      if (grid[row + boxStartRow][col + boxStartCol] == num)
    return true;
  return false;
}

Ref: http://see.stanford.edu/materials/icspacs106b/H19-RecBacktrackExamples.pdf



Related Contents to follow