Open Labyrinth (CheckiO > Home) 迷路の探索

どんな問題？

Open Labyrinth
http://www.checkio.org/mission/open-labyrinth/

12x12の迷路を探索する問題。スタート地点は座標(1,1)、ゴールは(10,10)となっている。
迷路データは、1が穴、0が道として定義されている。

スタートからゴールまでのルートを 'SSSSEEENNW...' のように文字列で返す。SSSSなら南に4回進む、EEEなら東に3回進むということだ。答えは最短ルートでなくてもいい。

もともとゲームを作りたくてプログラミングを始めたので、こういう問題はわりと好きだ。迷路を見てると、昔メガドライブで遊んだタントアールを思い出してしまった。（年齢がばれる？）

どうやって解く？

よく、迷路では左手（または右手）を壁に付けたまま進んでいけば必ずゴールできる、と言われているので、その方法を使ってみることにした。

全体の構造としては、自キャラの座標を変数にして、隣のマスへの移動を繰り返す。自キャラが(10,10)に来ればループを抜ける、という形になるだろう。
左手を壁に付けたまま、隣のマスへ移動するという部分をどう書けばいいかな？

-	北	-
西	▽	東
-	南	-

自キャラが南を向いて歩いているとき、左手は東だ。だから、まず東に進めばよい。東がダメなら南に進む、南もダメなら西、西もダメなら北に向かう。
北に向かうのは来た道を戻ることになるが、東、南、西に進めないということは袋小路ということ。つまり来た道を戻って正解だ。
同じように、自キャラの向きによって、探索マスの順番を決めていけば良さそうだ。

自キャラの向き	探索マスの順番
北	西→北→東→南
東	北→東→南→西
南	東→南→西→北
西	南→西→北→東

ようするに自分の左マスから時計回りに調べればいいだけか。右手で探索するなら右マスから反時計回りにすればいい。
コードを書いてみた。

def get_new_position(pos, direction):
    # 移動先の座標を取得
    dirs = {'N': (0, -1), 'E': (1, 0), 'S': (0, 1), 'W': (-1, 0)}
    return tuple([sum(t) for t in zip(pos, dirs[direction])])

def get_search_directions(direction):
    # 探索順を取得
    s = 'NESW'
    index = s.index(direction)
    return (s * 3)[index + 3:index + 3 + 4]

def checkio(maze_map):
    def is_safe(pos):
        # 移動可能ならTrue
        return maze_map[pos[1]][pos[0]] == 0

    my_position = (1, 1)  # 自キャラの位置
    my_direction = 'S'    # 自キャラの向き

    result = ''
    while my_position != (10, 10):
        for d in get_search_directions(my_direction):
            new_position = get_new_position(my_position, d)
            if is_safe(new_position):
                my_position = new_position
                my_direction = d
                result += d
                break
    return result

エディタ画面で、Check routeボタンを押すと、自キャラが歩いてゴールする様子をアニメーションで見ることができる。袋小路に入ったり無駄な動きが多いが、まあ一応テストはクリアした。

課題がいくつか

• get_new_position()がわかりにくい。
• get_search_directions()もわかりにくい。
• 左手だけでなく右手にも対応したい。

get_new_position()

現在位置と移動方向から、移動先の座標を取得する関数。

def get_new_position(pos, direction):
    dirs = {'N': (0, -1), 'E': (1, 0), 'S': (0, 1), 'W': (-1, 0)}
    return tuple([sum(t) for t in zip(pos, dirs[direction])])

指定した座標(pos)の1つ隣の座標を返すだけなのだが、何をやっているのかわかりにくい。タプルの足し算 (x1,y1) + (x2,y2) -> (x1+x2,y1+y2) って、もっと簡単な方法はないのかな？
いっそ、こんな感じで、ベタに書いたらどうだろう。

def get_new_position(pos, direction):
    if direction == 'N':
        return pos[0], pos[1] - 1
    elif direction == 'E':
        return pos[0] + 1, pos[1]
    elif direction == 'S':
        return pos[0], pos[1] + 1
    elif direction == 'W':
        return pos[0] - 1, pos[1]

さすがに野暮ったいか？

dirs = {'N': (0, -1), 'E': (1, 0), 'S': (0, 1), 'W': (-1, 0)}

def get_new_position(pos, direction):
    d = dirs[direction]
    return pos[0] + d[0], pos[1] + d[1]

これくらいが見やすくていいかな？dirsは関数の外に出しておいた。

get_search_directions()

探索する順番を取得する関数。例えば、南向きなら、東→南→西→北の順に探索するので、引数が'S'なら'ESWN'を返す。（同様に 'N' -> 'WNES', 'E' -> 'NESW', 'S' -> 'ESWN', 'W' -> 'SWNE'）

def get_search_directions(direction):
    s = 'NESW'
    index = s.index(direction)
    return (s * 3)[index + 3:index + 3 + 4]

上の最後の行で'NESWNESWNESW'から4文字をスライスしているのだが、何をやっているのかわかりにくい。

def get_search_directions(direction):
    s = 'NESW'
    prev = (s.index(direction) + 3) % 4
    return s[prev:] + s[:prev]

'NESW'の要素をprev分だけずらしてみた。あんまりしっくりこないなぁ。リストや文字列をシフトする定番の方法って何だろう？
ググったら、collections.dequeのrotateメソッドを使う方法もあるようだ。

def get_search_directions(direction):
    s = 'NESW'
    d = collections.deque(dirs)
    d.rotate(1 - s.index(direction))
    return ''.join(d)

import collections が必要になるけど、一番わかりやすいかな。

というわけで、まとめ。左手だけでなく右手にも対応してみた。

import collections

dirs = {'N': (0, -1), 'E': (1, 0), 'S': (0, 1), 'W': (-1, 0)}

def get_new_position(pos, direction):
    d = dirs[direction]
    return pos[0] + d[0], pos[1] + d[1]

def get_search_directions(direction, left_hand):
    """
    direction='S', left_hand=True -> 'ESWN'
    direction='S', left_hand=False -> 'WSEN'
    """
    s = 'NESW' if left_hand else 'NWSE'
    d = collections.deque(s)
    d.rotate(1 - s.index(direction))
    return ''.join(d)

def checkio(maze_map):

    def is_safe(pos):
        return maze_map[pos[1]][pos[0]] == 0

    my_position = (1, 1)
    my_direction = 'S'
    left_hand = True

    result = ''
    while my_position != (10, 10):
        for d in get_search_directions(my_direction, left_hand):
            new_position = get_new_position(my_position, d)
            if is_safe(new_position):
                my_position = new_position
                my_direction = d
                result += d
                break
    return result

いっちょあがり！

他の人の答え

・・・みんなの答えがさっぱりわからん（泣）
グラフ探索アルゴリズムとか、DFSとかBFSとか、ヒューリスティクスとか、何を言ってるんだ？？？

ググってみたが、とりあえず迷路探索というのが深いテーマなんだ、ということはわかった。
参考になりそうなリンク

• 迷路 - Wikipedia
• 深さ優先探索 - Wikipedia
• 幅優先探索 - Wikipedia
• Maze solving algorithm - Wikipedia, the free encyclopedia

私の書いたコードは、右手法（左手法）という名前の探索法らしい。
英語では、Wall followerとか、Left-hand rule というそうだ。

なにはともあれ、これで最初の島の全9ミッションをクリア！

追記

問題文を読み直してみると、ヒントが書いてあった。すっかり読み飛ばしていたよ。
（Show hintというリンクをクリックすると表示される。）

• The labyrinth in this task can be represented as graph. Just think about where you can go from each cell and find the correlating path in the graph.
• The simplest way is Breath-First-Search algorithm. But don't mix up graph and tree search.
• Do you want nice and quick solution? Read about A* search algorithm and don't forget about admissible heuristic.

すんません、よくわかりません・・・。