iPhone 앱의 Arrooow을 자동으로 해결하는 프로그램을 만듭니다.
총 40스테이지에 대해 각 스테이지 평균 0.6초로 풀 수 있었다.
작성한 프로그램은 여기 (github)

Arrooow란?

5x5의 화살표가 늘어서 있고, 화살표를 탭하면, 그 화살표를 선두로 해 가리키는 앞의 화살표가 순서대로 사라져 간다.
다만, 최소 2개 이상의 화살표가 사라져야 한다. 모든 화살표를 지우면 스테이지 클리어.

왜 할까

AppStore의 설명에 따르면,

too hard for the human race...

같다. 인간이 할 수 없다면 기계에 받을 수밖에 없다. .

구현

간단한 dfs로 구현. 계산량이 $25!!$ 정도가 될 생각도 하지만, 의외로 1s 이내에 제대로 끝난다.
github에 업로드했습니다. ( htps : // 기주 b. 코 m / f 베쵸 / 아로오 w w l / r / )

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

전망

25개의 화살표를 랜덤으로 작성해 풀 수 있을지 어떨지를 판정하면, 무한(?)에 문제를 작성할 수 있다.

bfs로 최적 해를 찾는 것이 좋습니까?