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[col] fill the cell[col]=number and recursively try fill in rest of grid b) If recursion successful, return true c) Else, undo the selection, cell[col]=0 and try another If all numbers are tried and solution not found, return false

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