算数のクイズ

算数のクイズでどうしても解けない問題があり、解放を教えてください。

問）６×６のボードにチェスのナイトを置き、全てのマスに同じマスにとまらずにスタート位置に戻る。


ランダムにマスを埋め、答えを導き出すだけでなく、その考え方を教えてください。
よろしくお願いします。

No.1 回答者： nag0720 回答日時： 2013/01/27 06:31

６×６のマスの位置を、11,12,13,・・・,66と表すことにする。

まず、11から始めて、ボードの淵を移動するようにナイトを動かすと、
11-23-15-36-55-63-51-32-11
と１周して１つの輪になる。
同様に、16、61、66から始めると、
16-35-56-64-52-31-12-24-16
61-42-21-13-25-46-65-53-61
66-54-62-41-22-14-26-45-66

通っていないマスは、中央の33,34,43,44だけ。
それぞれの輪の２番目の線を切って、中央のマスにつなげると、
11-23-44　、　34-15-36-55-63-51-32-11
16-35-43　、　44-56-64-52-31-12-24-16
61-42-34　、　33-21-13-25-46-65-53-61
66-54-33　、　43-62-41-22-14-26-45-66

これで１つの輪になる。
11-23-44-56-64-52-31-12-24-16-35-43-62-41-22-14-26-45-
66-54-33-21-13-25-46-65-53-61-42-34-15-36-55-63-51-32-11

No.2 回答者： ORUKA1951 回答日時： 2013/01/27 09:14

Knight Tour という昔から有名なパズルですね。

　回答のための手順は知られていますから、下記(英文)に譲りますが
　⇒Knight's tour - Wikipedia, the free encyclopedia( http://en.wikipedia.org/wiki/Knight%27s_tour )
　⇒chess knight tour 6x6 - Google 検索( https://www.google.co.jp/search?q=chess+knight+q … )

　必ず次ぎは異なる色の升目に移動すること、周囲か一辺の３×３の升目を埋めては次に進んでいく・・周囲から攻めていくか、横に攻めていくかで一通りではありません。

No.3 回答者： staratras 回答日時： 2013/01/30 23:42

６×６くらいでしたら、試行錯誤を繰り返してもいつかはできると思いますが、効率が悪いので、ワーンスドロフの規則といわれるルールに沿って考えてみました。

その規則とは、あるマスに移ったとき、そのマスからさらに移ることのできるマスを数え上げる、そしてそのそれぞれのマスからさらに何か所のマスに移れるかを数えて、もっとも少ないマスにしか移れないマスに移る。ただし対象となるマスが複数あれば、そのなかの任意のマスを選ぶ、というものです。（要するに選択肢の少ない厳しい状況にあるマスから先に回ろうということです）

例えば、添付した図の左側のAのマスからは、Ａ１からＡ８までの８か所に移ることができますが、そこからさらに何か所に移れるかを考えると、もっとも少ないのはＡ７とＡ８でどちらも３か所です。そこでＡ７またはＡ８に移ることになります。また４隅のマス(図ではＢ）からはＢ１かＢ２の２か所しか移れないことも明らかで、４隅に関しては（Ｂ１→Ｂ→Ｂ２）または（Ｂ２→Ｂ→Ｂ１）のどちらかの道筋しかないことが分かります。

効率よくルートを決めるために、あらかじめ「そのマスから何か所のマスに移れるか」を数えて色分けしてみました。真ん中の漢数字はそれぞれの色のマスから移れるマスの数を示しています。ただしこれは着手前の数で、移動を進めるにつれて当然この数よりは減っていきます。

添付した右側の図は、上の規則にほぼ従って発見した解の一つです。「ほぼ従って」というのはごく一部（２７→２８）例外があるからです。

No.4 回答者： staratras 回答日時： 2013/02/02 09:42

Ｎｏ．３です。

少し補足します。ワーンスドロフの規則に従って解を発見しても、ゴールからスタートへ戻れない場合があります。例えば添付した左側の図のような場合です。１から出発して終点が３６ですが、３６から１へは戻れません。

しかしその場合でも、途中で次の条件を満たす部分があれば、ゴールからスタートへ戻れるように修正することができます。その条件とは、N番目からゴールへ移動できて、かつN＋１番目からスタートへ移動できる、というものです。

添付した左図の場合、（３,４）、（９,１０）、（１３,１４）、（１５,１６）の4か所がこの条件を満たします。このうちの一つ（１５,１６）を使えば、１から15まで進んだ後、１６へは行かずにゴール（３６）へ移動して、３６→３５→３４…と逆に進み、１８→１７→１６のあとは15ではなくスタート（１）へ移動すればよいのです。これをあらためて番号を振りなおしたのが添付した右側の図です。(16以降を赤字にしました）