Knight Tourで経路も求める

Knight Tour Problem (Graph – Breadth First Search)をPythonで解いてみた。
これはチェス盤上にて開始から終了位置までのナイトの最短手順数を求めるものであるが、チェスのナイトが出発地点から目標地点まで移動する時のルートを保存、出力したい。BFS Knight's Tourで質問されているように途中の経路も出したい。
基本的な流れとしては過去に通った位置をすべて持ったまま幅優先で探索していけばよい。
幅優先なので最短経路が見つかる。
また、最大キュー数はおおよそ盤面のマス目の総数（8x8）× 駒の移動可能数(8)になるはず。
以下コード。やっぱりPythonは楽だ。

なお、開始、終了で互いに位置が異なる全組み合わせを試してみたが、最大でも7手順で収まる。

from collections import deque
from itertools import permutations

SIZE = 8 # 盤面サイズ

# 結果出力
def print_ans(ps, f):
    for r in range(SIZE):
        line = ''
        for c in range(SIZE):
            p = (r,c)
            line +=  f'{ps.index(p)+1}' if p in ps else '+'
        f.write(f'{line}\n')


def knight_tour(p_st, p_ed): # 開始、終了位置(行, 列)

    visited = set() # 訪問位置の集合
    q = deque()
    q.append([p_st])
    while q:
        ps_cur = q.popleft() # 現在位置

        # ゴールに到達
        p_cur = ps_cur[-1]
        if p_cur == p_ed:
            return ps_cur

        # 未訪問
        if p_cur not in visited:
            visited.add(p_cur)
            # 次の位置を探索
            for dir in [(-2,-1),(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2)]:
                p_nex = tuple(map(sum, zip(p_cur,dir)))
                # 盤面内
                if all(v >= 0 and v < SIZE for v in p_nex):
                    q.append(ps_cur + [p_nex])
    return None

with open('ret.txt', 'w') as f:
    cnt = 0
    # 開始、終了の全組み合わせ
    for st, ed in permutations(range(SIZE*SIZE), 2):
        p_st, p_ed = (st//SIZE,st%SIZE), (ed//SIZE,ed%SIZE)
        f.write(f'{p_st}->{p_ed}\n')
        ps = knight_tour(p_st,p_ed)
        if ps:
            cnt = max(len(ps),cnt)
            print_ans(ps, f)
    print(cnt) # 7

結果

(0, 0)->(0, 1)
14++++++
++2+++++
3+++++++
++++++++
++++++++
++++++++
++++++++
++++++++
：
(7, 7)->(7, 6)
++++++++
++++++++
++++++++
++++++++
++++++++
++++++2+
++++3+++
++++++41