hirax.net::inside out::2010年05月09日

■Rubyで数独ソルバを書いてみる　

　「Rubyで数独ソルバを書く（が、動かない…）」のコードを見直したところ、なぜ動かなかったがわかりました。理由は簡単で、Arrayに2次元行列を格納しているときには、 "a=self.dup" というコードでは2次元行列のディープ・コピーがされない、ということでした。ごく初歩的な間違いです。

　そこで、コードを修正し、また、少しコード量を短くしてみたのが、下のRuby ソースです。関数は全部で3つ、「解答であれば出力し、そうでなければ探索をする」という関数 "find" と、1～9野数字で埋まっていない部分（すなわち、0が入っている部分）を、周りおよび該当行・列を見た上で候補を上げ、候補数値で埋めた上でさらに探索を再帰的に行う関数 "deepen"と、候補数値群を作りだす関数、"candidates"です。

require 'pp'
def find b # isGoal or serach (b=boad)
 ( !b.flatten.include?(0) && !pp(b) ) || deepen(b)
end

def deepen b
 l=b.flatten.index 0; x,y=[l%9, (l/9).floor]
 candidates(b,x,y).each{ |v| a=b.map{|c| c.dup};a[y][x]=v;find a}
end

def candidates b,x,y
 h,v=[3*(y/3).floor, 3*(x/3).floor]
 (1..9).to_a-b[y]-(0..8).map{|i| b[i][x]}-
     (h..h+2).map{|i|　(v..v+2).map{|j| b[j]}[i]}
end

find [[0,0,0,0,0,7,0,9,0],
[0,3,0,0,2,0,0,0,8],
[0,0,9,6,0,0,5,0,0],
[0,0,5,3,0,0,9,0,0],
[0,1,0,0,8,0,0,0,2],
[6,0,0,0,0,4,0,0,0],
[3,0,0,0,0,0,0,1,0],
[0,4,0,0,0,0,0,0,7],
[0,0,7,0,0,0,3,0,0]]

[[1, 2, 3, 4, 5, 7, 8, 9, 6],
 [4, 3, 1, 5, 2, 9, 6, 7, 8],
 [2, 7, 9, 6, 1, 3, 5, 8, 4],
 [7, 6, 5, 3, 4, 8, 9, 2, 1],
 [5, 1, 4, 9, 8, 6, 7, 3, 2],
 [6, 8, 2, 7, 9, 4, 1, 5, 3],
 [3, 5, 6, 8, 7, 2, 4, 1, 9],
 [9, 4, 8, 1, 3, 5, 2, 6, 7],
 [8, 9, 7, 2, 6, 1, 3, 4, 5]]
[[1, 2, 3, 4, 5, 7, 8, 9, 6],
 [4, 3, 1, 5, 2, 9, 6, 7, 8],
 [2, 7, 9, 6, 1, 3, 5, 8, 4],
 [7, 6, 5, 3, 4, 8, 9, 2, 1],
 [5, 1, 4, 9, 8, 6, 7, 3, 2],
 [6, 8, 2, 7, 9, 4, 1, 5, 3],
 [3, 9, 6, 8, 7, 2, 4, 1, 5],
 [9, 4, 8, 1, 3, 5, 2, 6, 7],
 [8, 5, 7, 2, 6, 1, 3, 4, 9]]
・
・
・

　コードは、およそ12行ほどですから、（「数独で見るRuby（と Mathematica）のパワーと表現力」の10行にはとてもかないませんが）比較的コンパクトと言えそうです。また、本来のアルゴリズムとは関係のない、2次元のArray要素を検査・操作する部分に行数を費やしてしまっているので、（そういったよく使いそうな）メソッドをArrayクラスに追加するライブラリを書きたくなります。

　それにしても、プログラムのアルゴリズム・コードを作り・書くという作業は、とびきり面白いパズルを解くのと同じ楽しさ（そして辛さ）を与えてくれます。ハマると、止められません…。