ナイトツアー単語

ナイトツアー

ナイトツアーとは

概要

チェスのナイトは、上下左右に2つ進み、直に曲がって1つ進んだマス(図のマス)に移動できる。変則将棋で用いられる4方向に動ける桂馬(八方)と同じ動き。

ナイトツアーは、この駒の動きに従って、チェスボード8×8の64マスすべてを1回ずつ通過するパズルである。このとき、同じマスを2度通ってはいけない

以下にナイトツアーの一例を掲載する。

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

このように、すべてのマスを通過し、かつ最初の地点に戻ることができるものは、とくにClosed knight's tourclosed:閉じた、循環した)と呼ばれる。日本語では、騎士の周遊と訳される。

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マスも限定される)。さらに、他の隅のマスも通過するためには、隅を除いた辺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」しかない左上マスに移動するべきである。

問題

ここでは、通常のm×nではなく、一変わった問題を紹介します。同じマスを二度通ることなく、すべてのマスを通過してください。左上が出発地点とは限りません。反転すると解答(一例)をご覧になれます。

問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

関連商品

関連項目

外部リンク

脚注

  1. *Knight's Tours of an 8×8 Chessboardexitpdf注意) - Brendan McKay(2010年
  2. *ナイトの周遊 全解数exit

【スポンサーリンク】

スマホ版URL:
https://dic.nicovideo.jp/t/a/%E3%83%8A%E3%82%A4%E3%83%88%E3%83%84%E3%82%A2%E3%83%BC

この記事の掲示板に最近描かれたお絵カキコ

お絵カキコがありません

この記事の掲示板に最近投稿されたピコカキコ

ピコカキコがありません

ナイトツアー

1 ななしのよっしん
2017/09/02(土) 02:33:46 ID: FlM9c0hNzJ
4×4が巡回できないことの明の部分
>4×4の場合、ある隅のマスから移動できる2マスと、反対側の隅のマスから移動できる2マス重複している。そのため、隅のマスを出発地点とするしかなく、
のあとに「残った2つの隅に行けない」で終わりでは?
2 ななしのよっしん
2017/09/02(土) 03:00:03 ID: ggf2fmUsJv
>>1
⑤⑧
⑦②
④⑨


↑のように、「残った2つの隅に行けない」わけではないので違います
3 ななしのよっしん
2017/09/02(土) 03:02:29 ID: ggf2fmUsJv
隅に行くともう他に移動できるマスがなくなるので、「隅を除いた辺8マスすべて通過してから、中央のマスに進む必要がある」と記載しています。
4 ななしのよっしん
2017/09/05(火) 02:18:31 ID: FlM9c0hNzJ
終点にすればいいだけだから>>1じゃだめだと気づいたので見に来たらものの30分で摘されてた
はずかし
5 ななしのよっしん
2018/04/13(金) 01:16:49 ID: TvA5gQh4Us
01|08|15|×
14|11|02|05
07|04|09|12
10|13|06|03

四隅のうち一つを通らなくていいならなんとか

急上昇ワード

2019/08/26(月)17時更新