Monday 2 July 2012

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.

4 comments:

  1. Hey Chris, this is looking great! Am I able to try it out?

    ReplyDelete
    Replies
    1. As you probably realised, I still had most of the changes
      locally. I have now pushed my local branch to github
      (https://github.com/cbaines/gnome-games ). As for exactly how to build
      this, I think you can with git and jhbuild, but I am unsure of the
      exact process.

      Delete
  2. This looks good, but the last soduku is a little difficult for a human to solve. Maybe you can use the following algorithm.

    Start with a board containing the solution, and then remove one number at a time. Make sure that whenever you remove a number then a human must he able to deduce the reverse move. So if you remove the number two from a square the resulting state must allow a human to deduce that the square must contain the number two.

    Proceed like this until you cannot remove moe numbers. This approach makes sure that a human can solve the soduku, because you examine the path of solution step by step (in reverse order). Of coursee this requires you to model the way that a human deduces whn solving soduku, but Ithink that is doable.

    ReplyDelete
  3. Cool! I like where this is going.

    These puzzles so far are invalid, though: they all have more than one solution. I'm basing that on this very clever Sudoku solver: http://www.sudokuwiki.org/sudoku.htm
    (Ah, Sudoku is a crazy thing. So many variables!)

    I worked on a Sudoku generator (for a larger Sudoku project) at school last term, so I'm really interested to see your solution :)

    The usual approach is a lot of brute force. With my project, we hooked up the solver to branch around cells that accept different answers, so it eventually follows one branch to a completed puzzle. If it's validating a puzzle, it keeps following branches after that first finished one, so if it reaches a completed puzzle on _another_ branch we know the puzzle has more than one solution and is therefore invalid.

    Then, we just connect the generator to the solver so it keeps asking the solver if it has a valid puzzle. (Which is, indeed, a little inefficient).

    With that approach it can get pretty hard to generate puzzles for specific difficulty levels (or symmetrical puzzles, for that matter), so you might want to leave room for tweaking along those lines.

    Oh, the current gnome-sudoku is generating valid puzzles, too ;)

    Keep up the good work!

    ReplyDelete