Sudoku Generator (#182)

Ruby
1

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

The three rules of Ruby Q. 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 Q. 2 by submitting ideas as often as you can!
    Visit http://splatbang.com/rubyquiz/.

  3. Enjoy!

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

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

Sudoku Generator (#182)

Quiz idea provided by Lloyd L.

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

2

Sudoku Generator (#182)

Quiz idea provided by Lloyd L.

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.

3

On Mon, Nov 10, 2008 at 12:25 PM, Matthew M. [email protected] wrote:

Sudoku Generator (#182)

Quiz idea provided by Lloyd L.

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

:slight_smile:
#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]

4

On Tue, Nov 11, 2008 at 12:36 AM, [email protected] wrote:

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]

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

5

On Tue, Nov 11, 2008 at 12:34 AM, [email protected] wrote:

On Mon, Nov 10, 2008 at 12:25 PM, Matthew M. [email protected] wrote:

Sudoku Generator (#182)

Quiz idea provided by Lloyd L.

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/sudokumin.php

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

6

On Tue, Nov 11, 2008 at 2:32 AM, Kaz K. [email protected] wrote:

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 M. that he was afraid that no one
was interested in the quiz.)

7

On 2008-11-11, [email protected] [email protected] 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?

8

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

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.

9

On 2008-11-11, [email protected] [email protected] 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).

10

On Tue, Nov 11, 2008 at 11:12 PM, Kaz K. [email protected]
wrote:

On 2008-11-11, [email protected] [email protected] 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 :wink: Doesn’t Ruby
1.9.1 have something like:

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

Hi Matthew,

On Tue, Nov 11, 2008 at 10:30 PM, Matthew M. [email protected] wrote:

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

12

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

13

On Thu, 13 Nov 2008 11:10:54 -0500, Matthew M. wrote:

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.

This will punch out, on average, 44 holes.

14

Hi all,

Although I’m quite new to both Ruby and programming, sudoku generator
was the problem I picked to practice the basics over the last couple
of weeks. I just came across this thread by chance, so I thought I
might as well put my code here. I know nothing about algorithm or CS
stuff, so I just used a fairly naive approach.

(1) Fill a matrix using 1-9 in each row, column and block.

(2) Pick one cell, and see if punching the hole there will produce
another solution.

(3) If there’s a uniq solution, then punch out the cell. And, repeat
this until you check all the cells.

I found that (1) wasn’t as easy as I thought. You need some sort of
good way to do this, but again, this was just my practice of Ruby
programming, so I just brute forced: trial and error.

#!/usr/bin/ruby

=begin
= sudoku

  • Data structure
    matrix = [1,2,3,4,81]
    row_index = [[0,1,2,…8], [9,10,11…17],
    col_index = [[0,9,18,…72], [1,10,19…73],
    block_index = [[0,1,2,9,10,11,],[3,4,5,12,],]
  • Block numbering
    |0|1|2|
    |3|4|5|
    |6|7|8|
    =end

class Matrix
attr_accessor :row_index, :col_index, :block_index, :matrix

def initialize
@matrix = Array.new(81,0)

@row_index = Array.new
(0..8).each{|i|
  @row_index[i] = Array.new
  s = i * 9
  (s..s+8).each{|j|
    @row_index[i] << j
  }
}

@col_index = Array.new
(0..8).each{|i|
  @col_index[i] = Array.new
  (0..8).each{|j|
    @col_index[i] << (j * 9) + i
  }
}

@block_index = Array.new
block_pattern = [0,1,2,9,10,11,18,19,20]
(0..8).each{|i|
  @block_index[i] = block_pattern.map{|j|
    (j + (i / 3) * 27) + ((i % 3) * 3)}
}

end

def row(x)
@row_index[x].collect{|x| @matrix[x]}
end

def col(x)
@col_index[x].collect{|x| @matrix[x]}
end

def block(x)
@block_index[x].collect{|x| @matrix[x]}
end

def which_block(x,y)
((y / 3) * 3) + (x / 3)
end

def index(x,y)
x + (y * 9)
end

def fill_matrix
srand
100.times{|i|
break if self.try_fill_matrix
}

average 7.53 times

end

def try_fill_matrix
count = 0
abandon_flag = false

@matrix.fill(0)

(0..8).each{|y|
  repeat_flag = true
  break if(abandon_flag == true)
  until(repeat_flag == false)
    count += 1
    if (count > 20)
      abandon_flag = true
      @matrix.fill(0)
      break
    end
    seeds = (1..9).to_a
    (0..8).each{|x|
      appear = col(x) | block(which_block(x,y))
      n = (seeds - appear).pick_one
      @matrix[index(x,y)] = n
      seeds.delete(n)
      if((x == 8) && (!row(y).include?(nil)))
        repeat_flag = false
      end
    }
  end
  }
!abandon_flag

end

def make_new_puzzle
self.fill_matrix
self.reduce
end

def reduce
srand
candidate = (0…80).to_a
candidate.delete_if{|i| @matrix[i] == 0}

while(candidate.size > 0)
  c = candidate.pick_one
  if(uniq_solution?(c))
    @matrix[c] = 0
  end
  candidate.delete(c)
end

end

def reduce_by_quadruple
srand
candidate = (0…80).to_a
candidate.find{|i| ((i % 9) <= 4) && ((i / 9) <= 4)}

while(candidate.size > 0)
  c1 = candidate.pick_one
  c2 = 80 - c1
  if(uniq_solution?(c1) && (uniq_solution?(c2)))
    @matrix[c1] = @matrix[c2] = 0
  end
  candidate.delete(c1)
  candidate.delete(c2)
end

end

def uniq_solution?(n)
i = @matrix[n]
x = n % 9
y = n / 9

(1..9).to_a.delete_if{|n| n == i}.each{|j|
  if(!col(x).include?(j) &&
     !row(y).include?(j) &&
     !block(which_block(x,y)).include?(j))
    return false
  end
}

end

def to_s
print “-”*19,“\n”
(0…8).each{|y|
i = 0
row(y).each{|n|
if((i % 3) == 0)
separator = “|”
else
separator = " "
end
n = " " if n == 0
print separator, n
i += 1
}
print “|\n”
if(((y + 1) % 3) == 0)
print “-”*19,“\n”
end
}
end

def to_line
self.matrix.join
end

end

class Array
def pick_one
r = rand(self.size)
self[r]
end
end

m = Matrix.new
m.make_new_puzzle
puts m

This script seemed to generate decent sudoku puzzles like the one
below, and I went further.

| 1 | 8 | 5|
|8 7 5|3 9| |
| 3|5 7 |9 4|

|4 5 | 2| 3 |
|6 8 |1 5| |
|3 |8 6 |2 5 1|

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

Puzzles generated with this thing are not as fun, difficult to solve
at all. All the puzzles were too easy with many hints left. The
numbers of hints are between 35-50, averaging 42.7. Thinking that
maybe symmetry is a key to a good sudoku, I added this method:

def reduce_by_quadruple
srand
candidate = (0…80).to_a
candidate.find{|i| ((i % 9) <= 4) && ((i / 9) <= 4)}

while(candidate.size > 0)
c1 = candidate.pick_one
c2 = 80 - c1
if(uniq_solution?(c1) && (uniq_solution?(c2)))
@matrix[c1] = @matrix[c2] = 0
end
candidate.delete(c1)
candidate.delete(c2)
end
end

This method reduces a set of 4 cells that are in symmetric positions at
a time. The results were somewhat interesting. The numbers remaining
for each approach were:

(a) Reduce one by one : 42.7
(b) Reduce 4 cells at a time : 47.8
(c) Reduce 4 cells at a time, when that ends, reduce one by one: 42.5

You can see apparent symmetry in the puzzles generated with (b) and (c),
yet even (c) doesn’t yield any better puzzles at all.

Any given matrix filled with arbitrary numbers ends up either a
symmetric or a random puzzle with almost same amount of hints?

By the way, I was kind of sure that the puzzles generated with this
script are okay because there’s nothing complicated involved, however,
I used somebody else’s solver to check if any of the puzzles has a
uniq solution. Alas, 3-5 out of 100 puzzles, there were more than 1
solution…

I don’t know what I did wrong. I just lost interest and felt content
with the fact that I learnt many things with Ruby and had fun doing
this. And then, I found this thread, couldn’t resist.

–
Ken Nishimura, Tokyo

Matthew M. wrote:

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

The three rules of Ruby Q. 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 Q. 2 by submitting ideas as often as you can!
    Visit http://splatbang.com/rubyquiz/.

  3. Enjoy!

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

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

Sudoku Generator (#182)

Quiz idea provided by Lloyd L.

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