トップ  戦国と城  陰暦  異表記外来語  チェス  中国旅行  しごと  リンク  

4つのナイトの交換問題

Black KnightChess d44.pngBlack Knight
Chess d44.pngChess l44.pngChess d44.png
White KnightChess d44.pngWhite Knight
白と黒のナイトの交換
下2つを黒に,上2つを白にしてください.
(盤を持ち上げて回転させるのはナシです.(^^;) )

出典: P. Grogono and S. Nelson (永田訳),問題解決とプログラミング,近代科学社, 1985.
ネタばれ注意(解答があります)
Problem 341 "The Four Frogs" in Henry E. Dudeney, Amusements in Mathematics, Dover, 1917.

  • まず,やみくもにやっても駄目だということを体験してください.
  • この問題は,“同型グラフ”と“命名統治”のよい例題になります.
    1. 升目を節 (node) とし,動ける道筋を枝 (edge) として,グラフを書いてみましょう.節には名前(番号)を付けたほうがよいでしょう.
    2. その枝が交差しないように,同型なグラフに変形してみましょう.単純な形になるはずです.
    3. 白と黒のナイトを,そのグラフの上に置いてみましょう.
    4. もう,解答は小学生でも解るはずです.
  • 周上の升目に 0 から順に番号を付けると,“剰余環”にも関連します (+3).
     0 1 2
     7   3
     6 5 4
  • 最少手数の解の総数は,4,726,784 通りです(by 植田健治さん 2004-10-28).
  • 通常のチェスと同じに,白と黒を交互に動かすという条件をつけたときの,
    解の状態・動作グラフ (PDF) (Copr. 植田健治さん 2004-10-22)です.
    このときの最少手数の解の総数は,1,020 通りです(by 植田健治さん 2004-10-21).

キーワード: グラフ理論, 命名統治, 剰余環

駒の動き方
将棋を知っている人のための説明
ナイトは上下左右に桂馬跳び(現在地と異なる色の8マスに動ける).
将棋を知らない人のための説明
ナイトは半径2の円周上にある異なる色の8マスに飛び越して動ける.
Wikipedia 「ナイト (チェス)」
更新日: 2011-01-04 … 図を Wikipedia へのリンクに置き換えた
hr

Valid HTML 4.01!
Back ひとつ戻る
Banner 西村和夫のページ に戻る
NISHIMURA, Kazuo (nishimura@komazawa-u.ac.jp)