# Backtracking – SUDOKU Solver

Given a sudoku problem or partially filled sudoku, write a program to solve the sudoku.

What is Sudoku: Sudoku is a puzzle where a partially completed grid is given and objective is to fill a 9×9 grid with digits with conditions below –

• Each column contains all of the digits from 1 to 9 only once.
• Each row contains all of the digits from 1 to 9 only once.
• Each of the nine 3×3 sub-grid contains all of the digits from 1 to 9 only once.

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

Complete 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