182 Sudoku Generator

Description

Quiz idea provided by Lloyd Linklater

A bit over three years ago, we had a quiz to solve sudoku puzzles. Now it’s time to write a script that generates sudoku puzzles.

The output of your script should be the puzzle to solve. (Since we already have solver scripts from quiz #43, there is no need to output the solution.) In addition to generating the puzzle, you should adhere either one or the other of these two methods:

1. Reduce a generated puzzle to the fewest clues that will still suffice for finding a solution. To your output, include an estimated difficulty level.

2. Accept a command line parameter: the estimated difficulty level. Generate the puzzle such that it roughly matches that difficulty level.

The difficulty level should be a number from 1 (easiest) to 10 (hardest). Difficulty level, obviously, is somewhat subjective. However, there are various sudoku techniques that may be able to help you decide whether a puzzle is more difficult or not. Some suggested metrics include: number of clues, number of “gimmes”, number of possible solutions, cascading singletons, etc.

Summary

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), 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 – 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.


Wednesday, February 04, 2009