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

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