無謀にも覚えたての Haskell で DevQuiz のスライドパズルを解く

はずだったんですが、さすがに、3x3, 3x4くらいまでの問題しか、現実的な時間で解けないという当然の結果になってしまいました。4x4くらいになると、現実的な時間（数分）で解くのが難しいことは知っていたので、驚きはしないのですが、単なる置換の観察から得られる結果では、やはり解くのは難しそうです。
スライドパズルあるいは15パズルは、置換で表現できるという意味で、あみだくじと原理的に同等なんだけど、一般に置換を互換の積に分解する場合、一意な分解になりません。数学書では、「ね、一意じゃないでしょ」と例示して証明終了となる訳ですけど、数学者ではないプログラマは、一意になろうとならなかろうと、”具体的に”置換（初期状態をゴールの状態に置換する）を何らかの互換（空所の移動）の積に分解しないといけない訳です。
総当たりは、非現実的です。3x3の場合高々31手必要で、4x4の場合は高々80手必要らしいから、１回のコマの移動の可能性が概ね３通りあるとすると、総当たりすると、だいたい

>sum [ 3 ^ n | n <- [ 1..31 ] ]
926510094425919
>sum [ 3 ^ n | n <- [ 1..80 ] ]
221713244121518884974124815309574946400

くらいの局面があるので、とてもじゃないけど現実的な時間で解けません。
DevQuiz の問題で、盤上に壁があって、難しくなっていると受け取られがちですが、実は、盤上に１つ壁があることで、選択可能な互換の数が、最大４つ減るので、チェックしないといけない空間が小さくなってくます。より易しくなっているとも考えられます。壁が多い問題を選択して解くというのも作戦上ありだったように思います。



という訳で、探索という方法をとるなら、何らかの方法で、はしょってもいい組み合わせを識別しないといけません。

• 恒等写像になるような同じ位置に写す置換は省けます。
• 少ない個数の互換の積に分解できるものは、少ないほうを選ぶようにしたい。

詳細は省きますが、偶数個前の局面で同じ位置にある場合、より簡略な分解が存在するようなので（証明はしていません）、この情報をもとに枝刈りしています。
これでなんとか3x3についてはかなり速くなったんですが、このままでは、4x4は到底解けません。以下いくつかちょっとだけ試した手法やアイデアを書いておきます。


１）n x nの上辺 [1.. n ]と左辺 [1 .. (n * (n-1) + 1)]の部分を完成させてから、残りの部分を (n-1) x (n-1)の問題として、同じように解いて、再帰的に解くという方法もあるらしいですが、発想はエレガントですが、かえって、簡単な問題の場合でも、長い結果を出してしまってよろしくないようです。


２）中間過程の局面を仮定して初期状態、ゴール状態両方から攻めるという作戦もあるようですが、その中間の局面をどう選ぶのがよいのか一概にいえません。下手な局面を選んでしまうとかえって難しい問題を解く結果になります。


３）評価関数を導入したりして、優先度の高いものを選んで探索が進むようにするという考えもあります。しかし、なかなかうまい評価関数が見つからないのが現実です。15パズルでよく使われるパリティチェックとか、ゴール状態のコマに対する直線距離とかマンハッタン距離とかいろいろ計算して観察しましたが、値が単純減少になるのは終盤近くだけで、それ以前の状況では、極端に値が大きくなったりすることはよくあるので、直接使えそうにありません。なんだか泥臭い話になりそうなので、観察するにとどめてしまいました。


４）あるいは、ともかくゴールに到達するまでランダムに進めていって、長い経路を得た上で、その経路を簡約するというアプローチもありかもしれないと考えています（が、モナドの壁を越えないとHaskellでランダムを扱うのは難しそうだったので、このアプローチは試せていません）。


そのほか、有力な手法の情報もありますが、今回は自分の頭で考えることに主眼をおいていたので、基本的な考察の域を出ていません。
もう少し根本的に、置換の最小な互換分解の方法を発見できないか考えている今日この頃です。


Haskell は、数年前から本は読んでいたけど、実際に動かして試すようになったのは Start Haskell 01 からなので、一ヶ月くらいしか実際に使っていません。まだ IO Monad も知らないので、ファイル読み書きはなし、なんとか泥縄で getArgs を使っているということになっています。 顕学にとっては噴飯もののコードになっていること請け合いです。
Data.Array、Data.Sequence、Data.Treeとかあることは知っていても、まだ使い方を学んでいないので、使っているデータ構造はリストとタプルだけです。データ構造をもっと工夫すれば、効率的になるんだろうけど、今使いこなせるのは、このレベルです。


つたないコードですが、記念に公開しておきます。
slowly Haskell code for Slide Puzzle of Google DevQuiz


タプルを使わずリストだけで実装したやや速い版もあるのですが、コードが汚いので、互換をタプルで表現した素直なほうのコードです。また、この版では、互換のリストをリストに入れているので、遅いコードになっています。順次チェックして捨てていくようにするのも可能ですが、わかりやすさを優先しています。互換のリストの長さでソートすると幅優先の探索が簡単に実装できるのが利点です（が処理は相当遅くなります）。
一般論として、深さ優先で探索する方が、幅優先で探索するより高速になりますが、最短解を得る保証がありません。