8 Puzzle (GitHub) - 8パズル

どんな問題？

8 Puzzle
http://www.checkio.org/mission/8-puzzle/

8パズルをクリアせよ。

引数は、盤面データで、0～8 の list of list で渡される。0は空きマス。
戻り値は、クリアするための、空きマスの移動方向を文字列で返す。

U	上へ
D	下へ
L	左へ
R	右へ

例題：

checkio([[1, 2, 3],
         [4, 6, 8],
         [7, 5, 0]]) == "ULDR"

どうやって解く？

盤面をグラフの頂点として、BFS（幅優先探索）で解いてみる。
引数は list of listだけど、扱いやすいようにタプルに変換しておく。
上の例題だと、(1,2,3,4,6,8,7,5,0) となる。

tuple(n for line in puzzle for n in line)

get_next()関数で、空きマスを上下左右に移動した盤面を取得する。

MOVE = {'U': (0, -1), 'D': (0, 1), 'L': (-1, 0), 'R': (1, 0)}  # (x,y)

def get_next(numbers):
    for d in 'UDLR':
        zero_index = numbers.index(0)
        tx, ty = zero_index % 3 + MOVE[d][0], zero_index // 3 + MOVE[d][1]
        if 0 <= tx < 3 and 0 <= ty < 3:
            target_index = ty * 3 + tx
            result = list(numbers)
            result[zero_index], result[target_index] = numbers[target_index], 0
            yield d, tuple(result)

あとは、いつもと同じ。

まとめ

from collections import deque

MOVE = {'U': (0, -1), 'D': (0, 1), 'L': (-1, 0), 'R': (1, 0)}  # (x,y)

def get_next(numbers):
    for d in 'UDLR':
        zero_index = numbers.index(0)
        tx, ty = zero_index % 3 + MOVE[d][0], zero_index // 3 + MOVE[d][1]
        if 0 <= tx < 3 and 0 <= ty < 3:
            target_index = ty * 3 + tx
            result = list(numbers)
            result[zero_index], result[target_index] = numbers[target_index], 0
            yield d, tuple(result)

def checkio(puzzle):
    queue = deque([(tuple(n for line in puzzle for n in line), '')])
    seen = set()
    while queue:
        numbers, route = queue.popleft()
        seen.add(numbers)
        if numbers == (1, 2, 3, 4, 5, 6, 7, 8, 0):
            return route
        for direction, new_numbers in get_next(numbers):
            if new_numbers not in seen:
                queue.append((new_numbers, route + direction))

http://www.checkio.org/mission/8-puzzle/publications/natsuki/python-3/first/

問題によっては、答えが出るまでに少し時間がかかるけど、無事にクリア。

ちなみに、Wikipediaによると、「8パズルは任意の可能な配置へ31手以内で変形できる」そうだ。

他の人の答え

A*探索で、推定値にハミング距離を使ったり、マンハッタン距離を使ったりとみんな工夫している。BFSより、さらに効率的に解くためにはどうしたらいいかを考える問題だったのか。

気になる解答がたくさんあるので、後で詳しく見ることにしよう。（最近こればっかり）