Algo#15: Sudoku solver

To solve given Sudoku of any level, by back tracking method, we have to try each possible combinations until it gets solved. We have to take care about given filled numbers which we can not modified while doing back track.

First thing we need here is, way to check whether we can put chosen number at particular location or not. We can put number only if satisfy following criteria.
1. It should be unique in its row.
2. It should be unique in its column.
3. It should be unique in its region (3 * 3) box.

Lets say we made some function called isValid() which tell check above constraint for our move. Now we are ready to take up our back tracking algorithm.

Following is simple recursive algorithm for Solving given Sudoku.

Step 1: If we have filled all position without violation of any constraint, then we are done.
Step 2: If current location (filling row by row, left to right) is fixed location, we can not modified it, go ahead and fill remaining location recursively.
Step 3: Try every element from 1 to 9 one by one and check if remaining Sudoku can be solved recursively. If we are out of all nine numbers, and Sudoku doesn't yet solved then Sudoku is unsolvable.

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.