パズルゲー「ルームスイーパ」をC++で解いてみた

概要

　最近、Cygamesから出ているスマホゲーの「ルームスイーパ」にハマってしばらく解いていたのですが、流石に盤面がデカくなると自分で考えるのが面倒になるので、プログラムを組んで解かせてみることにしました。
　GitHubにもソースコード一式をアップロードしていますので、興味のある方は触ってみてください。以下の記述は、これを書く際に何を考えたのかというメモ書きです。
※2016/03/13追記：枝刈りを実装して超高速化しました。詳しくは文末にて。

　　SweepOptimizer - The Solver of "Room Sweeper"

パズルのルール

　ニコリのペンシルパズル風に書いてみると次の通りです。

1. 男の子・女の子・ロボット(以下掃除人)の移動するルートを決めましょう。

1. ルートは、ルームにおけるマスを横切るか、真ん中で折れ曲がります。
2. マスは最初、「拭かれていない床」「男の子」「女の子」「ロボット」「水たまり」「リンゴ」「ビン」「ゴミ箱」「リサイクル箱」「障害物」で初期化されています(「男の子」「女の子」「ロボット」は単なる初期位置)。
3. 掃除人は各0人以上、全体で1人以上存在します。
4. また、各掃除人は最大歩数が設定されており、それ以上マスを進むことができません。
5. 掃除人が「拭かれていない床」を通過すると**「拭かれた床」に変わります**。また、男の子が「水たまり」、女の子が「リンゴ」、**ロボットが「ビン」**のマスを通過すると同様に「拭かれた床」になります。
6. 女の子が「リンゴ」のマスを通過すると内部的にリンゴがストックされ、「ゴミ箱」のマスの隣(上下左右のどれか)を通過しないとそれが無くなりません。同様のことが、ロボットとビンとリサイクル箱にも言えます。なお、一度隣を通過した後に再度拾った場合は、再度隣を通過して捨てなければなりません。
7. ルートを走る際、掃除人はどれも1マスづつ同時に進行します。掃除人が2人以上同時に同じマスに鉢合わせした場合、その周囲1マス(8方向)の「拭かれていない床」が「拭かれた床」になります。
8. 全ての掃除人がルートを走り切った際に、全ての**「拭かれていない床」「水たまり」「リンゴ」「ビン」が「拭かれた床」になっており、かつどの女の子・ロボットもリンゴ・ビンをストックしていない**場合に清掃成功となります。
9. なお、掃除人がいた初期座標は、既に「拭かれた床」であるものとします。

　……こうして書き出すと長いですね。GitHubでのサンプル問題を図示するとこんな感じになります。

　お分かりいただけたでしょうか。以下、実装における考察を書いていきます。

考察

　盤面の実装はさほど難しくありませんでした。GitHubのReadme.mdにも書いていますが、床の状態は「拭かれていない床」～「障害物」の11種類ですので整数の配列で良いです(※実装では掃除人を盤面内に含めず、別途構造体の配列として保持している)。高速化を狙うなら、ビットボードで実装するのが恐らく一番でしょうね。
　後は各掃除人を深さ優先探索でパシらせればいいだけなのですが、種々の細かいルールが実装を面倒臭くしています。

ルール5(歩数制限)

　これはどちらかと言えばメリットに近いでしょう。各掃除人の最大歩数の最大値を取ればそれが再帰探索の上限ですから。

ルール7(ゴミ捨て)

　このルールのために、女の子およびロボットは、回収したブツを捨てるために一度はゴミ箱やリサイクル箱の隣を通らなければなりません。最適化の点ではメリットかもしれませんが、実装がややこしくなるという意味ではデメリットになります。

ルール8(鉢合わせ)

　どう考えてもデメリットです。もちろん「掃除人Aと掃除人Bが鉢合わせ可能か」は容易に判定可能(マスをチェス盤のように塗り分けて偶奇判定すればよい)ですが、鉢合わせできる場合は鉢合わせした際の処理を記述する必要があります。
　つまり、再帰探索中は「現在の歩数を保持」し、「鉢合わせした際は周囲を綺麗にする処理」を行い、「再帰を逆にたどる際はそれを元に戻す」作業を行います。ただ行って戻るだけなら前回の差分も小さくて済みますが、鉢合わせ処理は影響が大きすぎて盤面全体をバックアップして書き戻す処理を実装中では行っています。これがどれだけエグい処理かは言うまでもないでしょう。

ルール10(初期位置)

　このことから、実装では盤面と掃除人を分離して、盤面では「初期状態では、掃除人が立っていた位置は既に掃除された状態とする」、掃除人では「初期・一つ過去・現在の座標を保持しており、再帰探索を行う際に参照する」処理としています。恐らく一番オーソドックな方法でしょう。
　余談ですが、結果を保持するために人生初のstd::listを使いました。

探索速度

　現在、当該ゲームに実装された盤面は64個あります。権利上の都合でそれらをGitHubに上げるわけにはいきませんが、手元で幾つか写経してみたところNo.42ぐらいまではサクサク解くものの、No.54辺りを食わせたところあっさりと沈黙しました。真面目に枝刈りを行えばだいぶ違うのでしょうね……。
　上記を読めば誰でも実装できる~~(楽に実装できるとは言ってない)~~でしょうから、興味のある方は一度チャレンジしてみてはいかがでしょうか。

2016/03/13追記：枝刈りを実装

　拭くためには当然、そのマスまで「最大歩数の制限に引っかからない方法で」歩く必要があります。ルーム上に回復アイテムが落ちているわけではありませんので、「掃除人の位置から拭きたい位置のマスまでの最短距離＞掃除人が歩ける残り歩数」である場合、当該掃除人はそのマスを拭くことができません。つまり、ある状態において、「どの掃除人も拭けないマス」が1つでも存在した場合は枝刈りできます。
　ただし、ルール8の都合上、「枝刈りを無視した場合」と「枝刈りを無視しない場合」とで枝刈りの範囲を変える必要があります。鉢合わせ処理がありえる場合、上記条件が**「掃除人の位置から拭きたい位置のマスまでの最短距離＞掃除人が歩ける残り歩数＋2歩」に書き換わりますので。
　前述の通り、鉢合わせ処理自体も重いので、探索ルーチンを「鉢合わせを無視する版」と「鉢合わせを考慮する版」に分けることにしました。前者で解ければ儲けものですが、後者でも一応枝刈りできるので高速化が期待できます。実際に試したところ、鉢合わせを無視できる盤面でも鉢合わせを考慮する盤面でも絶大な効果を発揮。後にNo.1～No.64まで全データを一通り食わせてみましたが、それぞれ100倍以上**・10倍以上の高速化が期待できます。
　また、先に「鉢合わせを考慮しない版」に掛けるようにしたおかげで、攻略サイトでは鉢合わせ処理を使った解答だったのに実は鉢合わせさせなくても解けたといった例も見つかりました。僥倖と言えるでしょうね。

　なお、これらの工夫があっても、No.44～48,52,54,56,60～64は未だに解けていませんので、想像以上にルームスイーパの闇は深そうです……。今後も研究していこうと思います。ちなみに解けている中で一番手こずったのがNo.58(14.103秒)でした。