Sudoku Solver

I don’t know about the rest of the world, but the part of the world I live in, Sudoku was spreading like a wildfire. It was almost to the point that you couldn’t be in a place where you didn’t see anyone playing Sudoku in one form or another. This trend seems to have died down a bit, but Sudoku still is quite popular puzzle and a good way to spend (waste?) some time exercising your brain cells.

I, on the other hand, have never played Sudoku. But that doesn’t mean that I can’t write a solver for it. It’s written in Python, and is pretty simple and straightforward. It uses a recursive backtracking to find a solution, so there is no fancy algorithm there. Still, it manages to solve most of the Sudoku puzzles I’ve encountered within a second. For some harder ones it spends about a few seconds, but it’s still within what I consider a reasonable time frame.

How to use it is pretty simple. When you download and unpack the file, you should see a file named sdksolve in the base directory. It takes a text file containing a Sudoku grid as an input file, and spits out the solution to standard output. There are some example input files under the example directory, so you can use those to see how it works. Here is an example run:

./sdksolve sample/web1.txt
Sudoku Solver by Kohei Yoshida
--------------------------------------------------------------------
Input Sudoku Grid
--------------------------------------------------------------------
5 * * 3 * * 1 * *
7 4 * 2 * * * 3 6
* * * * 1 * * 2 4
* * * 7 2 * 8 6 *
4 * 2 * * * 7 * 5
* 7 9 * 8 1 * * *
2 1 * * 7 * * * *
3 6 * * * 2 * 5 8
* * 4 * * 6 * * 1
--------------------------------------------------------------------
5 2 6 3 4 9 1 8 7
7 4 1 2 5 8 9 3 6
8 9 3 6 1 7 5 2 4
1 3 5 7 2 4 8 6 9
4 8 2 9 6 3 7 1 5
6 7 9 5 8 1 3 4 2
2 1 8 4 7 5 6 9 3
3 6 7 1 9 2 4 5 8
9 5 4 8 3 6 2 7 1
valid sudoku grid!
number of iterations: 116

So, here goes yet-another-Sudoku-solver out in the wild. Have fun! :-)