summer_tree_home

Check iOでPython3をマスターするぜっ

The shortest Knight's path (Incinerator) - ナイトの最短ルート

Python CheckiO

どんな問題？

The shortest Knight's path
http://www.checkio.org/mission/shortest-knight-path/

チェスのナイトが、ある地点から別の地点へ移動するときの、最短ルートを探せ。

スタートとゴールの２点が"b1-d5"のような文字列で渡される。
最短で何手で移動できるかを返す。

ナイトは、桂馬が四方向を向いているようなもので、8ヶ所に移動できる。

■ ■ 　
■ ■
▲ 　 　
■ ■
■ ■ 　

どうやって解く？

これも探索問題ってことになるのかな？
前に苦労したOpen Labyrinthに似ているが、今回は最短経路という条件が付いてくる。
1手目で進めるのは8ヶ所、2手目で進めるのは8*8=64ヶ所（実際には重複するのでもっと減るだろうけど）、どんどん広がっていくツリーを探索していって、ゴールが見つかれば終了、という流れだろうか。

探索＆最短経路

アルゴリズムの本を再度読んでみたが、やっぱりBFSとかDFSとか、ちゃんと理解していないので、もう一度整理してみる。

他にも、最短経路問題として

などが載っていた。

書き出してみると、よけいに混乱してきた。今回、マスからマスへは一手で動くわけだから、辺の重みはなし、ってことだと思うんだが…。
とにかく、BFSでやってみる。

引数を座標に変換

引数の'b1-d5'形式の文字列を、(x1,y1)と(x2,y2)という座標に変換する。文字列のindex=0がx1、index1がy=1、と決めうちして変換しておく。あまりいい方法ではないかもしれない。

def parse(s):
    X = 'abcdefgh'
    Y = '12345678'
    return (X.index(s[0]), Y.index(s[1])), (X.index(s[3]), Y.index(s[4]))

次に進むことができるマスを取得

現在位置を(x,y)とすると、次に進めるマスは、(x±1,y±2),(x±2,y±1)となる。
内包表記でうまく書けた（つもり）。範囲チェックして、ボード内の座標のみを返す。

def get_next_positions(pt):
    pts = [(pt[0] + x * sx, pt[1] + y * sy) for sx in [-1, 1] for sy in [-1, 1] for x, y in [(1, 2), (2, 1)]]
    return [p for p in pts if 0 <= p[0] < 8 and 0 <= p[1] < 8]

まとめると

def checkio(move):
    def parse(s):
        # 'b1-d5' to (1,0),(3,4)
        X = 'abcdefgh'
        Y = '12345678'
        return (X.index(s[0]), Y.index(s[1])), (X.index(s[3]), Y.index(s[4]))

    def get_next_positions(pt):
        pts = [(pt[0] + x * sx, pt[1] + y * sy) for sx in [-1, 1] for sy in [-1, 1] for x, y in [(1, 2), (2, 1)]]
        return [p for p in pts if 0 <= p[0] < 8 and 0 <= p[1] < 8]

    def get_path():
        result = []
        pt = goal
        while pt != start:
            result.append(visited[pt])
            pt = visited[pt]
        return result

    start, goal = parse(move)
    visited = dict()  # Key=pos, Value=prev pos
    queue = [start]
    while len(queue) > 0:
        pos = queue.pop(0)
        if pos == goal:
            return len(get_path())

        for new_pos in get_next_positions(pos):
            if new_pos not in visited:
                visited[new_pos] = pos
                queue.append(new_pos)
    return 0

一度通ったマスは、visited辞書で管理しておく。
visited辞書に、移動前の座標を入れておいて、ゴールに着いたら、これを逆にたどればルート（通ってきたマスのリスト）がわかる。 get_path()がその部分。ルートの長さが答えとなる。


難しそうだと思ったわりには、あっさりとクリアできてしまった。
ちょっと物足りないので、別解も考えてみる。

続く