チェス・ナイトツアー(騎士の巡歴)問題がわかりません。

チェスのナイトツアーに関する質問です。チェス盤(8×8)でナイトを動かす時に左上隅から出発してすべてのマスを1回ずつ通って右下隅で終わる動き方は存在するのでしょうか。理由、参考文献、参考URLなどあればぜひお教えください。

No.2 ベストアンサー 回答者： rnakamra 回答日時： 2009/07/20 17:42

存在しません。

これは簡単に証明できます。
チェスボードは白と黒に色分けされています。隣り合うマスの色は異なります。

ナイトの動きでは移動前と後で必ずマスの色が変化します。
(理由は自分で考えてください)

今回の動きだとナイトは8×8-1=63回移動します。
つまり、最初が黒マスであるとすると、63回後には必ず白マスにいないといけないことになります。

しかし、チェスボードの対角線上の色は全て同じであるため左上が黒なら右下も黒になります。ですから63回の動きで右下隅に移動することはできません。

では、将棋盤(9×9)なら可能なのか。これは確認していません。

この回答へのお礼

ご回答ありがとうございます!!
色分けを考えるんですね。すごくわかりやすいです!!答えに気づいてしまうととても簡単ですが、私1人では決して気づきませんでした。笑
本当にありがとうございました☆

お礼日時：2009/07/20 19:47

No.1 回答者： univ-kyoto 回答日時： 2009/07/20 17:26

左下から右下はたぶん無理だと思われます。

６４マス全てのマスを１回づつ通る方法を教えますのでやってみてください。（この方法で左上から初めて右下に行く方法がなかったら不可能ということです。）

１．今のマスから移動可能なマスを一つ見る。
２．そのマスからさらに次にいくつのマスに移動できるかを数える。
３．挙げられる全ての移動可能なマスに対して２の作業を行う。
４．２で数えた数が最小であったマスに移動する。
５．最小のマスが複数個存在する場合、それらのマスは任意に選択する。
がんばってみてください！ファイトｗｗ

この回答へのお礼

簡潔でわかりやすい方法を教えていただきありがとうございます!!
この方法を知っていれば、今回のケースだけでなく全てのナイトツアー問題を考えることができますね。
実際にやってみたいと思います。ありがとうございました★

お礼日時：2009/07/20 19:41