Scala でスライドパズルを解いてみた

もうすぐ ニンテンドー3DS が発売されますね!
私は買う気まんまんなんだけど、ローンチタイトルで買う予定なのは「レイトン教授と奇跡の仮面」のみ。そしてレイトン教授シリーズは買ったのはいいけどずっと積んだまま…。
私はこの手のシリーズ物は順番にやらないと気が済まない質なので、先月末くらいにようやく手を付け始めた(遅っ)。いやー楽しいねレイトン!

ようやく本題

レイトン教授シリーズはストーリーを進めながらパズルの問題を問いていくゲームで、その中でもちらほらとスライドパズルが出題される。
スライドパズルは試行錯誤で解いていくのも面白いんだけど、難しい問題は本当に難しい。ドツボにハマると平気で1時間とかかかったりする。
で、先ほども言ったように私には時間がないわけです。自業自得だろうとなんだろうとないものはないんです。
そこで、ちょっとずるいけど、プログラムの練習も兼ねてスライドパズルを解くプログラムを作ることにした。私はプログラマだ!プログラムで解ける問題をプログラムで解いて何が悪い!攻略サイトを探せば解き方書いてあるかもしれないけど、さすがにそこまでずるはしたくない。

とりあえずできたもの

コード

勉強するだけしてロクにコードを書いていなかった Scala で書くことにした。案の定すごい苦戦…。隙間時間でちょこちょこやってたとは言え、えらい時間かかってしまった。
紆余曲折あったけどとりあえずこうなった。扱うデータについてはコードの下で。


入力

問題は初期配置と最終的な配置を空行で区切った以下のようなテキストファイルで用意。

   ##
  #@@#
 # @@1#
#3   11#
#33    #
# 34 22#
# 44 2 #
 ##4 ##
   ##

   ##
  #22#
 # 24 #
#  44  #
#  34  #
#  33  #
#  13  #
 ##11##
   ##

# は壁。それ以外の文字は同じ文字で1つのブロック。空白は何もないところ。
最終的な配置は位置が決まってるブロックのみ書く。ないブロックは最終的にどこにあってもいい。
ちなみに、全体が壁で囲まれているか、とか、初期配置と最終配置で壁が同じになっているか、とか、初期配置にないブロックが最終配置にあったりしないか、とか、そういうのはまったくチェックしてないのでそういう問題を入れると散々答えを探索した挙句 "No answer." と出す。チェックまで手が回らなかった。と言うか面倒だった。

出力

入力の初期配置のものから1手ずつ動いたものがずらずらと出てくる。

動作

レイトン教授と悪魔の箱」より「ナゾ153 悪魔の箱」を解いてみた。最後の問題だけあってむずい。

   ##
  #@@#
  #@@##
 #a  f #
#aaa ff#
# a #ee #
# bbcdd#
 # bcd #
  #  ##
  #  #
   ##

   ##
  #  #
  #  ##
 #     #
#      #
#   #   #
#      #
 #     #
  #@@##
  #@@#
   ##

普通に動かしたら、どんどん重くなっていって相当時間かかった後 OutOfMemory で死んだ…。
が、JVMのメモリを増やしたら、4分くらいで見事答えが!よかったよかった。
ちなみにこの問題の解答は78手。

作ってて気になった部分など

MemoizeHash

HashSet を使っているのでハッシュの計算は相当な回数行われていると思ったので、immutable なクラスは何度計算しても変わらないはずだからと hashCode の計算をメモ化したら 3 倍くらい速くなった。メモ化すごい!
ただ、trait MemoizeHash って形で実装したんだけど、super.hashCode を呼ぶので case class Block extends MemoizeHash としてしまうと MemoizeHash が Block の上になってしまう。ダミーのサブクラスを作る手もあるけど面倒。結局 new するときに with 付けることにしたけど、これはこれで面倒。
こういうときどうするのがいいんだろ。ちゃんとやる場合はダミーのサブクラス作るしかないのかなー。

速度/メモリ

例で出した問題は一応解けたけど、もっと複雑な問題になったら解けなさそう。辿った全状態持ってるのでメモリの使用量も半端ないし。
一番最初、答えが出るようになった段階と比べるとそれなりに速くはなったけど、それでもまだまだ。できる人がやればもっと速くなるんだろうなー。私はこの辺りで力尽きた。
あー movable() も逆戻りチェックすればもう少し速くなるかも…だめだ、めんどい。これ以上はデータ構造やアルゴリズム自体を見直さないと辛そう。

落ちる

実は致命的なバグがあって、入力問題によってはなぜか落ちる。例えば以下の問題。

 ####
#a b #
#aa c#
#  cc#
# d  #
 ####

 ####
#    #
#    #
# ca #
#ccaa#
 ####

試験用に作った簡単に解けそうな問題。これを解こうとすると、"java.util.NoSuchElementException: next on empty iterator" で落ちる。ちなみに Scala 2.8.1.final。
ざっとトレースを見た感じだと、67 行目の map で落ちてる。多分。Scalaスタックトレースは相変らず魔界。
しかしそうだとすると、map で "next on empty iterator" はおかしい気がする。
状態表す部分は全部 immutable にしたつもりだし標準のコレクションライブラリしか使ってないはずなんだけど、何がおかしいのかさっぱりわからない…。誰か教えてください!

Scala の作法

あとは Scala 自体の作法とかよくあるパターンとかあまりわかってないので、そこら辺が大丈夫かも気になるところ。mutable と immutable の使い分けとかもあまりよくわかってない。

感想とか

ちゃんと問題が解けて嬉しかったんだけど、反面、ゲームで答えを入力しているときは「本当にこんな方法で解いちゃって本当に良かったのか…?」などと罪悪感にかられまくった。うう。

ちなみに肝心のゲームは3作目の「最後の時間旅行」をクリアしたので(現状)最新作の4つ目「魔人の笛」に手を付け始めたところ。全然間に合わないね!やはり1ヶ月で4本クリアは難しかったか…。多分私のことだから、3D 見たさにとりあえず「奇跡の仮面」を起動して「すげー」とか言いつつすぐに「魔人の笛」に戻るんだろうな。順番にやらないと気が済まない。