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

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

　　[SweepOptimizer - The Solver of "Room Sweeper"](https://github.com/YSRKEN/SweepOptimizer)

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

　……こうして書き出すと長いですね。[GitHubでのサンプル問題](https://github.com/YSRKEN/SweepOptimizer/blob/master/sample/sample.txt)を図示するとこんな感じになります。

![sample.png](https://qiita-image-store.s3.amazonaws.com/0/29802/2159fb68-3723-6355-1c98-dbe5a50d576d.png)

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

# 考察
　盤面の実装はさほど難しくありませんでした。[GitHubのReadme.md](https://github.com/YSRKEN/SweepOptimizer/blob/master/Readme.md)にも書いていますが、床の状態は「拭かれていない床」～「障害物」の11種類ですので整数の配列で良いです(※実装では掃除人を盤面内に含めず、別途構造体の配列として保持している)。高速化を狙うなら、**[ビットボードで実装する](http://qiita.com/YSRKEN/items/29829c7f5beae7900f36)**のが恐らく一番でしょうね。
　後は各掃除人を[深さ優先探索](http://mathtrain.jp/dfsbfs)でパシらせればいいだけなのですが、種々の細かいルールが**実装を面倒臭くしています**。
## ルール5(歩数制限)
　これはどちらかと言えばメリットに近いでしょう。各掃除人の**最大歩数の最大値**を取ればそれが**再帰探索の上限**ですから。
## ルール7(ゴミ捨て)
　このルールのために、女の子およびロボットは、回収したブツを捨てるために一度はゴミ箱やリサイクル箱の隣を通らなければなりません。最適化の点ではメリットかもしれませんが、実装がややこしくなるという意味ではデメリットになります。
## ルール8(鉢合わせ)
　**どう考えてもデメリットです**。もちろん「掃除人Aと掃除人Bが鉢合わせ可能か」は容易に判定可能(**マスを**チェス盤のように塗り分けて**偶奇判定**すればよい)ですが、鉢合わせできる場合は鉢合わせした際の処理を記述する必要があります。
　つまり、再帰探索中は「現在の歩数を保持」し、「鉢合わせした際は周囲を綺麗にする処理」を行い、「再帰を逆にたどる際はそれを元に戻す」作業を行います。ただ行って戻るだけなら前回の差分も小さくて済みますが、鉢合わせ処理は影響が大きすぎて**盤面全体をバックアップして書き戻す処理**を実装中では行っています。これがどれだけエグい処理かは言うまでもないでしょう。
## ルール10(初期位置)
　このことから、実装では盤面と掃除人を分離して、盤面では「初期状態では、**掃除人が立っていた位置は既に掃除された状態**とする」、掃除人では「**初期・一つ過去・現在の座標**を保持しており、再帰探索を行う際に参照する」処理としています。恐らく一番オーソドックな方法でしょう。
　余談ですが、結果を保持するために**人生初の[std::list](http://vivi.dyndns.org/tech/cpp/list.html)を使いました**。

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

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

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