GSoC Update 4: Solving Sudoku's

In my previous post, I discussed my work on generating Sudoku puzzles. I had planned to try and improve this, and did make some small improvements, for instance adding a check at the end using the existing solver code to check for a unique solution. However I am not sure if this is a very good method.

While looking for inspiration in the python code, I noticed that its generator used the functionality of the solver to help it generate puzzles with a unique solution. So I decided to port the python Sudoku solver and rater  directly.

At first this was very hard, the data structures in the python code are quite complicated and it uses them in some quite complicated ways. This is exacerbated by pythons use of duck typing. However, once I had worked out how to run the python code from the interpreter, either by pasting in the bit I was interested in, or by just importing the file and executing whole functions, the process went much quicker. I found that looking at the data structure, then working backwards to determine its function, then working out how to replicate that, was far quicker and easier than trying to reproduce the semantics of the code exactly.

I now have written out most of the solver, and understand some of it. The code currently on github will work for simple puzzles, but I am having problems determining if the guessing and backtracking part of the solver is correct. This is because when I run the python code, I believe the slight difference in implementation or the hashing function used in the sets in this part, causes their contents to be written out in a different order when converted to an array. This in turn, causes the two solvers to pick different paths, meaning that I can't directly compare the output.

Once this issue is solved, I should be able to calculate difficulty ratings for the Sudoku's. My current plan for solving it, devised while writing this blog post, is to add a function to both solvers, to sort the arrays that differ in such a way that they don't, then compare the resulting output of the solver.

Once I have done that, I will go through the code, adding plenty of comments to explain the methodology of the solver (this is once I have worked it out for myself!).