|
この記事は第790回のオススメ記事に選ばれました！
よりニコニコできるような記事に編集していきましょう。
|
ナイトツアーとは
概要
チェスのナイトは、上下左右に2つ進み、直角に曲がって1つ進んだマス（図の★のマス）に移動できる。変則将棋で用いられる4方向に動ける桂馬（八方桂）と同じ動き。
ナイトツアーは、この駒の動きに従って、チェスボード8×8の64マスすべてを1回ずつ通過するパズルである。このとき、同じマスを2度通ってはいけない。
以下にナイトツアーの一例を掲載する。1から順に64まで進むことができる。
| 1 |
42 |
63 |
54 |
5 |
44 |
57 |
18 |
| 62 |
53 |
2 |
43 |
56 |
17 |
6 |
45 |
| 41 |
64 |
55 |
60 |
47 |
4 |
19 |
58 |
| 52 |
61 |
40 |
3 |
16 |
59 |
46 |
7 |
| 39 |
14 |
27 |
48 |
35 |
8 |
29 |
20 |
| 26 |
51 |
36 |
15 |
28 |
23 |
32 |
9 |
| 13 |
38 |
49 |
24 |
11 |
34 |
21 |
30 |
| 50 |
25 |
12 |
37 |
22 |
31 |
10 |
33 |
|
さらに、この図の場合は64から1に戻ることができる。このように、すべてのマスを通過し、かつ最初の地点に戻ることができるものは、とくにClosed knight's tour（closed：循環した）と呼ばれる。日本語では、騎士の周遊と訳される。
8×8の騎士の周遊ルートは、約13兆通り存在し、回転同形や鏡像同形を除外しても1兆通り以上ある。[1]
考察
巡歴可能な最小のマス数
3×4
| 1 |
8 |
3 |
| 4 |
11 |
6 |
| 7 |
2 |
9 |
| 10 |
5 |
12 |
|
3×4
| 1 |
12 |
3 |
| 4 |
9 |
6 |
| 7 |
2 |
11 |
| 10 |
5 |
8 |
|
5×5
| 1 |
16 |
21 |
8 |
3 |
| 12 |
7 |
2 |
15 |
20 |
| 17 |
22 |
13 |
4 |
9 |
| 6 |
11 |
24 |
19 |
14 |
| 23 |
18 |
5 |
10 |
25 |
|
ナイトツアーは、8×8に限らずm×nに拡張して考えることができる。1×1を除けば、ナイトが巡歴可能な最小のものは3×4である。縦と横のマスの数が同じものに限れば5×5が最小となる。
左上のマスを出発地点とした場合、3×4の解は2通り、5×5は304通りある。[2]
3×3や4×4はなぜ巡歴できないのか
3×3の場合、中央のマスへの移動、または中央のマスから周囲のマスへの移動が不可能である。
4×4の場合、ある隅のマスから移動できる2マスと、反対側の隅のマスから移動できる2マスが重複している。そのため、隅のマスを出発地点とするしかなく、以下4マス目までは限定される（対称形となるので厳密には5マス目も限定される）。さらに、ほか2つの隅のマスを通過するためには、隅を除いた辺の8マス（図の☆マークのマス）をすべて通過したのちに中央のマス（◆マークのマス）に進まなければならない。しかし、◆マークのマスを通過せずに☆マークの8マスすべてを通過することは不可能である。
周遊可能な最小のマス数
3×10
| 1 |
4 |
29 |
18 |
21 |
6 |
23 |
16 |
13 |
10 |
| 28 |
19 |
2 |
5 |
26 |
17 |
8 |
11 |
24 |
15 |
| 3 |
30 |
27 |
20 |
7 |
22 |
25 |
14 |
9 |
12 |
|
5×6
| 1 |
18 |
7 |
22 |
3 |
16 |
| 8 |
27 |
2 |
17 |
12 |
23 |
| 19 |
30 |
21 |
6 |
15 |
4 |
| 26 |
9 |
28 |
13 |
24 |
11 |
| 29 |
20 |
25 |
10 |
5 |
14 |
|
6×6
| 1 |
8 |
23 |
16 |
31 |
10 |
| 22 |
15 |
2 |
9 |
24 |
17 |
| 7 |
36 |
21 |
30 |
11 |
32 |
| 14 |
29 |
12 |
3 |
18 |
25 |
| 35 |
6 |
27 |
20 |
33 |
4 |
| 28 |
13 |
34 |
5 |
26 |
19 |
|
ナイトが周遊可能な（＝最初の地点に戻ることができる）最小のものは3×10または5×6である。縦と横のマスの数が同じものに限れば6×6が最小となる。
逆順を除けば、3×10の解は16通り、5×6は8通り、6×6は9,862通りある。[2]
5×5はなぜ周遊できないのか
5×5に限らず、奇数×奇数の場合、騎士の周遊はできない。それはチェスボードのようにマスを交互に2色で塗り分けると分かりやすく、ナイトは白マスの次は黒マスに、黒マスの次は白マスに移動する。実際に、図の黒マスにいるナイトが移動可能なマス（☆マークのマス）はすべて白マスになっている。奇数×奇数のものは、この白マスと黒マスの数が1つ違う。ナイトが巡歴し終えたとき、ナイトがいるマスは出発地点のマスと同じ色のマスとなるため、次に出発地点に戻ることができない。
解法
ダイヤモンドとスクエア
ナイトは、4×4の範囲の中で、互いに重複せずに周遊できるルートがある。ここでは便宜上、これらをダイヤモンドとスクエアと呼称する。ダイヤモンドとスクエアを考えれば、8×8の基本的なナイトツアーは簡単に解くことができる。
- 8×8を、4×4の4つの正方形に分割し、それぞれダイヤモンドとスクエアを区別する。
- ABどちらかのダイヤモンドをすべて巡歴する。
- ABどちらかのスクエアをすべて巡歴する。
- 2で通らなかったほうのダイヤモンドをすべて巡歴する。
- 3で通らなかったほうのスクエアをすべて巡歴する。
Warnsdorf's rule
ナイトの辿るルートは、Warnsdorfの法則によっても考えることができる。
- ナイトが移動可能なマスをすべて拾い上げる。
- それぞれのマスについて、そこから移動可能なマスの数をチェックする。
- 最も少ないマス（同数のものが複数あればそのいずれか）に移動する。
図では、ナイトが移動できるマスは6つある。そして、それぞれのマスについて、移動可能なマスの数を記載した。この法則に従うなら、移動可能なマスの数が「1」しかない左上のマスに移動するべきである。
問題
ここでは、通常の四角形ではない変わった形のナイトツアーを紹介する。同じマスを二度通ることなく、すべてのマスを通過すること。左上が出発地点とは限らない。反転すると解答例を閲覧できる。
問2
|
|
1 |
|
|
9 |
6 |
3 |
| 5 |
2 |
11 |
8 |
| 10 |
7 |
4 |
|
|
12 |
|
|
|
問3
|
6 |
|
12 |
|
11 |
|
5 |
| 1 |
4 |
7 |
10 |
| 8 |
|
2 |
|
| 3 |
|
9 |
|
|
問4
|
11 |
|
15 |
|
| 5 |
14 |
9 |
12 |
7 |
| 10 |
1 |
6 |
3 |
16 |
|
4 |
13 |
8 |
|
|
|
2 |
|
|
|
関連リンク
関連項目
脚注
- *Knight's Tours of an 8×8 Chessboard
（pdf注意） - Brendan McKay（2010年） - *ナイトの周遊 全解数（リンク切れ）
親記事
子記事
兄弟記事
-
ページ番号: 5366020
-
-
リビジョン番号: 3263365
-
9件
