ナイトツアー

この記事は第790回のオススメ記事に選ばれました！ よりニコニコできるような記事に編集していきましょう。

ナイトツアーとは

• Knight's tour - チェスのナイトを使用したパズル。騎士の巡歴、桂馬拾いとも。本稿で扱う。
• Night tour - パッケージツアーの一種。日没後（夜間）に行われるツアー。

概要

	★		★
★				★
★				★
	★		★

チェスのナイトは、上下左右に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はなぜ巡歴できないのか

4×4

1 ☆ ☆ ☆ ◆ 2 ☆ ☆ 4 ◆ ☆ ☆ ☆ 3

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つ違う。ナイトが巡歴し終えたとき、ナイトがいるマスは出発地点のマスと同じ色のマスとなるため、次に出発地点に戻ることができない。

解法

ダイヤモンドとスクエア

ダイヤモンドA

★ ★ ★ ★

スクエアA

★ ★ ★ ★

スクエアB

★ ★ ★ ★

ダイヤモンドB

★ ★ ★ ★

ナイトは、4×4の範囲の中で、互いに重複せずに周遊できるルートがある。ここでは便宜上、これらをダイヤモンドとスクエアと呼称する。ダイヤモンドとスクエアを考えれば、8×8の基本的なナイトツアーは簡単に解くことができる。

1. 8×8を、4×4の4つの正方形に分割し、それぞれダイヤモンドとスクエアを区別する。
2. ABどちらかのダイヤモンドをすべて巡歴する。
3. ABどちらかのスクエアをすべて巡歴する。
4. 2で通らなかったほうのダイヤモンドをすべて巡歴する。
5. 3で通らなかったほうのスクエアをすべて巡歴する。

Warnsdorf's rule

1 2 3 5 5 7

ナイトの辿るルートは、Warnsdorfの法則によっても考えることができる。

1. ナイトが移動可能なマスをすべて拾い上げる。
2. それぞれのマスについて、そこから移動可能なマスの数をチェックする。
3. 最も少ないマス（同数のものが複数あればそのいずれか）に移動する。

図では、ナイトが移動できるマスは6つある。そして、それぞれのマスについて、移動可能なマスの数を記載した。この法則に従うなら、移動可能なマスの数が「1」しかない左上のマスに移動するべきである。

問題

ここでは、通常の四角形ではない変わった形のナイトツアーを紹介する。同じマスを二度通ることなく、すべてのマスを通過すること。左上が出発地点とは限らない。反転すると解答例を閲覧できる。

問1

3 6 1 4 5 2 7

問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 Tour - 5×5～12×12、15×15の9種類のナイトツアーで遊べるサイト。

関連項目

• 数学
• チェス
• パズル
  • エイトクイーン
• レオンハルト・オイラー
• 組合せ爆発

脚注

1. *Knight's Tours of an 8×8 Chessboard（pdf注意） - Brendan McKay（2010年）
2. *ナイトの周遊 全解数（リンク切れ）