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:

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




Related Contents to follow