From: Kaz Kylheku <kkylheku@...>
Date: 2008-11-11T16:32:31+09:00
Subject: Re: [QUIZ] Sudoku Generator (#182)

On 2008-11-11, brabuhr@gmail.com <brabuhr@gmail.com> wrote:
> I haven't take the time to look at difficulty level, but have a very
> naive generator; the basic idea is to generate a puzzle using a sudoku
> solver and then punch some random holes in it:

[...]

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

In the very unlikely event that all 72 holes go to unique locations, you will
end up with an improper puzzle (more than one solution), because it will have
only 9 givens. 

The minimum number of givens for a standard 9x9 Sudoku is believed to be 17.

When this is possible, the givens can't be in any randomly chosen 17 places,
either.

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.

As a rough estimate of difficulty level, you could use the number of givens.
I.e.  if you manage to produce a puzzle with only 17 givens this way, that
could be assigned the highest difficulty level. (Though difficulty doesn't
exactly correlate with the number of givens).