Arrooow(iOSゲーム)のソルバーを作成する

iPhoneアプリのArrooowを自動で解くプログラムを作成する。
全40ステージに対して、各ステージ平均0.6秒で解くことが出来た。
作成したプログラムはここ (github)

Arrooowとは？

5x5の矢印が並んでいて、矢印をタップすると、その矢印を先頭にして指す先の矢印が順に消えていく。
ただし、最低2つ以上の矢印が消えなければならない。すべての矢印を消したらステージクリア。

なぜやるのか

AppStoreの説明によれば、

too hard for the human race...

らしい。人間にできないのなら機械にやってもらうしかない。。

実装

単純なdfsで実装。計算量が$25!!$程度になる気もするが、意外と1s以内にちゃんと終わる。
githubにアップロードした。(https://github.com/fbessho/ArrooowSolver/)

public class Solver
{
    public List<Integer> solve(Board board)
    {
        if (board.isSolved())
            return FastList.newList();

        for (int i = 0; i < 25; i++) {
            if (board.tappable(i)) {
                List<Integer> tapSequence = solve(board.tap(i));
                if (tapSequence != null) {
                    FastList<Integer> ans = FastList.newListWith(i);
                    ans.addAll(tapSequence);
                    return ans;
                }
            }
        }

        // unsolved
        return null;
    }
}

実験例

ステージ25（下図）を解いてみる。

argsにボード情報を入力(上、下、右、左をそれぞれt, b, r, lで表して全行を一列に並べている）。

実行結果。

結果通りのマスをタップする。最上（下）段がrow=1(5)、最左（右）列がcolumn=1(5)となる。
解けた。

統計

Arrooowに入っていた全40ステージを解いてみる。
Stage 5だけ探索が続き、20秒以上かかったが、その他のステージでは0.2秒未満で探索が終了している。

----- Summary -----
Max: 20436ms
Min: 484μs
Ave: 525ms

Stage  1: 38.35 ms
Stage  2: 3.354 ms
Stage  3: 6.901 ms
Stage  4: 6.122 ms
Stage  5: 20.44 s
Stage  6: 1.150 ms
Stage  7: 1.391 ms
Stage  8: 1.010 ms
Stage  9: 1.031 ms
Stage 10: 1.423 ms
Stage 11: 1.368 ms
Stage 12: 2.237 ms
Stage 13: 5.031 ms
Stage 14: 1.726 ms
Stage 15: 1.464 ms
Stage 16: 987.7 μs
Stage 17: 513.4 μs
Stage 18: 1.616 ms
Stage 19: 5.323 ms
Stage 20: 25.62 ms
Stage 21: 3.364 ms
Stage 22: 2.190 ms
Stage 23: 11.07 ms
Stage 24: 2.044 ms
Stage 25: 2.191 ms
Stage 26: 1.910 ms
Stage 27: 80.72 ms
Stage 28: 766.2 μs
Stage 29: 1.197 ms
Stage 30: 484.1 μs
Stage 31: 103.2 ms
Stage 32: 1.949 ms
Stage 33: 33.97 ms
Stage 34: 2.068 ms
Stage 35: 5.251 ms
Stage 36: 1.970 ms
Stage 37: 2.361 ms
Stage 38: 3.066 ms
Stage 39: 125.4 ms
Stage 40: 90.62 ms

展望

1. 25個の矢印をランダムに作成して解けるかどうかを判定すれば、無限（？）に問題を作成できる。
2. bfsにして最適解を求めたほうがいい？