数独ジェネレータ完成？

数独の問題ジェネレータができた気がする。「気がする」というのは、第三者が作ったソルバーで実際に問題として成立しているか検証していないから。

ともあれ、以下のコードを加えて適当にマトリックスから数字を消してみた。

def delete_one
  srand
  candidate = (0..80).to_a
  candidate.delete_if{|i| @matrix[i] == 0}
  c = candidate.pick_one
  if(uniq_solution?(c))
    @matrix[c] = 0
  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(!tate(x).include?(j) &&
       !yoko(y).include?(j) &&
       !block(which_block(x,y)).include?(j))
      return false
    end
  }
end

すでに空いているセルをのぞいて、何か数字の入っている場所をランダムにピックアップし、そこに別解があるかどうか（uniq_solution?）をチェックしている。

出てきたマトリックスを眺めていると、何となく数独として成り立っているような気もするけど、ともかくヒント数が多くて初心者問題ばかり。だいたい36〜50個ぐらいは数字が残ってしまう。一般的な数独の問題がどの程度のヒント数か知らないけど、たぶん上級問題とかだと20個前後なのではないか。数学的に検証している人たちによれば、どうも16個あたりが下限という。

-------------------
|  2 5|    1|     |
|3 9 1|    4|     |
|  8 4|  9  |2 5  |
-------------------
|  3  |5 2  |  1  |
|2 6 7|  1  |  8  |
|     |    7|4 9  |
-------------------
|1 5  |9    |  7 6|
|8    |7 6  |     |
|     |1 8 2|    3|
-------------------
ヒント数は36個。今回のプログラムでは割とよくできたほうの問題だけど解くのはやたら簡単

ランダムな間引きじゃなくて、例えばマトリックスの対称性を考えたほうがいいのかもしれない。あるいは、いったん間引きが行き詰まったら、再び何らかの方法で数字を戻したりしてかき回したほうがいいんだろうか。

ランダムなアプローチではこのへんが限界なのか、あるいは、そもそも何か考え違いをしているような気もする。うーん、考え違いの気がしてきた。もっと減らせそうか？

ともあれ、Rubyの習作としては結構楽しかったし、ほどよい課題が次々と現れていい練習になった。特にArrayの扱いでいろいろと試せた。

#!/usr/bin/ruby

=begin
= sudoku
* データ構造は
  matrix = [1,2,3,4,,,,,,,81]
  yoko_index = [[0,1,2,...8], [9,10,11...17],
  tate_index = [[0,9,18,...72], [1,10,19...73],
  block_index = [[0,1,2,9,10,11,],[3,4,5,12,],,]
* blockは
  |0|1|2|
  |3|4|5|
  |6|7|8|
  という構造で、matrix[block_index(3)
* ひょっとして class Cellでindex(x,y)あたりを抽象化するとうまくいく？
違うかなー
class Cell
  attr_accessor :x, :y, :index
  def initialize
  end
end
=end

class Matrix
  attr_accessor :yoko_index, :tate_index, :block_index, :matrix

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

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

    @tate_index = Array.new
    (0..8).each{|i|
      @tate_index[i] = Array.new
      (0..8).each{|j|
        @tate_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 yoko(x)
    @yoko_index[x].collect{|x| @matrix[x]}
  end

  def tate(x)
    @tate_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
    }
#    puts self.to_s
# 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 > 100)
          abandon_flag = true
          @matrix.fill(0)
          break
        end
        seeds = (1..9).to_a
        (0..8).each{|x|
          appear = tate(x) | block(which_block(x,y))
          n = (seeds - appear).pick_one
          @matrix[index(x,y)] = n
          seeds.delete(n)
          if((x == 8) && (!yoko(y).include?(nil)))
            repeat_flag = false
          end
#          puts self.to_s
        }
      end
      }
#    puts self.to_s
    !abandon_flag
  end

  def make_new_puzzle
    self.fill_matrix
    self.reduce
  end

  def reduce
    1000.times{
      delete_one
    }
#    self.to_s
    puts (0..80).to_a.delete_if{|i| @matrix[i] == 0}.size
  end

  def delete_one
    srand
    candidate = (0..80).to_a
    candidate.delete_if{|i| @matrix[i] == 0}
    c = candidate.pick_one
    if(uniq_solution?(c))
      @matrix[c] = 0
#      self.to_s
    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(!tate(x).include?(j) &&
         !yoko(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
      yoko(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
end

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

#m = Matrix.new
#m.make_new_puzzle
(sudoku.rb)