[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

[QUIZ] Sudoku Generator (#182

Matthew Moss

11/7/2008 3:02:00 PM

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The three rules of Ruby Quiz 2:

1. Please do not post any solutions or spoiler discussion for this
quiz until 48 hours have passed from the time on this message.

2. Support Ruby Quiz 2 by submitting ideas as often as you can!
Visit <http://splatbang.com/rub....

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem
helps everyone on Ruby Talk follow the discussion. Please reply to
the original quiz message, if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

## Sudoku Generator (#182)


_Quiz idea provided by Lloyd Linklater_

A bit over three years ago, we had a quiz to [solve sudoku puzzles]
[1]. 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][2] 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.


[1]: http://rubyquiz.com/q...
[2]: http://www.sadmansoftware.com/sudoku/tech...
13 Answers

Matthew Moss

11/10/2008 5:26:00 PM

0

>
> ## Sudoku Generator (#182)
>
>
> _Quiz idea provided by Lloyd Linklater_
>
> A bit over three years ago, we had a quiz to [solve sudoku puzzles]
> [1]. Now it's time to write a script that generates sudoku puzzles.


If the requirement to create puzzles of specified difficulty (or
determine a puzzle's difficulty) is too much, feel free to simply
generate a puzzle.

brabuhr

11/11/2008 5:34:00 AM

0

On Mon, Nov 10, 2008 at 12:25 PM, Matthew Moss <matt@moss.name> wrote:
>> ## Sudoku Generator (#182)
>>
>> _Quiz idea provided by Lloyd Linklater_
>>
>> A bit over three years ago, we had a quiz to [solve sudoku puzzles][1].
>> Now it's time to write a script that generates sudoku puzzles.
>
> If the requirement to create puzzles of specified difficulty (or determine a
> puzzle's difficulty) is too much, feel free to simply generate a puzzle.

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:

#!/usr/bin/env ruby

# so far, only sudoku-x has completed in the time I'm willing to wait :-)
#require 'small_sudoku_solver'
#require 'yet_another_sudoku_solver'
require 'sudoku-x'

require 'enumerator'

puzzle = [0] * 81

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

puzzle[0..2] = a[0..2]
puzzle[9..11] = a[3..5]
puzzle[18..20] = a[6..8]

puzzle[30..32] = b[0..2]
puzzle[39..41] = b[3..5]
puzzle[48..50] = b[6..8]

puzzle[60..62] = b[0..2]
puzzle[69..71] = b[3..5]
puzzle[78..80] = b[6..8]

puts "Seed Puzzle"
puzzle.each_slice(9){|s| p s}
puts

puzzle = solve(puzzle)

puts "Solved Puzzle"
puzzle.each_slice(9){|s| p s}
puts

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

puts "Puzzle"
puzzle.each_slice(9){|s| p s}
puts

Full output:

Seed Puzzle
[6, 8, 5, 0, 0, 0, 0, 0, 0]
[3, 1, 9, 0, 0, 0, 0, 0, 0]
[7, 2, 4, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 2, 1, 8, 0, 0, 0]
[0, 0, 0, 4, 5, 6, 0, 0, 0]
[0, 0, 0, 9, 7, 3, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 2, 1, 8]
[0, 0, 0, 0, 0, 0, 4, 5, 6]
[0, 0, 0, 0, 0, 0, 9, 7, 3]

Solved Puzzle
[6, 8, 5, 7, 3, 9, 1, 2, 4]
[3, 1, 9, 6, 2, 4, 5, 8, 7]
[7, 2, 4, 1, 8, 5, 3, 6, 9]
[9, 4, 6, 2, 1, 8, 7, 3, 5]
[1, 3, 7, 4, 5, 6, 8, 9, 2]
[2, 5, 8, 9, 7, 3, 6, 4, 1]
[4, 9, 3, 5, 6, 7, 2, 1, 8]
[8, 7, 1, 3, 9, 2, 4, 5, 6]
[5, 6, 2, 8, 4, 1, 9, 7, 3]

Puzzle
[0, 8, 5, 0, 3, 9, 0, 2, 0]
[0, 0, 0, 6, 0, 0, 0, 0, 0]
[0, 0, 4, 1, 0, 5, 3, 0, 0]
[0, 0, 0, 2, 0, 8, 0, 0, 5]
[0, 3, 0, 0, 0, 6, 0, 9, 2]
[2, 5, 8, 0, 0, 0, 0, 0, 0]
[4, 9, 0, 5, 0, 0, 2, 0, 0]
[0, 7, 0, 3, 9, 0, 4, 0, 6]
[0, 0, 2, 8, 4, 0, 9, 7, 0]

Some more puzzles:

[3, 0, 0, 9, 0, 0, 0, 8, 0]
[0, 7, 4, 0, 3, 0, 0, 0, 0]
[0, 8, 0, 0, 6, 5, 1, 0, 0]
[0, 4, 0, 3, 1, 0, 0, 0, 0]
[0, 0, 0, 4, 9, 7, 0, 0, 0]
[7, 0, 9, 2, 0, 0, 0, 0, 3]
[4, 5, 7, 6, 2, 9, 0, 0, 8]
[6, 0, 0, 0, 8, 3, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 0, 6]

[6, 0, 0, 0, 3, 0, 0, 0, 8]
[0, 8, 4, 0, 0, 7, 2, 0, 9]
[0, 0, 2, 5, 0, 0, 0, 0, 7]
[0, 0, 6, 0, 0, 0, 5, 0, 0]
[0, 0, 0, 0, 4, 1, 0, 8, 0]
[0, 0, 1, 0, 7, 0, 0, 0, 6]
[0, 0, 0, 0, 1, 6, 0, 0, 3]
[0, 0, 0, 0, 5, 0, 0, 4, 1]
[0, 6, 3, 4, 0, 2, 8, 0, 0]

[4, 8, 1, 0, 0, 0, 9, 0, 0]
[0, 0, 6, 0, 0, 0, 0, 0, 4]
[0, 0, 5, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 8, 5, 0, 0, 0, 0]
[8, 1, 9, 0, 3, 6, 5, 0, 0]
[5, 6, 0, 0, 0, 1, 0, 0, 8]
[1, 0, 0, 0, 0, 0, 8, 0, 0]
[7, 0, 2, 0, 0, 0, 4, 3, 0]
[0, 4, 0, 3, 0, 0, 2, 9, 0]

brabuhr

11/11/2008 5:38:00 AM

0

On Tue, Nov 11, 2008 at 12:36 AM, <brabuhr@gmail.com> wrote:
> On Mon, Nov 10, 2008 at 12:25 PM, Matthew Moss <matt@moss.name> wrote:
>>> ## Sudoku Generator (#182)
>>>
>>> _Quiz idea provided by Lloyd Linklater_
>
> a = (1..9).sort_by{rand}
> b = (1..9).sort_by{rand}
> c = (1..9).sort_by{rand}
>
> puzzle[0..2] = a[0..2]
> puzzle[9..11] = a[3..5]
> puzzle[18..20] = a[6..8]
>
> puzzle[30..32] = b[0..2]
> puzzle[39..41] = b[3..5]
> puzzle[48..50] = b[6..8]
>
> puzzle[60..62] = b[0..2]
> puzzle[69..71] = b[3..5]
> puzzle[78..80] = b[6..8]

:-( obviously I meant to use a,b,c not a,b,b when seeding the board;
that might make the puzzles slightly more interesting :-)

brabuhr

11/11/2008 6:13:00 AM

0

On Tue, Nov 11, 2008 at 12:34 AM, <brabuhr@gmail.com> wrote:
> On Mon, Nov 10, 2008 at 12:25 PM, Matthew Moss <matt@moss.name> wrote:
>>> ## Sudoku Generator (#182)
>>>
>>> _Quiz idea provided by Lloyd Linklater_
>
> 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}

Hmm, changed that while I was messing around with it, originally:

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

Since, it appears that any (unique) Sudoku puzzle must have at least
17 given numbers:

http://people.csse.uwa.edu.au/gordon/sud...

(Though, I take no effort to ensure that the at-least 17 numbers left
will lead to a unique solution.)

Kaz Kylheku

11/11/2008 7:33:00 AM

0

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

brabuhr

11/11/2008 2:50:00 PM

0

On Tue, Nov 11, 2008 at 2:32 AM, Kaz Kylheku <kkylheku@gmail.com> wrote:
> 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}
>
> [...]
>
> 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.

Yes, that was my next step, but I never got around to it this past
weekend. The third solver 'sudoku-x' apparently can report multiple
solutions (the others are too brute-force to populate the blank board
in any reasonable time on any hardware I have). Keeping with the
random theme, the next planned iteration was like:

64 times
pick a random spot
skip it if it is already a hole
poke a hole and pass the puzzle to the solver
if
the solver finds more than one solution
put the number back and try another
the solver finds one solution
leave the number out and try another

And the next iteration would replace 64 with a number calculated from
difficulty level. (I wasn't going to post at all, but I was afraid
from the second post from Matthew Moss that he was afraid that no one
was interested in the quiz.)

Kaz Kylheku

11/12/2008 4:13:00 AM

0

On 2008-11-11, brabuhr@gmail.com <brabuhr@gmail.com> wrote:
> 64 times
> pick a random spot
> skip it if it is already a hole

Is it really so difficult to make a sequence of integers from 0 to 80, scramble
its order (e.g. using the Knuth random exchange method) and then take
successive elements from this sequence as the locations on the Sudoku
board?

Matthew Moss

11/12/2008 4:31:00 AM

0


On Nov 11, 2008, at 10:12 PM, Kaz Kylheku wrote:

> On 2008-11-11, brabuhr@gmail.com <brabuhr@gmail.com> wrote:
>> 64 times
>> pick a random spot
>> skip it if it is already a hole
>
> Is it really so difficult to make a sequence of integers from 0 to
> 80, scramble
> its order (e.g. using the Knuth random exchange method) and then take
> successive elements from this sequence as the locations on the Sudoku
> board?
>

That alone does not a Sudoku make. Unless you've got some other
criteria in mind that you don't mention, that's just a 9x9 grid of
random numbers.

Marcelo

11/12/2008 1:32:00 PM

0

Hi Matthew,

On Tue, Nov 11, 2008 at 10:30 PM, Matthew Moss <matt@moss.name> wrote:

> On Nov 11, 2008, at 10:12 PM, Kaz Kylheku wrote:
>
>> On 2008-11-11, brabuhr@gmail.com <brabuhr@gmail.com> wrote:
>>>
>>> 64 times
>>> pick a random spot
>>> skip it if it is already a hole
>>
>> Is it really so difficult to make a sequence of integers from
>> 0 to 80, scramble its order (e.g. using the Knuth random
>> exchange method) and then take successive elements from this
>> sequence as the locations on the Sudoku board?
>
> That alone does not a Sudoku make. Unless you've got some other
> criteria in mind that you don't mention, that's just a 9x9 grid
> of random numbers.

I think Kaz meant that you can do without the ugly "pick a
random spot... darn! I had already looked at this one!" IOW,
shuffle a list of all the numbers between 0 and 80, and pick a
random amount of them (1 .. 64) that are removed in order to
generate the sudoku puzzle.

It's an interesting question whether or not this generates
better puzzles.

Marcelo

brabuhr

11/12/2008 2:54:00 PM

0

On Tue, Nov 11, 2008 at 11:12 PM, Kaz Kylheku <kkylheku@gmail.com> wrote:
> On 2008-11-11, brabuhr@gmail.com <brabuhr@gmail.com> wrote:
>> 64 times
>> pick a random spot
>> skip it if it is already a hole
>
> Is it really so difficult to make a sequence of integers from 0 to 80, scramble
> its order (e.g. using the Knuth random exchange method) and then take
> successive elements from this sequence as the locations on the Sudoku
> board?

No, it's not difficult at all. (But maybe less fun ;-) Doesn't Ruby
1.9.1 have something like:

(0..80).sample(n)...