**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

**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

*Related*