# 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

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

```

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

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