From: Matthew Moss <matt@...>
Date: 2008-11-14T01:10:54+09:00
Subject: [SUMMARY] Sudoku Generator (#182)


In this week's quiz, I ended up dropping the requirement to select or  
determine puzzle difficulty. That, I suspect, is a much harder problem  
than generating a quiz and also somewhat subjective. I even wondered  
if anyone would attempt generating _any_ Sudoku puzzles, but _brabuhr_  
presented a solution that is almost trivial. Granted, it does require  
the use of a Sudoku solver (such as sudoku-x used, or perhaps one from  
[quiz #43][1]), but I have no arguments against good reuse of code!

brabuhr begins by generating what is called the _seed puzzle_. This is  
a partially-filled puzzle that should be solveable. The code for this  
is:

     puzzle = [0] * 81

     a = (1..9).sort_by{rand}
     b = (1..9).sort_by{rand}
     c = (1..9).sort_by{rand}

     # Completely fill in the upper-left 3x3 section.
     puzzle[0..2] = a[0..2]
     puzzle[9..11] = a[3..5]
     puzzle[18..20] = a[6..8]

     # Completely fill in the center 3x3 section.
     puzzle[30..32] = b[0..2]
     puzzle[39..41] = b[3..5]
     puzzle[48..50] = b[6..8]

     # Completely fill in the lower-right 3x3 section.
     puzzle[60..62] = c[0..2]
     puzzle[69..71] = c[3..5]
     puzzle[78..80] = c[6..8]

I added in a few comments to show what parts of the 9x9 puzzle are  
being modified. As the upper-left, central, and lower-right 3x3  
sections are completely independent of one another, they can be filled  
at random without any expection of contradiction (assuming the rest of  
the puzzle is still empty, ensured here by the initial fill of zero).

Visually, the seed puzzle will look something like this (zeros have  
been replaced with blanks to improve clarity):

     +-------+-------+-------+
     | 6 8 5 |       |       |
     | 3 1 9 |       |       |
     | 7 2 4 |       |       |
     +-------+-------+-------+
     |       | 2 1 8 |       |
     |       | 4 5 6 |       |
     |       | 9 7 3 |       |
     +-------+-------+-------+
     |       |       | 2 1 8 |
     |       |       | 4 5 6 |
     |       |       | 9 7 3 |
     +-------+-------+-------+

The next step is to generate the rest of the puzzle. But since this is  
exactly what a solver does, brabuhr uses a solver to generate the  
puzzle.

     puzzle = solve(puzzle)

I'm not sure whether or not the seed has multiple solutions, but it  
doesn't really matter. This is just the first part of creating a  
puzzle for humans to solve, so as long as the solving library provides  
_some_ solution, we'll have a usable puzzle.

The final step is to take the "solved" puzzle and poke holes in it,  
enough so we have a real puzzle for humans to solve. Again, this is  
quite simple:

     64.times{puzzle[rand(81)] = 0}

This line will punch at most 64 holes into the puzzle. 64 is chosen as  
the upper limit, since there seems to be some evidence that the  
[Minimum Sudokus][2] -- puzzles uniquely solveable with the least  
number of clues -- seems to require 17 clues (and 81 - 17 = 64). It is  
quite likely, however, that there will be some overlap in the hole  
choices, and so there will likely be more than 17 clues: fewer holes  
means more clues, which means (generally) an easier puzzle.

So it is certainly possible that this generator will create puzzles  
with more than one solution. _Kaz Kylheku_ provided a suggestion to  
deal with that:

     An obvious way to improve your generator would be to call the  
solver function
     after punching a hole. (The solver function hopefully tells you  
that the
     puzzle has two or more solutions, right?) If after punching a  
hole, the puzzle
     has more than one solution, then backtrack; restore the hole, and  
punch out a
     different number.




[1]: http://rubyquiz.com/quiz43.html
[2]: http://people.csse.uwa.edu.au/gordon/sudokumin.php