昨日のエントリで書いた，8パズルでの「アタマノタイソウ」問題，解くプログラムをRubyで書いてみました．
#!/usr/bin/env ruby # -*- coding: utf-8 -*- class PuzzleSolver def initialize(opt = {}) @width = opt[:width] || 4 @init = opt[:init] || "123456789ABCDEF*" @goal = opt[:goal] || "123456789AFBDEC*" @blank = opt[:blank] || "*" @size = @init.split(//).length end def search @pred_h = Hash.new # state => previous state @queue = [@goal] # states to be searched @count_search = 0 # number of states picked out until @queue.empty? state = @queue.shift @count_search += 1 puts "get(#{@count_search}): #{state}" if $DEBUG if state == @init return true # positively solved end ary = state.split(//) ary.each_with_index do |c, i| next if c != @blank x = i % @width y = (i - x) / @width new_state(ary, x, y, :left) new_state(ary, x, y, :right) new_state(ary, x, y, :up) new_state(ary, x, y, :down) end end false # negatively solved end def new_state(state_ary, x, y, dir) case dir when :left return false if x <= 0 x2, y2 = x - 1, y when :right return false if x >= @width - 1 x2, y2 = x + 1, y when :up return false if y <= 0 x2, y2 = x, y - 1 when :down return false if x + (y + 1) * @width >= @size x2, y2 = x, y + 1 else return false end ary = state_ary.dup state = ary.join pos1 = x + y * @width pos2 = x2 + y2 * @width ary[pos1], ary[pos2] = ary[pos2], ary[pos1] state2 = ary.join if @pred_h.key?(state2) return false end puts "new: #{state2}" if $DEBUG @pred_h[state2] = state @queue << state2 true end def print_field(str) ary = str.split(//) until ary.empty? puts ary[0, @width].join ary[0, @width] = [] end puts end def trace state = @init print_field(state) while state != @goal && @pred_h.key?(state) state = @pred_h[state] print_field(state) end end def start puts "[init]" print_field(@init) puts "[goal]" print_field(@goal) if search puts "Answer Found!"; puts trace else puts "No answer" end end end if __FILE__ == $0 # PuzzleSolver.new.start # PuzzleSolver.new(:width => 2, :blank => "*", :init => "123*", :goal => "231*").start PuzzleSolver.new(:width => 3, :blank => "＊", :init => "ウアタソ＊マイタノ", :goal => "ソウアイ＊タタノマ").start # PuzzleSolver.new(:width => 3, :blank => "＊", :init => "アタマノタイソウ＊", :goal => "アタマノタイウソ＊").start # PuzzleSolver.new(:width => 3, :blank => "＊", :init => "ウアタソ＊マイセノ", :goal => "ソウアイ＊タセノマ").start end
いつものようにRuby 1.8，1.9両対応です．文字コードはUTF-8（Emacsならutf-8-unix）とし，Ruby 1.8で実行する際には-Kuオプションが必要です．出力はこうなります．
[init] ウアタ ソ＊マ イタノ [goal] ソウア イ＊タ タノマ Answer Found! ウアタ ソ＊マ イタノ ウアタ ソタマ イ＊ノ ウアタ ソタマ イノ＊ ウアタ ソタ＊ イノマ ウア＊ ソタタ イノマ ウ＊ア ソタタ イノマ ＊ウア ソタタ イノマ ソウア ＊タタ イノマ ソウア タ＊タ イノマ ソウア タタ＊ イノマ ソウア タタマ イノ＊ ソウア タタマ イ＊ノ ソウア タ＊マ イタノ ソウア ＊タマ イタノ ソウア イタマ ＊タノ ソウア イタマ タ＊ノ ソウア イタマ タノ＊ ソウア イタ＊ タノマ ソウア イ＊タ タノマ
2つの「タ」が交換されていることも確認できます．
プログラムは，一言でいうと「幅優先探索」です．これは移動回数が最小となる解がほしいからです．PuzzleSolverクラスのインスタンス変数@queueは，Arrayのオブジェクトですが，<< すなわちpushで値を入れ，shiftで先頭の値を取り出すという，キューにしています．
@pred_hは，ある状態をキー，遷移可能な次の状態を値とする，ハッシュです．この種のパズルは対称性，すなわち「xの状態からyの状態へ行けるなら，yからxへも行ける」という性質がありますが，最短となる解を求めたいので，ゴールに近づくほうのみを格納します．そして，ゴールすなわちインスタンス変数@goalから始めて，@initにたどり着けるか@queueが空っぽになるまで繰り返し処理をします．解が見つかれば，@init, @pred_h[ @init ], @pred_h[ @pred_h[ @init ] ], ...を順に見て@goalになるまで，それぞれ整形し出力しています．
少々最適でないコードをしているのは，Ruby 1.8/1.9対応*1のほか，盤面の状態の数が多くなっても効率良く処理できるよう，インスタンスをなるべく多く作らないようにしているためです．
コードの中の
PuzzleSolver.new(:width => 3, :blank => "＊", :init => "ウアタソ＊マイタノ", :goal => "ソウアイ＊タタノマ").start
で，列数（幅），初期配置，目標とする配置を指定します．行数（高さ）は，初期配置を列数で割れば求められます．ということで，2×2でも，4×4でも，適用可能ですが，処理時間は一切考慮していません．
*1:例えば，メソッドprint_fieldの中で，「ary[0, @width]」を2度使用している箇所は，「puts ary.shift(@width).join」としたいところです．しかしhttp://doc.okkez.net/を起点にリファレンスを見ると，Array#shiftに引数を持てるのは1.8.7からとなっています．なので不採用としました．
