Simple Sudoku-Solver23 Dec 2011
I’ve always wanted to program a sudoku solver. It’s a funny little problem which is essentially a computation with a little logic mixed in. There are <a href=”http://en.wikipedia.org/wiki/Algorithmics_of_sudoku” title=wikipedia”>many ways</a> to solve a sudoku. Some of the more involved are constraint programming and stochastic search.
There are actually approaches that just fill the numbers brute force. So they start with e.g. 1 in the first cell and then try 1 again in the next cell. Because it was already used they advance the counter to 2 and go on. If none of the 9 numbers works for a cell they go back one cell and increase its counter by one. Surprisingly this approach is actually viable, although there 6.67 x 10^21 different possible grids.
As a middle way, I’ve implemented a backtracking solution that at least takes into account the rules for rows, columns and 3x3-squares. I haven’t optimized the program for speed and it can take a couple of seconds for the harder sudokus.
The main magic happens in the recursiveSolve() method:
First the program tries to derive all the numbers that follow logically from existing numbers. These “derivations” are then stored as are the different choices that are tried in each backtracking step. If a backtracking step turns out to be invalid it returns false and its calling step tries another value for the cell in question.