[QUIZ] Sudoku Generator (#182)

Discussion in 'Ruby' started by Matthew Moss, Nov 7, 2008.

  1. Matthew Moss

    Matthew Moss Guest

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

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

    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/quiz43.html
    [2]: http://www.sadmansoftware.com/sudoku/techniques.htm
     
    Matthew Moss, Nov 7, 2008
    #1
    1. Advertising

  2. Matthew Moss

    Matthew Moss Guest

    >
    > ## 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.
     
    Matthew Moss, Nov 10, 2008
    #2
    1. Advertising

  3. Matthew Moss

    Guest

    On Mon, Nov 10, 2008 at 12:25 PM, Matthew Moss <> 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]
     
    , Nov 11, 2008
    #3
  4. Matthew Moss

    Guest

    On Tue, Nov 11, 2008 at 12:36 AM, <> wrote:
    > On Mon, Nov 10, 2008 at 12:25 PM, Matthew Moss <> 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 :)
     
    , Nov 11, 2008
    #4
  5. Matthew Moss

    Guest

    On Tue, Nov 11, 2008 at 12:34 AM, <> wrote:
    > On Mon, Nov 10, 2008 at 12:25 PM, Matthew Moss <> 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/sudokumin.php

    (Though, I take no effort to ensure that the at-least 17 numbers left
    will lead to a unique solution.)
     
    , Nov 11, 2008
    #5
  6. Matthew Moss

    Kaz Kylheku Guest

    On 2008-11-11, <> 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).
     
    Kaz Kylheku, Nov 11, 2008
    #6
  7. Matthew Moss

    Guest

    On Tue, Nov 11, 2008 at 2:32 AM, Kaz Kylheku <> wrote:
    > On 2008-11-11, <> 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.)
     
    , Nov 11, 2008
    #7
  8. Matthew Moss

    Kaz Kylheku Guest

    On 2008-11-11, <> 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?
     
    Kaz Kylheku, Nov 12, 2008
    #8
  9. Matthew Moss

    Matthew Moss Guest

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

    > On 2008-11-11, <> 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.
     
    Matthew Moss, Nov 12, 2008
    #9
  10. Matthew Moss

    Marcelo Guest

    Hi Matthew,

    On Tue, Nov 11, 2008 at 10:30 PM, Matthew Moss <> wrote:

    > On Nov 11, 2008, at 10:12 PM, Kaz Kylheku wrote:
    >
    >> On 2008-11-11, <> 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
     
    Marcelo, Nov 12, 2008
    #10
  11. Matthew Moss

    Guest

    On Tue, Nov 11, 2008 at 11:12 PM, Kaz Kylheku <> wrote:
    > On 2008-11-11, <> 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)...
     
    , Nov 12, 2008
    #11
  12. Matthew Moss

    Matthew Moss Guest

    [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
     
    Matthew Moss, Nov 13, 2008
    #12
  13. Matthew Moss

    Ken Bloom Guest

    Re: [SUMMARY] Sudoku Generator (#182)

    On Thu, 13 Nov 2008 11:10:54 -0500, Matthew Moss wrote:
    > 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.


    This will punch out, on average, 44 holes.




    --
    Chanoch (Ken) Bloom. PhD candidate. Linguistic Cognition Laboratory.
    Department of Computer Science. Illinois Institute of Technology.
    http://www.iit.edu/~kbloom1/
     
    Ken Bloom, Nov 14, 2008
    #13
  14. Re: Sudoku Generator (#182)

    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 = Array.new
    s = i * 9
    (s..s+8).each{|j|
    @row_index << j
    }
    }

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

    @block_index = Array.new
    block_pattern = [0,1,2,9,10,11,18,19,20]
    (0..8).each{|i|
    @block_index = 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 == 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 Moss wrote:
    > -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
    >
    > 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/rubyquiz/>.
    >
    > 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/quiz43.html
    > [2]: http://www.sadmansoftware.com/sudoku/techniques.htm


    --
    Posted via http://www.ruby-forum.com/.
     
    Ken Nishimura, Nov 14, 2008
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Curt Hibbs
    Replies:
    13
    Views:
    182
    Robert McGovern
    Jan 7, 2005
  2. Markus Liebelt

    Using of tkextlib in ruby-182-14

    Markus Liebelt, Jan 6, 2005, in forum: Ruby
    Replies:
    5
    Views:
    454
    Hidetoshi NAGAI
    Jan 9, 2005
  3. Ruby Quiz

    [QUIZ] Animal Quiz (#15)

    Ruby Quiz, Jan 14, 2005, in forum: Ruby
    Replies:
    11
    Views:
    404
    James Edward Gray II
    Jan 18, 2005
  4. Curt Hibbs
    Replies:
    31
    Views:
    369
    Curt Hibbs
    May 1, 2005
  5. Replies:
    0
    Views:
    116
Loading...

Share This Page