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

GSoC Update 3: Sudoku Generation

I have been quite busy since my last report, both with GSoC stuff, and with moving house. I have now begun working on generating Sudoku puzzles, up until now, the sudoku-vala branch has had a hardcoded sudoku. The existing code is also much less in this area, compared with the functional interface, this was the extent of the generator:

   public static SudokuGame generate (string difficulty)  
   {  
     var x = "";  
     for (var row = 0; row < 9; row++)  
     {  
       for (var col = 0; col < 9; col++)  
       {  
         var z = Random.int_range (0, 27);  
         if (z < 9)  
           x += "%d".printf (z);  
         else  
           x += ".";  
       }  
     }  
   
     return new SudokuGame.from_string (x);  
   }  

So, I began with the python code, working out how it worked, and then replicating that in Vala. To my current understanding, the current Gnome Sudoku game first creates a complete board (with all the cells filled in), and then selects cells to be part of the puzzle. It can do the cell selection in different ways, the two ways I have currently looked at and replicated are make_puzzle_by_boxes, and make_symmetric_puzzle.

The python code uses sets of coordinates, this made it slightly harder to translate as Vala can replicate some of this behaviour but its syntactically more expensive. So I chose to try and understand the methodology behind the code, and write in a style I believe more suits Vala.

The other missing bit from the Vala code concerning Sudoku generation was the solver, the current Vala solver doesn't have any publicly accessible methods for doing solving, it can only give tell you if the puzzle has 0, 1 or more than 1 solution. However it does this with a recursive (calls itself) method. I adapted this by introducing some random number generation, and placed it in the generator class to generate the full boards. 

Making Symmetrical Sudoku's

I was a bit confused by the methodology in the python code, it seemed to involve two loops, whereas I chose to implement it using only one. My code, generates a filled and blank board. Then picks a cell on the grid randomly, checks if its been filled yet, and if not inserts the corresponding value in filled grid, then it works out the coordinate of the reflection in the bottom left to top right diagonal, and does the same. It then repeats the steps in the previous sentence until the new board (that began blank) has enough filled cells.

Sudoku generated using the symmetrical method described above.

Making Sudoku's by Box

This is the second and slightly more complicated of the methods in the python code to produce Sudoku's. It generates puzzles that have a certain clue skew (unevenness).

Skew of 0

Skew of 0.5

Skew of 1

This works by picking a number of cells from each box (the large 3 by 3 areas), then picking that many cells from within each box.

Next

At the moment I have done some work on unifying the above methods, I aim to finish that off soon. I also would like to be able to produce symmetrical Sudoku's with different lines of symmetry (the code is limited to one in particular at the moment).

The python generation code generates puzzles, then using its quite complicated solver, solves them to generate some numbers (about 5) regarding the steps it took to solve them. These are then used to generate its difficulty score.

I am hoping that by tweaking the skew in the second method I describe, I hope that it will affect the difficulty of the resulting Sudoku. But I wont be able to evaluate this until I implement the solver.