問題

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を解くコード
問題2を解くコード

どちらも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 *
------
歩金角
銀香と
飛　王
------