I wrote a program to solve sudoku. It was a neat project. It currently solves the most difficult sudoku puzzles I can find online in about 4.5 seconds.

The program is here and you need a Ruby interpreter to run it.

The algorithm for solving the puzzles is based off the algorithm I used for the n-queens problem back in college. The idea is that you brute force your way through all possibilities until you find one that works. This is done using recursion and an algorithm basically identical to the solution to the 8-queens puzzle.

Peter Norvig discusses his implementation in Python here.

The big difference between Norvig's implementation and mine is that he reduces the problem space before running his calculations. The general idea with sudoku is that a number can not repeat inside it's box (Norvig calls them units), on it's veritcal line or on it's horizontal line. If this is the case, then one can remove any numbers that do exist in those regions from the possible numbers tried while searching for a correct board configuration.

This basically means that instead of trying 1-9 in every board position, you try less numbers and skip the ones you know are bad choices.

The output of the program looks like this:

$ ruby ./sudoku.rb
Before solving
-------------
| 6 |1 4| 5 |
|  8|3 5|6  |
|2  |   |  1|
-------------
|8  |4 7|  6|
|  6|   |3  |
|7  |9 1|  4|
-------------
|5  |   |  2|
|  7|2 6|9  |
| 4 |5 8| 7 |
-------------
Solving...
Finished!
-------------
|963|174|258|
|178|325|649|
|254|689|731|
-------------
|821|437|596|
|496|852|317|
|735|961|824|
-------------
|589|713|462|
|317|246|985|
|642|598|173|
-------------