将棋フォーカスの将棋パズルを解く

## 問題

2025/10/31 のNHK将棋フォーカスで、将棋盤のある配置から別の配置へ最短手順でたどり着く、というパズルが紹介されました（[NHKへのリンク](https://www.nhk.jp/p/shogi/ts/JV8MQK55Q4/episode/te/7WZ3LPXVP9/)。初回放送は1/12 だったようです）。

問題1.

<table>
<tr>
<td><img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/80588/ff2e5e8f-596a-41b2-b310-e5866c1ed49b.png"></td>
<td> <big>→</big> </td>
<td><img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/80588/22c58a18-5c68-4269-a03e-a5e253227386.png"></td>
</tr>
</table>

問題2.

<table>
<tr>
<td><img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/80588/6481a4e2-c85e-46bc-ba0a-2b5f45cc63de.png"></td>
<td> <big>→</big> </td>
<td><img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/80588/ab8aae2b-b421-48a1-8fbe-7056fe09b661.png"></td>
</tr>
</table>

## 解法

3x3 や 4x4 の小さい盤での動きなので、以前書いたコードを少し変えて最適解を計算しました（[以前の記事「飛角の入替え」](https://qiita.com/kota9/items/7ccb58e0d8f9fdb509df)）。
アルゴリズムは、普通の幅優先探索です。

```python: 幅優先探索（擬似コード）
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を解くコード](https://gist.github.com/kota7/e4b5983a00f2c8b4f83356570cba1102)
- [問題2を解くコード](https://gist.github.com/kota7/ae830236699a5eeea047b363266830cb)

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