Backtracking – SUDOKU Solver

SUDOKU Puzzle : The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid (also called “boxes”, “blocks”, “regions”, or “sub-squares”) contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a unique solution. (Source: Wiki – http://en.wikipedia.org/wiki/Sudoku)

SUDOKU Puzzle

SUDOKU Puzzle

Approach:

Naive Approach:

The Naive way to solve it to is to generate all possible combinations of numbers from 1 to 9 to fill the empty cells. Try every configuration till the problem is solved.

Better Approach – Backtracking:

Find empty cell, find int row, col number
  If there are no empty cells, return true, problem solved.
  For number  from 1 to 9
    a) If there if is safe for digit at cell[row][col]
        fill the cell[row][col]=number and recursively try fill in rest of 	grid
    b) If recursion successful, return true
    c) Else, undo the selection, cell[row][col]=0 and try another
  If all numbers are tried and solution not found, return false

Code:


Output:

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

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

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

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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

%d bloggers like this: