４つのナイトの交換問題
白と黒のナイトの交換
下２つを黒に，上２つを白にしてください．
（盤を持ち上げて回転させるのはナシです．(^^;) ）
出典： P. Grogono and S. Nelson （永田訳），問題解決とプログラミング，近代科学社, 1985.
↓
ネタばれ注意（解答があります）
Problem 341 "
The Four Frogs" in Henry E. Dudeney, Amusements in Mathematics, Dover, 1917.
- まず，やみくもにやっても駄目だということを体験してください．
- この問題は，“同型グラフ”と“命名統治”のよい例題になります．
- 升目を節 (node) とし，動ける道筋を枝 (edge) として，グラフを書いてみましょう．節には名前（番号）を付けたほうがよいでしょう．
- その枝が交差しないように，同型なグラフに変形してみましょう．単純な形になるはずです．
- 白と黒のナイトを，そのグラフの上に置いてみましょう．
- もう，解答は小学生でも解るはずです．
- 周上の升目に 0 から順に番号を付けると，“剰余環”にも関連します (+3)．
-
最少手数の解の総数は，4,726,784 通りです（by 植田健治さん 2004-10-28）．
-
通常のチェスと同じに，白と黒を交互に動かすという条件をつけたときの，
解の状態・動作グラフ (PDF) （Copr. 植田健治さん 2004-10-22）です．
このときの最少手数の解の総数は，1,020 通りです（by 植田健治さん 2004-10-21）．
|
