考え方
コマを頂点に置く方法は$9! = 362,880$と少ないので，dictで「並び順：かかった手数」を管理しながら全探索（BFS）できます．コマのない頂点には，仮想的なコマ9を置くことにします．
- まだ見ていない遷移状態を
queに入れる． queから一つ取り出す．- コマのない頂点
akiを見つけ，
akiとつながっている全ての頂点chiについてakiとchiのコマを入れ替えるdictにこの状態がないなら，手数を+1して追加する．さらに，この状態をqueに追加する．
最終状態がdictに含まれていれば手数を出力すれば良いです．
回答例1：「Pinv[頂点]=コマ」を使う
与えられているのは「P[コマ]=頂点」です．これをそのまま使うのではなく，逆の対応「Pinv[頂点]=コマ」を利用する方法です．from collections import deque M = int(input()) G = [[] for _ in range(9)] for _ in range(M): u, v = map(int, input().split()) u -= 1 v -= 1 G[u].append(v) G[v].append(u) P = list(map(lambda x: int(x) - 1, input().split())) Pinv = [8] * 9 for i, p in enumerate(P): Pinv[p] = i Pinv = tuple(Pinv) memo = {Pinv:0} que = deque([Pinv]) while que: x = que.popleft() for i in range(9): if x[i] == 8: aki = i for chi in G[aki]: x2 = list(x) x2[chi], x2[aki] = x[aki], x[chi] x2 = tuple(x2) if x2 not in memo: memo[x2] = memo[x] + 1 que.append(x2) goal = tuple(i for i in range(9)) print(memo[goal] if goal in memo else -1)
【参考】
アライグマ「D問題はBFSなのだ！ 盤面の状態は「頂点iに駒A[i]がある」っていうリストAで表すのが簡単だと思うのだ」https://t.co/j8AvVeMd8n
— 競技プログラミングをするフレンズ (@kyopro_friends) October 23, 2021
回答例2：「P[コマ]=頂点」を使う
こちらの書き方のほうが素直です．上で頂点でループさせていた部分を，コマでループさせれば上手く書けます．
from collections import deque M = int(input()) G = [[] for _ in range(9)] for _ in range(M): u, v = map(int, input().split()) u -= 1 v -= 1 G[u].append(v) G[v].append(u) P = list(map(lambda x: int(x) - 1, input().split())) aki = list(set(i for i in range(9)) - set(P))[0] P = tuple(P + [aki]) memo = {P:0} que = deque([P]) while que: x = que.popleft() for koma in range(9): if x[koma] in G[x[8]]: x2 = list(x) x2[koma], x2[8] = x[8], x[koma] x2 = tuple(x2) if x2 not in memo: memo[x2] = memo[x] + 1 que.append(x2) goal = tuple(i for i in range(9)) print(memo[goal] if goal in memo else -1)
