箱入り娘パズルをRubyで解く
「Rubyによる情報科学入門」（久野靖著）の第10章にあった箱入り娘パズルをやってみた。スライドパズルの一種。掲載されているコードをそのまま打ち込むのも芸がないし、例によって、久野先生のコードが、どうもCっぽく見えることもあって、自分で書き直してみた。
事前に状態空間全体をツリーやグラフとして構成するのが現実的でない、組み合わせの爆発が起こるような問題では、状態を順次作りつつダイナミックに探索を行う。このとき深さ優先と幅優先の2つの戦略がある。
ある状態と隣接する状態を作ってスタックに積み、これを上から取り出して探索すれば、深さ優先になる。逆にキューに突っ込んでFIFOで処理すれば、幅優先になる。RubyのArrayはpopもshiftもできるスタック兼キューだったりするので、コード中の1カ所で「stack.pop」を「stack.shift」に変えるだけで幅優先の探索もできる。
Koma = Struct.new(:width, :height, :name, :y, :x) INIT_STATE = [Koma.new(2, 2, "M", 0, 1), Koma.new(1, 2, "v", 0, 0), Koma.new(1, 2, "v", 0, 3), Koma.new(1, 2, "v", 2, 0), Koma.new(1, 2, "v", 2, 3), Koma.new(2, 1, "w", 2, 1), Koma.new(1, 1, "s", 3, 1), Koma.new(1, 1, "s", 3, 2), Koma.new(1, 1, "s", 4, 0), Koma.new(1, 1, "s", 4, 3),] class State attr_accessor :koma @@visited = {} def initialize(s=nil) @prev = s if @prev == nil @koma = INIT_STATE else @koma = Marshal.load(Marshal.dump(s.koma)) end @b = Array.new(5) do Array.new(4, -1) end place end def place @b.each{|y| y.fill(-1)} @koma.each_with_index do |k, i| k.width.times do |w| k.height.times do |h| @b[k.y + h][k.x + w] = i end end end end def isgoal? musume = @koma.find{|k| k.name == "M"} return musume.x == 1 && musume.y == 3 end def visited @@visited[self.to_s] = true end def visited? @@visited[self.to_s] == true end def to_s str = "-------\n" @b.each do |line| line.each do |num| if num == -1 then str += ". " else # str += @koma[num].name + " " str += num.to_s + " " end end str += "\n" end return str end def generate_moves @koma.each_with_index do |k, i| [[-1, 0], [1, 0], [0, -1], [0, 1]].each do |dy, dx| if ((0 > k.y + dy || 0 > k.x + dx) || ((4 < k.y + k.height - 1 + dy) || (3 < k.x + k.width - 1 + dx))) then next end if movable?(i, dy, dx) then s2 = State.new(self) s2.koma[i].x += dx; s2.koma[i].y += dy s2.place yield s2 end end end end def movable?(i, dy, dx) y = @koma[i].y + dy x = @koma[i].x + dx @koma[i].height.times do |h| @koma[i].width.times do |w| num = @b[y + h][x + w] if (num != -1) && (num != i) then return false end end end true end def traceback if @prev != nil then @prev.traceback end puts self.to_s end end # main stack = [] checked = 0 s = State.new(nil) stack << s puts "initial state:" puts s.to_s puts Thread.new do |t| while true sleep 3 print "checked: #{checked}\n" print "stacked: #{stack.size}\n" print "sample :\n#{stack.last.to_s}\n" end end while !(stack.empty?) do s = stack.pop s.visited s.generate_moves do |s2| if s2.isgoal? then print "found the answer:\n", s2.to_s print "process:\n" s2.traceback exit elsif !s2.visited? then stack << s2 checked += 1 end end end t.kill print "checked #{checked} states\n"
キモは一番最後のwhileループで、
- 初期状態を作ってスタックに積む
- スタックが空でない限りwhileを回す
- スタックからpop
- popした状態をチェック済みマーク
- 隣接状態を作って、それらがゴールか調べる
- ゴールでなく、かつチェック済みでないならスタックに積む
というのが状態空間探索の基本動作。
ある局面でのコマの配置状態を保持するStateクラスを作ったのはいいけど、何でもかんでもこのクラスに突っ込んでしまったのがいいのか悪いのかよく分からない。コマの配置を実際の盤面でのデータ表現にマップさせるようなことは、別のクラスにしたほうが良かったのか、とか。しかし分けるほど別じゃない。ていうか、クラスとか大げさなのか。
これを実行すると所要時間22分、700MBほどのメモリを消費して確かに解を発見したように見える。検査した状態は80万ぐらい。終了時にスタックに積まれた状態は40万ぐらい。組み合わせパズルの状態数を甘く見積もっていたらしい。
最後はエラーで終わってしまった。単方向連結リストとして記録しておいた手順を、初期状態から逆順に表示するために、最後に再起（Stack#traceback）しているところで、stack level too deepが出て落ちてしまった。どうも8000手順ぐらいで解けているらしい。あいや、8000手順さかのぼったところでエラーが出てるだけで、実際はもっと深い可能性もあるのか。またもう1度20分も走らせる気がしない……。
どっちみち視認で正解かどうかを確認するのは非現実的だし、まあいいかという感じ。結果を見ると確かに娘はゴールにたどり着いている。
:
:
checked: 818500
stacked: 421515
sample :
-------
3 2 . 6
3 2 4 1
8 7 4 1
. 9 0 0
5 5 0 0
checked: 819544
stacked: 422014
sample :
-------
2 9 8 1
2 7 6 1
. 3 0 0
4 3 0 0
4 5 5 .
checked: 820358
stacked: 422418
sample :
-------
4 6 . 1
4 9 7 1
3 2 . 8
3 2 0 0
5 5 0 0
found the answer:
-------
7 6 4 1
2 3 4 1
2 3 5 5
. 0 0 9
. 0 0 8
process:
hako.rb:105:in `traceback': stack level too deep (SystemStackError)
from hako.rb:105:in `traceback'
from hako.rb:105:in `traceback'
from hako.rb:105:in `traceback'
from hako.rb:105:in `traceback'
from hako.rb:105:in `traceback'
from hako.rb:105:in `traceback'
from hako.rb:105:in `traceback'
from hako.rb:105:in `traceback'
... 8719 levels...
from hako.rb:105:in `traceback'
from hako.rb:137:in `block in <main>'
from hako.rb:133:in `each'
from hako.rb:133:in `<main>'実際にはこのパズル、最短だと81手順で解けるらしい。むかし自分でやった感覚だと、もっと短い気もするけど、それは、ある種の一連の操作を人間は一塊に認識するからかもしれない。
途中経過を3秒おきに表示するようにしているのだけど、これが見ていると結構おもしろい。10分ほど経過したとき、明らかに「娘」のコマがゴール付近をうろついていて、もう少し！ もう少し！ とドキドキした。結局、「番頭」が邪魔になって「娘」は外に出られなかったりして、ああ、なるほど、その枝方向には解がなかったのかな、とか。
さらに幅優先でやってみているけど、一体どのぐらい時間がかかるのか分からない。80手程度で正解にたどり着けるのだとすれば、案外たいしたことはないのかもしれないように思ったけど、数時間かかって100万状態をチェックした今、娘のコマは微動だにしていない……。下のほうでゴチャゴチャとコマを動かして似たような（しかし同一ではない）状態をしらみつぶしにしているらしい様子が分かる。組み合わせの爆発っていうけど、まさにそんな感じなのか。
自分でやってみると本当にいろいろと分かるもので、スタックやキューを使った深さ優先と幅優先の意味がよく分かった。
もう1つ、勉強というか教訓になったのは、直前の状態から新規の状態を作るときに、コマの配置をコピーするのを忘れて、State#initializeで、
@koma = s.koma
とやったりしてハマったこと。Ruby初心者の典型的なミスとして知っていたはずだけど、最初は気づかなかった。これだと新規のStateオブジェクトが、直前のコマの状態を共有してしまって意図しない書き換えが起こる。そのために探索がある深さまで行って一瞬で終わる。で、次に
@koma = s.koma.dup
としてみたけど、やっぱりどうも探索が一瞬で終わってしまう。s.komaの中身はStructクラスで作ったKomaオブジェクトのArrayだったりするので、dupだけではシャローコピーになってしまう。なので正しくは、
@koma = Marshal.load(Marshal.dump(s.koma))
とマーシャリングしてディープコピーしないといけない。これはオブジェクトを扱う上でけっこう本質的なハマりだった気がする。
たいした必要性がないのに無駄にクラスを作って入れ子とかにすると、人間に分かりやすくはなっても、実行効率が落ちるし「コピー」という単純な概念も入れ子になってしまって、デメリットもバカにならない。Komaオブジェクトとか、やめておけば良かった。コマを1つずつ調べるループを抽象化したつもりが、結局インデックスを使わないと隣接する状態間で「このコマ」という指定ができないので、eachじゃなくて、each_with_indexと本末転倒なことをやっていたりする。だったら最初から数値のインデックスだけでいいじゃんとか。
そもそも効率優先で考えれば、盤面の状態はint5個で充分だし、各コマの場所やサイズだってint1つ、20bitもあれば足りそう。あ、ビットで盤面の配置を表せばビット演算で重なり判定もできて、速そうだ。
8000手順を超えるような解が発見できてもうれしくないので、せめて200手順ぐらいのものを見てみたい。幅探索で適当に「枝をかる」のとか、どうやってやるんだろうか。
