アドホックでブルートフォースな富豪

数独の問題を生成するプログラムを作るために、あれこれと道具をそろえてみた。9×9のマトリックスを、81個の数字を並べた1次元配列として扱う。x,y座標を与えると、それが位置する縦の列や横に列、あるいは3×3のブロックに含まれる数字を拾って返す関数を作った。これだけあれば、後は何とかなりそうな気がしている。

問題生成の方針は以下のとおり。

まず数字が全部埋まったマトリックスを作る
1つずつ数字をランダムに消していく
数字を消すたびに、消した場所に消した数字以外のものをすべて入れてみる
空欄に数字が2つ以上入るなら別解ありということで元の数字を戻す
一定回数以上、数字が消せないようになったら適当に切り上げる

ひとまずマトリックスを埋めるところをやってみた。完成形の例は以下のとおり。こういう表示をするメソッドをMatrix#to_sとして定義した。

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

同一の縦列、横列、同じ3×3のブロック内に数字の1から9が1度ずつ登場している。これが数独の特徴というか、唯一のルールらしきルール。問題を解くときも、このルールに従って後は推論を進めるだけ。

ともあれ、このマトリックスを作るのに、最初は次のような方法を考えた。

左上からランダムに数字を置いていく。横列に関しては最初に1から9までの配列を用意しておき、そこからランダムに1つずつ数字をピックアップするようにした。ピックアップする前に、縦列とブロックですでに登場している数字を取り除く。

これでうまく行くような気がしていたけど、実際にやってみるとマトリックスに次々とnilが現れた。非常に順調にマトリックスが埋まるケースもあるものの、ほとんどのケースではマトリックスの右側に来てから、もう置くべき数字がなくなってしまうということが起こってしまうようだった。

別のアプローチを考えるよりも、コンピュータにやり直しをさせたほうが手っ取り早そうだったので、nilが出た列に関しては、その列の先頭からやり直すようにした。

ところが、予想通りnilで行き詰まるケースでもやり直せば先に進む場合があった一方で、やり直してもやり直しても「手詰まり」となっているケースがあるようだった。それまでの上の列の配置によっては、にっちもさっちもいかないということが起こっているらしかった。

やっぱり別のアプローチを考えたほうがいいのかなと思いつつ、具体的な方法を考えるのが面倒だったので、手っ取り早く「行き詰まったらぜーんぶ破棄して最初からやり直し」という方針でやってみた。破棄フラグだの繰り返しフラグだのを立ててループをbreakするという何だかややこしくて汚いコードになってしまった。

ともあれ、平均して7.5回ぐらいの破棄で1つのマトリックスが生成されることが分かった。実行時間にすると、30回ぐらい破棄を繰り返す遅いケースでも1秒ちょっとだった。ほとんどのケースで一瞬で結果が戻ってくるので、まあいっかということにした。

なんともアドホックでブルートフォースなアプローチだけど、Rubyの練習問題をやっているのであって、パズルのアルゴリズムを考えたいわけじゃないんだよと誰にともなく言い訳したりしてみる。

#!/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|
  という構造
=end

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

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

    @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 to_s
    print "-"*19,"\n"
    (0..8).each{|y|
      i = 0
      yoko(y).each{|n|
        if((i % 3) == 0)
          separator = "|"
        else
          separator = " "
        end
        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.fill_matrix
#puts m