問題：飛車と角の入替え
2022年4月10日の将棋フォーカスの１コーナーで、将棋パズルが出題されました。
将棋の初期配置から、ルール通りに先手のみ駒を動かして飛車と角の位置を入れ替えてください
初期配置から
|
→ | この配置へ
|
番組では、制限時間５分で司会のサバンナ高橋さんが挑戦していました。
この問題の最短手順を探しました。
問題のサイズを見積もる
探す前に、最適解を見つけられるレベルの問題かを考えてみます。この問題、後ろへ下がれない駒を動かすと目的の配置を作れなくなるため、動かすことのできる駒は「飛・角・王・金x2・銀x2」の７枚です。また、駒が動く範囲は１・２段目の桂香のいない場所なので、14箇所です。したがって、配置の場合の数は、14箇所に7枚の駒を配置していくわけなので、$_{14}P_7 = 17297280$通り。 ただし、2枚ある金銀の入替えを区別しなければ場合の数は1/4の4324320通りになり、さらに角と銀は到達し得ない場所があることを考慮すると実際にはもっと少ない数になります。ざっと数百万くらいの配置（状態）がありそうだと見積もることができます。これくらいなら、標準的なPCでもすべての状態の情報をメモリに保持することができますし、現実的な時間で最適解を見つけられそうだと予想できます（アルゴリズムにもよりますが、大体$10^8$オーダーを超える辺りから厳しくなることが多いです）。
幅優先探索
初期状態 $s_0$ と目的の状態 $s_1$ が与えられたときの次のような幅優先探索を用います。
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 # ゴールへ到達
状態をキューから取り出すため、先に到達した状態ほど先に展開される幅優先探索になります。その結果、手数が単調に増加していき、目的の状態にたどり着いたときにはそれが最短手数であることが保証されます。
上の擬似コードは、最短手数を返すだけで具体的なステップは示しません。ステップまで求める方法としては、各状態の1つ前の状態を保持しておいて最後にさかのぼっていくことが考えられます。
def bfs(s0, s1):
initialize q # 展開すべき状態のキュー
initialize reached # すでに到達した状態を保持する集合
initialize prev # 各状態の1つ前の状態を保持する辞書
# 初期状態を追加
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))
prev[s_next] = s
if s_next = s1:
return make_path(s0, s1, prev)
def make_path(s0, s1, prev):
out = [s1]
s = s1
while s != s0:
s = prev[s]
out.append(s)
return reverse(out)
実装・実行時間
実装はPythonで行いました。コードはGist (https://gist.github.com/kota7/e55d7050a31080ca3de98353a1efb986) に置いてありますので、よろしければご覧ください。
実行時間は手元の環境で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 *
------------------
歩歩歩歩歩歩歩歩歩
王銀飛角
香桂銀金 金 桂香
------------------
* Step 20 *
------------------
歩歩歩歩歩歩歩歩歩
銀飛角
香桂銀金王金 桂香
------------------
* Step 21 *
------------------
歩歩歩歩歩歩歩歩歩
飛角
香桂銀金王金銀桂香
------------------
* Step 22 *
------------------
歩歩歩歩歩歩歩歩歩
飛 角
香桂銀金王金銀桂香
------------------