ウォーターサーバーとコーヒーマシンが一体化した画期的マシン >>

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

A 回答 (2件)

存在しません。


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

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

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

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

では、将棋盤(9×9)なら可能なのか。これは確認していません。
    • good
    • 0
この回答へのお礼

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

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

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


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

1.今のマスから移動可能なマスを一つ見る。
2.そのマスからさらに次にいくつのマスに移動できるかを数える。
3.挙げられる全ての移動可能なマスに対して2の作業を行う。
4.2で数えた数が最小であったマスに移動する。
5.最小のマスが複数個存在する場合、それらのマスは任意に選択する。
がんばってみてください!ファイトww
    • good
    • 0
この回答へのお礼

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

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

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

QNullってどういう意味ですか?

プログラミングで「Null」っていうのがよく出てきますけれど

一般的にどういう時に使うものなのか分かりやすく教えていただけませんか?

Aベストアンサー

値が何もないことをさします。
普通に考えると、値がないのであれば「0」でいいじゃないか、
というふうに思ってしまうのですが、
プログラミングの場合は「0」も意味をもつので、
特にNULLと表現します。

例えば、真=1 偽=0 値なし=NULL
という具合。
…真偽が反対だったらゴメンナサイ。


このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング