Rubyで数独（ナンプレ）を解く（本当の解決編）

4月 27th, 2008 admin Posted in Ruby, 今日のコード |

前回で攻略したかと思われたナンプレですが、またもや間違った仮定で作っていたため解けない問題があるということがわかりました。（そんな問題があるって知らなかったんです。）
いくら「コードは間違ってても恥ずかしがらずに晒せ」と言ってもこう何度も間違えてたら流石に怒られるんじゃないかと不安になってきましたが、よく考えたら怒ってくれる人もいないので気にせず進めます。

今回はアルゴリズムをバックトラック法という方法を使うように変更しました。 バックトラック法というのはとにかく候補を順番に試していって矛盾が発生したら一つ戻るという方法です。矛盾が発生したらそれ以降の（矛盾を含んだ）パターンの探索は行わないので総当りと比べて効率がよく、どんなパターンであっても解を求めることができるのが特長です。

コード

PLAIN TEXT
RUBY:
  1. require 'pp'
  2. before = Time.now
  3. t = Time.now
  4. class Numpla
  5.     def initialize(sheet)
  6.         @sheet = sheet
  7.         @size = Math.sqrt(sheet.size).to_i
  8.         @side_size = Math.sqrt(@size).to_i
  9.         @possible = Array.new
  10.     end
  11.    
  12.     def solve
  13.         #初期の状態から入力候補をリストアップする。
  14.         (0...@sheet.length).each do |i|
  15.             if @sheet[i] == 0
  16.                 @possible[i] = get_possibles(get_neighbors(i))
  17.             else
  18.                 @possible[i] = []
  19.             end
  20.         end
  21.        
  22.         #探索開始
  23.         search(0)
  24.         return @sheet
  25.     end
  26.  
  27.     def search(index)
  28.         return true if index == 81
  29.        
  30.        
  31.         if @sheet[index] != 0
  32.             #０でない場合はチェックするだけ（初期から数字が割り当てられていたら）
  33.             if check(index, @sheet[index]) && search(index + 1)
  34.                 return true
  35.             end
  36.         else
  37.             #入力候補の数だけ調査する
  38.             @possible[index].each do |x|
  39.                 if check(index,x)
  40.                     @sheet[index] = x
  41.                     unless search(index + 1)
  42.                         #間違った値だった場合は取り消す
  43.                         @sheet[index] = 0
  44.                     else
  45.                         return true
  46.                     end
  47.                 end
  48.             end
  49.         end
  50.         return false
  51.     end
  52.    
  53.     #そのマスに入力できる可能性があるかどうか調べる
  54.     def check(index,x)
  55.         return  get_possibles(get_neighbors(index)).index(x)
  56.     end
  57.    
  58.     #当該マスxに関連するマスのインデックスを配列で返す
  59.     def get_neighbors(index)
  60.         get_neighbors_h(index) | get_neighbors_v(index) | get_neighbors_b(index)
  61.     end
  62.    
  63.     #水平方向のマスをリストアップ
  64.     def get_neighbors_h(index)
  65.         neighbors = Array.new
  66.         horizone = index / @size * @size
  67.         @size.times {|i|
  68.             neighbors.push(i + horizone)
  69.         }
  70.         neighbors.delete(index)
  71.         neighbors
  72.     end
  73.    
  74.     #垂直方向のマスをリストアップ
  75.     def get_neighbors_v(index)
  76.         neighbors = Array.new
  77.         vertical = index % @size
  78.         @size.times {|i|
  79.             neighbors.push(@size * i + vertical);
  80.         }
  81.         neighbors.delete(index)
  82.         neighbors
  83.     end
  84.  
  85.     #3x3のブロックのマスをリストアップ
  86.     def get_neighbors_b(x)
  87.           tf = x / @side_size * @side_size
  88.           offset = tf / @size % @side_size
  89.           fc = tf - @size * offset
  90.  
  91.           neighbors = Array.new
  92.           (0..(@side_size-1)).each do |j|
  93.             (fc+@size*j..fc+@size*j+(@side_size-1)).each do |i| neighbors.push(i) end
  94.           end
  95.           neighbors.delete(x)
  96.           neighbors
  97.     end
  98.  
  99.     #すでに確定しているマスの情報から、置ける可能性のある数字を割り出す
  100.     def get_possibles(neighbors)
  101.         possibles = Array.new
  102.         (1..@size).each{|i| possibles.push i }
  103.         neighbors.each do |i|
  104.             possibles.delete(@sheet[i])
  105.         end
  106.        
  107.         possibles
  108.     end
  109. end
  110.  
  111. sheet = Array.new
  112. sheet.concat [6,0,0,0,0,0,1,0,8]
  113. sheet.concat [0,7,0,0,0,2,3,0,0]
  114. sheet.concat [0,0,5,8,0,0,9,0,0]
  115. sheet.concat [0,4,0,9,0,0,0,0,0]
  116. sheet.concat [0,5,0,0,4,0,0,6,0]
  117. sheet.concat [0,0,1,0,5,0,0,0,4]
  118. sheet.concat [0,0,0,6,3,0,0,0,0]
  119. sheet.concat [0,2,6,0,7,9,0,3,0]
  120. sheet.concat [0,0,3,0,0,0,0,0,0]
  121.  
  122. width = 9
  123. height= 9
  124.  
  125.  
  126. foo = Numpla.new(sheet)
  127. result = foo.solve
  128.  
  129. count = 1
  130. result.each do |x|
  131.   print x
  132.   print ","
  133.   print "\n" unless count % 9> 0
  134.   count += 1
  135. end
  136.  
  137. #処理時間
  138. p Time.now - before

まとめ

１３行目付近で初期の配置から候補を絞って、それを探索に使っているのだけど、この問題の場合でいうとこれをすると約６秒、やらないと約１２秒とかなり計算時間に差が出た。今後はこの調子で計算時間を縮めたい。ちなみにこの問題での再帰の回数は14764回でした、がんばってるねー！

4 Responses to “Rubyで数独（ナンプレ）を解く（本当の解決編）”

  1. toyosystem | Rubyで数独（ナンプレ）を解く（解決編） Says:
    4月 27th, 2008 at 2:15:19

    [...] 4月 26th, 2008 admin Posted in 今日のコード, Ruby | ※このコードでは解けない問題があることがわかったのでコードを書き直しました。 新しいコードはこちら「Rubyで数独（ナンプレ）を解く（本当の解決編）」 [...]

  2. ヒロキ Says:
    4月 27th, 2008 at 3:07:47

    >よく考えたら怒ってくれる人もいないので気にせず進めます。
    僕が怒ろうか(^-^;)

    いやいや、コード晒すのは称賛に値するよ。
    最近、他でもたまに見かけるけどよくやるなぁと。
    でも晒す程、鍛えられるんだろうな。

    僕も何かやった方がいいかなぁ。

  3. toyoshi Says:
    4月 27th, 2008 at 15:33:30

    >僕が怒ろうか(^-^;)
    ほめられると伸びないタイプなので怒ってOK

    読まれるコードだと思って書くと品質が２～３割ぐらいはアップしている感じがありますね。
    これは「あのころは若かった」と振り返る準備なんだと思って続けます。

    ヒロキのコードは是非読みたいよ！

  4. toyosystem | バックトラック法 Says:
    11月 11th, 2008 at 2:19:41

    [...] ある解を求めるときに、考えられるパターンをすべて試しながら解く方法のひとつです。迷路の右手法をイメージするといいんじゃないでしょうか。パワープレイすぎてスマートさはありませんが、結局この方法が早かったり、この方法でないと解けなかったりします。以前ナンプレに挑戦したときも結局このバックトラック法を使いました。 [...]

Leave a Reply