paiza オンラインハッカソンに挑戦

この一ヶ月ほど、paiza オンラインハッカソンというイベントで、15 パズルを解くプログラムの作成に挑戦していました。与えられた盤面を解く手数の短さを競う形式です。イベントのウェブサイトは以下にあります。
Rena and Minami International Programming Competition |Paiza Online Hackathon 5

私が作成したプログラムは GitHub に公開しています*1。このプログラムで、平均手数は 46.4 手でした。ウェブサイトのランキングによると、優勝者は 39.6 手で解けているので、私のプログラムとは 6.8 手の差があります。
php-15puzzle-solver/solve2.php at 1.0 · y-uti/php-15puzzle-solver · GitHub

プログラムの説明

プログラムは、15 パズルを以下の 4 つの部分問題に分割して解いていきます。それぞれの部分問題では、すべての盤面を網羅的に探索して、手数が最短になる動かし方を見つけます。実行時間の短縮のため、これらの探索処理は別のプログラムを用いて事前に実行しておき*2、全探索の結果を圧縮してプログラムに埋め込んでいます*3。

空白を動かして、一番下の行に 1 から 4 のいずれのタイルも空白も存在しない状態にする
上から 3 行の範囲内で空白を動かして、先頭行に 1 から 4 のタイルを正しく揃える
先頭行を除いた 3 行の範囲内で空白を動かして、 2 行目に 5 から 8 のタイルを正しく揃える
下半分の 2 行の範囲内で空白を動かして、9 から 15 のタイルを正しく揃える

15 パズルは、理論上は幅優先探索で最適解を求められます。下図で具体的に説明します。図の右端の盤面は解けている状態です。ここから空白を上か左に動かすと、二通りの盤面が得られます。これらは、一手で解ける盤面です。さらに空白を動かすと、二手で解ける盤面が得られます。これを繰り返せば、いずれすべての盤面に辿り着きます。各ステップで空白を動かした方向を記録しておけば、それを逆向きに辿ったものが最適解になります。

ところが、15 パズルの盤面の数は全部で 16 の階乗 = 20,922,789,888,000 通り存在し、これらを網羅的に調べるのは非現実的です。そこで、上述のようにいくつかの部分問題に分けて解くことで、現実的な時間で元の問題の解を求められるように工夫します。ただし一般に、それぞれの部分問題を最短の手数で解いても、それらを繋げたものは元問題の最適解にはなりません。この点に注意が必要です。

手順の後ろから遡って考える方が簡単だと思いますので、まず、部分問題の 4 番目、下半分を揃える問題を考えます。上半分には 1 から 8 が正しく揃っていることを前提にしていますので、盤面の数は全部で 8 の階乗 = 40,320 通りです。この程度であれば、すべての盤面を網羅的に探索できます。探索は下図のようなイメージです。上半分の 1 から 8 は固定した状態で、下半分の 2 行の範囲内で空白を動かします。

次に、手順を一つ遡って、2 行目に 5 から 8 のタイルを揃える問題を考えます。ここでは、先頭行に 1 から 4 が正しく揃っていることが前提になります。この問題の場合は、区別が必要な盤面の数は 12! / 7! = 95,040 通りになります。2 行目を揃えることだけに注目しているので、9 から 15 のタイルを互いに区別する必要はありません。探索は下図のようなイメージです。9 から 15 のタイルを X で表しています。この問題では、解けている盤面が複数存在することにも注意してください。たとえば、右端の解けている状態から空白を左、右、下に動かした盤面も、やはり解けている状態です。これは幅優先探索で辿られることはありません。

1 行目に 1 から 4 のタイルを揃える問題も同様にして 16! / 11! = 524,160 通りの盤面数で解けるのですが、今回のオンラインハッカソンではプログラムの実行時間やコードサイズが制限されているため、これは取り扱いの難しいサイズです。そこで、1 行目はさらに問題を分割して、まず 1 から 4 のタイルと空白をすべて 3 行目までに動かし、その後に最下行を除いた 3 行の範囲内で 1 から 4 のタイルを揃える方針としました。このような部分問題に分割すると、後半は 2 行目に 5 から 8 のタイルを揃える問題とまったく同じ問題になっているので、前半の問題だけを新たに解けばよいことになります。

1 から 4 のタイルと空白を 3 行目までに動かす問題では、区別が必要な盤面の数は 16! / (11! * 4!) = 21,840 通りです。5 から 15 のタイルを互いに区別する必要がないため 11! で割れるほか、この問題では 1 から 4 のタイルも互いに区別する必要がないので、さらに 4! で割れます。探索は下図のようなイメージです。1 から 4 のタイルを O で、5 から 15 のタイルを X で表しています。この問題も先ほどの問題と同様に、解けている盤面は複数存在します。右端の解けている状態から空白を左、上、下に動かした盤面も解けている状態ですので、幅優先探索では辿られません。また、図の左端下側の盤面も、幅優先探索では辿られません。この盤面から空白を上に動かせば部分問題は解けるので、これは二手ではなく一手で解ける盤面です。

ここまで、盤面をノードとする木構造のイメージで説明してきましたが、実装上はよりコンパクトな形で表現しています。まず、適当な方法で盤面と自然数を一対一に対応付けることで*4、この木構造は、盤面をインデックス、空白の移動方向を値とする配列で表現できます。空白の移動方向は上下左右の 4 通りなので 2 ビットの情報で表現でき、このことを利用すれば、この配列は盤面数の 1/4 の長さの文字列として表現できます*5。これを事前計算したうえで gzencode, base64_encode した文字列をプログラムに埋め込んでおきます。15 パズルの問題を解く際には、復元されたデータを見ながら盤面を操作していくことで、一直線に問題を解いています。

プログラム提出ごとの結果の推移

プログラム登録ごとの平均手数と実行時間の推移は以下のとおりです。このオンラインハッカソンは、開催期間中に何度でも自由にプログラムを登録してよいルールで、私は全部で 64 回登録していました。このうち全問正解したものは 49 回で、残りの 15 回は実行時エラーや解答不正解といった理由で失敗しています。これら失敗したものは、グラフの横軸上に灰色の点で示しています。

最初に提出したプログラムは、この記事で説明したような探索処理を一切行わず、タイルを一つずつ正しい位置に動かしていく方法でした。そのため、高速に実行できるものの手数は大きくなっています。その後 4/20 頃までに、下半分の 2 行の全探索、2 行目の全探索は実装しましたが、この時点では 1 行目は雑多なパターンを色々試して最良の結果を選ぶ方法で解いていました。GitHub リポジトリの数多くのファイルは、この頃の実装が残っているものです。この方法でも手数は最終版と大差ないのですが、パターンを増やした分だけ実行時間が長くなっています。1 行目を二つの部分問題に分ける方法を思いついたのは 5/13 です。この方法は実際のところ手数の改善はなかったのですが、それまでの手当たり次第に試してみるような解き方を整理することができ、実行時間を大幅に改善できました。

*1:今回は、イベント開催期間中に自由に公開してよいという記載がウェブサイトに見つからなかったので、開催終了後に push しました。

*2:GitHub リポジトリの toupper3.php, secondrow.php, lower2rows.php で計算できます。その他にも似たようなファイルがいくつかありますが、試行錯誤の段階で使っていたもので、最終的なコードでは利用していません。

*3:solve2.php の意味不明な文字列が、それぞれの全探索の結果を圧縮したデータです。

*4:gendata.php の encode 関数、decode 関数に実装されています。

*5:0x0 から 0xff までの全体を利用することになるので、実質的には文字列ではなくバイナリデータです。