Solving Sudoku

The above algorithm would result in a sudoku where all its definites(numbers that are definitely going to be there) are fixed, but it may still have many empty positions.

But now we still have positions where there can be more than one possible numbers in it. What do we do now? We try out a number (assuming that to be the correct one) that is possible in that position and fix it there. We repeat the above procedure again until, we have a situation where NO number fits into a position or you have a completely filled SUDOKU. If we have a situation where no number fits in, it simply means that one of our assumption was wrong. So we backtrack and try out the next possible number and repeat the whole process again until we have all the positions filled in the SUDOKU grid.

This is normally how one would solve a SUDOKU (Bit of elimination and Trial and Error).

I have written a Java program that does exactly the same and Depth First Search technique is used to achieve the same.

You can find the code for the same @ https://github.com/deepakrn/Sudoku_solver

It accepts a space seperated set of numbers (9x9) (0 indicates the position is empty) from a file and writes the generated solution to another file. The above link also has sample input and output files that were generated.

My Program would give only one solution for the Sudoku, but there are chances that the problem may not have an unique solution. In that case a minor change to the program would give you all the possible solution for the problem.