Simple Sudoku Solver

Simple Sudoku Solver

Ah, the joy of alliteration. First a bit of background:

Sudoku is a kind of crossword variant with numbers, it has recently become popular in Sweden. The goal is to fill a 9x9 matrix with integers ranging from 1 to 9 so that each row, column and each of the nine 3x3 submatrices (placed so that they cover the whole matrix) contain exactly one instance of each integer in the range 1 to 9. A few (20-30) elements are given from the beginning so that only one possible solution exists.

Personally I don't like sudoku. The problem seems meant for a computer, not a human. The first (and last) time I tried a sudoku I immediately though "Hey, I'm just doing a depth first search with some smart guesses. I should let a computer do this instead.". I wasn't interested in such a solver though, so I just put the puzzle aside and did something else.

A friend recently requested a simple algorithm efficient enough to solve the hardest sudokus, so I wrote something good enough. I also figured that I might as well post it here too, in case someone is interested. The program seems to fit the Miscellaneous Java section, so I have dumped it there. The download includes both binaries and source. The program is run from the command line.

So how does the algorithm work? It is just a standard depth first search with a lock list. The lock list keeps track of which squares have what restrictions, for instance which numbers that can be placed in square (3,5). The algorithm then selects the square with the most restrictions (but without a unified value), picks a number that can be placed in the square, locks the square to that number (updating all affected squares in the lock list) and tries to solve the new matrix. The advantage with the lock list is just that the guesses are more likely to be correct, hence cutting down the search tree. E.g. the algorithm has a 50% chance of picking the right number in a square which can only have 2 different values in it instead of a lower percentage in a square that has less restrictions.

The algorithm and the code could be polished further, but it solved all the hardest sodukus I could find in an instant, so I really don't see the point.