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! :-)

Constraint parsing bug

One avid user of my Calc Solver from Belgium found a rather serious, and a little embarrassing bug and brought it to my attention (thank you, Ludovic!). It was the way I convert a constraint formula from the spreadsheet format to the internal model, which utterly fails to do it correctly when the left-hand-side cell contains a constant value. I need to fix this sooner rather than later since I believe this is rather a severe bug that should not be left in the code knowingly (now that I know it…).

So, I’ll spend my next available time trying to fix it, and put it into ooo-build first. Then bring the fix to scsolver02 cws afterwards. I’ll have to hold off the upstream integration work for now.