DevQuizのスライドパズルのひねた解法

Google Developer Day 2011 Japanの参加権を得るために、DevQuizに参戦してました。いや、正直途中から目的が参加よりも参戦に変わってしまいましたが…9/12にそのDevQuizが終わりましたので、自分でもかなり面白かったスライドパズルのちょっと変わった解法をピックアップしてみます。

文中のわからない単語はググると良いでしょう。

正統派の解法

まず正統派の解法は総手数制限があることから「探索空間を張って最適解を求める」です。最悪全解答が最適解であることも想定しなければいけません(ただし少し解答が揃えばその心配は杞憂であることがわかります)。実際の探索は最適解なので幅優先が好ましいですが、空間がO(n!)と明らかに広すぎるのでまともな方法では歯が立ちません。なので最適解を求めるという意味では枝刈りを工夫するかIDDFS(反復深化深さ優先探索)で頑張るしかありません。探索方法にはA*とかありますが、この問題に限って言えば幅優先探索とほとんど同じです。もちろんIDDFSでも枝刈りは有効に機能します。しかし日本の社会人には頑張って枝刈りする気力と時間はあまり無いのも事実です。もっとも探索空間の定義がO(n!)ですから最悪解を考えれば枝刈りもほぼ焼け石に水なわけです。

私も最初は幅優先でやってみたのですが、あまりにメモリの使用が激しい&一問解答後のメモリ解放に時間がかかりすぎるため、ほぼ固定メモリで解けるIDDFSを最終的には選択しました。枝刈りは単純なマンハッタン距離の壁考慮版。あと一問毎のタイムアウトは必須です。結果、Core 2 Duoの3G Hzクラスなマシンで秒間4000万手を探索できるソルバーが完成しています。この数字、スゴく見えますが問題の広さから考えたら絶望的な数字でして「解けるのしか解けないよね」ってもんです。でもPCが頑張ってくれるので4000問くらいまではこの手法で充分です。あとは投機的に探索を中断して再探索を始めたり、逆探査をしてみたり、深さ設定を150くらいに固定して探索したりで残り7問程度までは行けました。

一風変わった解法

ここからが本題。前述までの方法はそもそも探索空間の定義が広すぎる点が問題です。そのためどう工夫しても最悪のケースに対応できません。ここで「最悪のケースでも線形時間で答えを出すには?」と考えてしまうのは、システム屋さんの性とでも言いましょうか。ハイ、趣味の世界です。なので根本的に発想を変えてしまいます。

概要

考え方はシンプルです。決してローカルミニマムに落ち込まないエネルギー関数を与え、それを小さくする(維持する)方向への操作を優先して探索する。それができりゃ苦労はないって話ですが、問題が7問程度に限定されるなら現実的に可能でした。また総手数には余裕があるのでそちらも無視です。手順の概要は以下のとおりです。

右下からはじめ、一筆書きで全マスを通過して戻ってくるルートを設定する
通過できないマス(以下スポット)ができてしまう場合、ルートに2ヶ所以上接するように配置する
ルート上での最終状態と現在状態の間でエネルギー関数を与える

ちょっと見ればわかりますが1と2は巡回セールスマン問題の亜種に見え、短期間で片手間にプログラムに解かせるのは無理だと判断しました。そのため一度このアイデアは破棄しています。しかし7問程度なら人力でルート設定できるので、なんとかなるなと実装に移しました。

状態とエネルギー関数の定義

状態の定義は以下の要素で成り立ちます。

ルート状のマス目を順番に並べた文字列(0は除く)
各スポット上のマス目を順番に並べた文字列

こう考えると盤面での操作は以下の4つに分類&解釈できます。

ルートに沿って動く、状態が変わらない操作
ルート上のある位置(正確には0がある位置)に、別の場所からマスを移動(もしくは挿入)する操作
スポットからマスを復帰させる操作
スポットへマスを退避させる操作

2以降の操作は状態が変わるため全てエネルギーの変動があることになります。また3の操作後は4しか選択できませんので、スポットへの接続が2ヶ所ないとこのアルゴリズムは成立しません。ですから2以降の操作でエネルギーが上がってしまうものはバッサリとカットできます。いえ、そのようなエネルギー関数を定義することが重要になります。

となればエネルギー関数への要件としては以下のとおりです。

状態は循環で定義される(1234と3412はエネルギー的に等価)
スポットには正しいマス、誤ったマス、0が入りうる

理想を言えばあと何回(2～3)の操作をすれば最終状態になるかを定義できれば良いのですが、なかなかに難しいので今回は近似ということで

ルート上の見ているマスの右隣が間違っていたら+1、正しければ+0
スポット上のマスがあっていれば+0、間違っていたら+2、0だったならば+1
ルート上にスポット用のマスがあれば、そのスポット上にあるマスで置き換えて適用

といった感じのエネルギー関数を設定しました。

結果

7問中6問はこの方式で解けました。しかも数問は4000手を超えます。手数にゆとりがなければ採用できない手法となりました。

ソースコードはgithubに上げてあります。SlidePuzzle/route下を参照してください。

言い訳ですが、このアイデアは粗削りで穴も目立つのでとりあえず動くことを確認しようと、あまりまじめには実装しませんでした。深さ優先で簡単なバックトラックを仕込んだだけです。そのため候補の選択順に依存して、とんでもない計算結果をだしたり答えを出せなかったりします。ヒドイですね。ただし解答を出せる時は数千手であろうともかなり高速に、長くとも数秒以内で出してきます。

改良案の考察

改良案は幾つも考えられますので、とりあえず思いついたところから箇条書きしてみます。

ルートを自動設定したい
ルート選択を盤面進行に合わせて(一部を固定など)変化させたい(解けなかった一問は多分コレでイケる)
一筆書できない盤面へ対応させたい
深さ優先ではなく幅優先で探索すべき
盤面上の操作ではなく、状態上の操作で解いてから、盤面上への操作へ再翻訳
再翻訳のコストを付ければA*で最適解の探索もできそう?

総括

残った一問は手動+IDDFSで解いちゃいました。

全体的にやはり面白かったです。参加途中にはいろんな細かいエピソードがあったのですが、気が向いたら書きます。

補足

探索空間について「O(k^n)では?」という指摘をいただきました。指摘中のkとnの定義がわからないので「ハイそうですね」とは言えないのですが、本文中のO(n!)のnはマス数であり単純な順列の状態数を想定しているため、実際の探索空間はそれよりも小さいハズというのは事実ですので、そのことを補足しておきます。ただそうだとしても探索空間が広すぎるということに変わりはありません。