問題
2025/10/31 のNHK将棋フォーカスで、将棋盤のある配置から別の配置へ最短手順でたどり着く、というパズルが紹介されました（NHKへのリンク。初回放送は1/12 だったようです）。
問題1.
 |
→ |  |
問題2.
 |
→ |  |
解法
3x3 や 4x4 の小さい盤での動きなので、以前書いたコードを少し変えて最適解を計算しました（以前の記事「飛角の入替え」）。
アルゴリズムは、普通の幅優先探索です。
幅優先探索（擬似コード）
def bfs(s0, s1):
initialize q # 展開すべき状態のキュー
initialize reached # すでに到達した状態を保持する集合
# 初期状態を追加
q.push((s0, 0))
reached.add(s0)
while q is not empty:
s, x = q.pop()
for s_next in next_states(s): # sから1手で到達できる状態についてループ
if s_next in reached:
continue # すでに到達した状態はスキップ
reached.add(s_next)
q.push((s_next, x+1))
if s_next = s1:
return x + 1 # ゴールへ到達
これをPythonで実装したスクリプトはこちら：
どちらも1秒以内に無事計算が終わりました（4x4の方は1秒ギリギリでした）。結果は、番組中で紹介されていたのと同じ手数となりました。残念ながら記録更新とはいきませんでした。
結果
問題１
* Step 0 *
--------
香 銀
金飛金桂
歩 歩
桂歩銀
--------
* Step 1 *
--------
金香 銀
飛金桂
歩 歩
桂歩銀
--------
* Step 2 *
--------
金香 銀
飛 金桂
歩 歩
桂歩銀
--------
* Step 3 *
--------
金香 銀
飛金 桂
歩 歩
桂歩銀
--------
* Step 4 *
--------
金香 銀
飛 桂
歩金歩
桂歩銀
--------
* Step 5 *
--------
金香 銀
飛桂
歩金歩
桂歩銀
--------
* Step 6 *
--------
香 銀
金 飛桂
歩金歩
桂歩銀
--------
* Step 7 *
--------
香飛銀
金 桂
歩金歩
桂歩銀
--------
* Step 8 *
--------
香飛
金 銀桂
歩金歩
桂歩銀
--------
* Step 9 *
--------
香飛
金銀桂
歩金歩
桂歩銀
--------
* Step 10 *
--------
香 飛
金銀桂
歩金歩
桂歩銀
--------
* Step 11 *
--------
香 飛
歩金銀桂
金歩
桂歩銀
--------
* Step 12 *
--------
香 飛
歩金銀桂
金 歩
桂歩銀
--------
* Step 13 *
--------
香銀飛
歩金 桂
金 歩
桂歩銀
--------
* Step 14 *
--------
香銀飛
歩金歩桂
金
桂歩銀
--------
* Step 15 *
--------
香銀飛
歩 歩桂
金金
桂歩銀
--------
* Step 16 *
--------
香銀飛
歩桂歩桂
金金
歩銀
--------
* Step 17 *
--------
香銀飛
歩桂歩桂
金金銀
歩
--------
* Step 18 *
--------
香銀飛
歩桂歩桂
金金
歩 銀
--------
* Step 19 *
--------
香銀飛
歩桂歩桂
金 金
歩 銀
--------
問題2
* Step 0 *
------
金飛
歩角と
王香銀
------
* Step 1 *
------
金飛と
歩角
王香銀
------
* Step 2 *
------
金飛と
歩角銀
王香
------
* Step 3 *
------
金飛と
歩 銀
王香角
------
* Step 4 *
------
金 と
歩飛銀
王香角
------
* Step 5 *
------
金と
歩飛銀
王香角
------
* Step 6 *
------
歩金と
飛銀
王香角
------
* Step 7 *
------
歩金と
飛 銀
王香角
------
* Step 8 *
------
歩 と
飛金銀
王香角
------
* Step 9 *
------
歩銀と
飛金
王香角
------
* Step 10 *
------
歩銀と
飛 金
王香角
------
* Step 11 *
------
歩銀と
飛王金
香角
------
* Step 12 *
------
歩銀と
王金
飛香角
------
* Step 13 *
------
歩 と
銀王金
飛香角
------
* Step 14 *
------
歩金と
銀王
飛香角
------
* Step 15 *
------
歩金と
銀 王
飛香角
------
* Step 16 *
------
歩金と
銀角王
飛香
------
* Step 17 *
------
歩金と
銀角
飛香王
------
* Step 18 *
------
歩金
銀角と
飛香王
------
* Step 19 *
------
歩金角
銀 と
飛香王
------
* Step 20 *
------
歩金角
銀香と
飛 王
------