hirax.net::Keywords::「数独」のブログ

■Rubyで数独ソルバを書く（が、動かない…）　

　数独で見るRuby（と Mathematica）のパワーと表現力を参考に、Rubyで数独ソルバを書いたのですが、まともに動作してくれません…。もちろん、「書いた通りに動作している」わけですから、書き方が悪いわけですが、どうにもこうにも上手く書くことができません。そこで、Rubyコードをここに貼り付け、とりあえず「わかる」ようになるまで、放置しておこうと思います。

require 'pp'
class Array
  def replaceAtXY x,y,v
    a=self.dup;a[y][x]=v;a;
  end
end

def search b
  (!b.flatten.include?(0)&&!pp(b)&&exit)||(deepen b)
end

def deepen b
  l=b.flatten.index 0; x=l%9; y=(l/9).floor
  candidates(b,x,y).each{|v| 
    search b.replaceAtXY(x,y,v) }
end

def candidates b,x,y
  cand=Range.new(1,9).to_a
  ym=3*(y/3).round;xm=3*(x/3).round;
  (ym..ym+2).each {|i| (xm..xm+2).each {|j| 
    cand.delete b[i][j]} } 
  b[y].each{|v| cand.delete v}  
 # (0..8).each {|i| cand.delete b[i][x] }
  cand
end

search [[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, 4, 5, 8, 7, 6, 9, 3],
 [5, 3, 6, 1, 2, 9, 7, 4, 8],
 [7, 8, 9, 6, 3, 4, 5, 1, 2],
 [2, 4, 5, 3, 1, 6, 9, 7, 8],
 [3, 1, 7, 5, 8, 9, 4, 6, 2],
 [6, 8, 9, 2, 7, 4, 1, 3, 5],
 [3, 2, 5, 4, 6, 7, 8, 1, 9],
 [1, 4, 6, 3, 9, 9, 5, 2, 7],
 [8, 9, 7, 1, 2, 5, 3, 4, 6]]

■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クラスに追加するライブラリを書きたくなります。

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

■遺伝的アルゴリズムを使って数独を解く　

　「遺伝的アルゴリズムを使って数独を解く」

　Solving Sudoku with genetic algorithms(遺伝的アルゴリズムを使って数独を解く) というブログエントリを読んで，遺伝的アルゴリズムの入門記事として面白かったので紹介。
　

遺伝的アルゴリズムとは，生命の遺伝の仕組みを模した方法を使って解を探索する手法のこと。データを遺伝子で表現した個体を複数用意し，適応度によって個体を選択し，遺伝子に突然変異を起こしたりして解を探索してゆく。（中略）上記エントリでは，この遺伝的アルゴリズムを使って数独の問題を解く手法を紹介している。

■初心者向け「Mathematicaで書かれた数独ソルバ」　

　「Rubyで数独ソルバを書いてみる」では、Mathematicaで書かれた数独ソルバを前に、そのコードをRubyで写経してみました。

　MathematicaのコードをRubyに翻訳しようとするときに、一番最初は、Mathematicaでよく使われる「短い書き方」からでは、（私の単純で小さなあたまでは）動作の手順を見通しづらかったので、まずはじめにしたことはMathematicaのコードを冗長な記法で打ち直すことでした。私が写経がてら打ち直した、（自分向けの）冗長なMathematicaのコードが下のようになります。

　"deepen"関数は上記の"冗長"コードではずいぶんと長くなっていますが、オリジナルのコードでは下記のように実に簡潔です。

deepen[x_] := With[{pos = First@Position[x, 0]}, 
  Or @@ Map[search, (ReplacePart[x, pos -> #] & 
      /@ candidates[x, pos])]]

　一体、どういう記述の仕方であれば、自分にとって「わかりやすく・書きやすい」のだろうか？と、少し、頭を捻っているところです。