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