# Backtracking — SUDOKU Solver

SUDOKU Puz­zle : The objec­tive is to fill a 9×9 grid with dig­its so that each col­umn, each row, and each of the nine 3×3 sub-grids that com­pose the grid (also called “boxes”, “blocks”, “regions”, or “sub-squares”) con­tains all of the dig­its from 1 to 9. The puz­zle set­ter pro­vides a par­tially com­pleted grid, which for a well-posed puz­zle has a unique solu­tion. (Source: Wiki — http://en.wikipedia.org/wiki/Sudoku)

SUDOKU Puz­zle

Approach:

Naive Approach:

The Naive way to solve it to is to gen­er­ate all pos­si­ble com­bi­na­tions of num­bers from 1 to 9 to fill the empty cells. Try every con­fig­u­ra­tion till the prob­lem is solved.

Bet­ter 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:

Out­put:

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

```

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