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.