わさっきhb

大学(教育研究)とか ,親馬鹿とか,和歌山とか,とか,とか.

アタマノタイソウ問題を解く

昨日のエントリで書いた,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-8Emacsなら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からとなっています.なので不採用としました.