要旨
チェスのナイトは、縦に $2$・横に $1$(または縦に $1$・横に $2$)跳ぶ。盤の全マスを一度ずつ通る道筋をナイトの巡回といい、最後のマスから最初のマスへ一手で戻れるものを閉じた巡回という。どの盤に閉じた巡回があるかを、塗り分けと全探索の二つで確かめる。新しい定理も法則も主張しない。
第一に、$5\times5$ には閉じた巡回が無い。$5\times5$ の盤で全部の道筋を探すと、全マスを一度ずつ回る巡回は向きを区別して $1728$ 本あり、そのうち最初のマスへ戻れるものは $0$ 本だった(第2節)。
第二に、巡回は多い色からしか始まらない。盤を市松に塗ると、$5\times5$ は一方の色が $13$ マス(四隅を含む)、もう一方が $12$ マスである。$1728$ 本はすべて $13$ マスの色から始まり、$12$ マスの色からは $1$ 本も始まらなかった。角から始まる巡回は $304$ 本である(第2節)。
第三に、これが本稿の芯である。ナイトは一手ごとに色を替えるので、マスの数が奇数の盤には閉じた巡回が無い。色を交互に踏むので、$25$ マスを回る道筋は多い色で始まり多い色で終わる。最後のマスから最初のマスへ戻る一手は同じ色どうしで、ナイトにはできない(第3節)。
第四に、マスの数が偶数の盤には、閉じた巡回がある。$6\times6$ と $8\times8$ で、行き先の少ないマスから試す探索が閉じた巡回を見つけ、全マスを一度ずつナイトの動きで回って最初へ戻れることを確かめた(第4節)。
キーワード:ナイトツアー、閉じた巡回、二色の塗り分け、ワーンスドルフの規則、ハミルトン閉路。
射程(何を示さないか)
新しい定理も法則も主張しない。どの長方形の盤に閉じた巡回があるかの分類(シュウェンク、$1991$)、行き先の少ないマスへ進む規則(ワーンスドルフ、$1823$)、$5\times5$ の巡回の数は、いずれも既知である。巡回の総数の一般式を扱わない。$5\times5$ を全部探し、$6\times6$ と $8\times8$ では閉じた巡回を一つ見つけるだけである。偶数でも閉じた巡回が無い盤は扱わない。$4\times n$ の盤などには、マスの数が偶数でも閉じた巡回が無いことが知られているが、本稿は奇数の場合だけを見る。既刊との関係:論文601 は、15 パズルの局面の半分が届かないのは盤が二色に塗れるからだと示した。同じ二色の塗り分けが、ここでは閉じた巡回を禁じる。論文348 は、同じグラフでも繋ぐのは安く並べるのは高いことを示した。全マスを一度ずつ回る並べ方は、探すのに手間がかかる。加えたのは、$5\times5$ の全探索で巡回の本数と始まる色を数えたこと、塗り分けの数えと全探索の二つを突き合わせたこと、分離子をマスの数の偶奇に置いたことである。
1. 記法と問い
設定:$R\times C$ の盤のマスを市松に二色で塗る。ナイトの一手は縦横に $(2,1)$ か $(1,2)$ 動き、必ず色の違うマスへ跳ぶ。全マスを一度ずつ通る道筋を巡回、最後から最初へ一手で戻れる巡回を閉じた巡回と呼ぶ。
問い:どの盤に閉じた巡回があるか。巡回はどのマスから始められるか。
2. $5\times5$ を全部探す
計算 2.1:$5\times5$ の $25$ マスのそれぞれから、全部の道筋を探した。
| 数えたもの | 本数 |
|---|---|
| 向きを区別した巡回 | $1728$ |
| 閉じた巡回 | $0$ |
| 多い色($13$ マス・四隅を含む)から始まる巡回 | $1728$ |
| 少ない色($12$ マス)から始まる巡回 | $0$ |
| 角から始まる巡回 | $304$ |
観察 2.2 $1728$ 本の巡回のうち、最初へ戻れるものは一本も無い。そして少ない色の $12$ マスからは、巡回が一本も始まらない。同じ盤の同じ駒で、始まるマスが色だけで二つに分かれる。
3. 塗り分けで数える
観察 3.1 これが本稿の芯である。ナイトは一手ごとに色を替えるので、マスの数が奇数の盤には閉じた巡回が無い。巡回は色を交互に踏むので、$25$ マスの道筋は色 A と色 B を A,B,A,B,…,A と $13$ 対 $12$ で踏む。だから多い色で始まり、多い色で終わる。最後のマスと最初のマスは同じ色なので、その間を一手で結ぶことはナイトにはできない。少ない色から始めると、$13$ 対 $12$ にならず、全マスを踏み切れない。
観察 3.2 塗り分けの数えが、全探索の結果をそのまま言い当てる。閉じた巡回 $0$ 本、少ない色からの巡回 $0$ 本は、どちらも道筋を一本も調べずに、色の数だけから出る。全探索はその予言を $1728$ 本すべてで確かめた。
4. 偶数の盤
計算 4.1:$6\times6$ と $8\times8$ で、行き先の少ないマスから試し、まだ通っていないマスがどれも二本の辺を残せるかを見て枝を刈る探索で、閉じた巡回を探した。$6\times6$ では $158204$ 回の分かれ道、$8\times8$ では $67$ 回の分かれ道で見つかり、どちらも全マスを一度ずつナイトの動きで回って最初へ戻れることを確かめた。
観察 4.2 偶数の盤では、二色が同じ数になり、閉じた巡回が可能になる。$36$ マスなら $18$ 対 $18$、$64$ マスなら $32$ 対 $32$ で、多い色で始まり多い色で終わるという縛りが消える。ただし、偶数なら必ずあるわけではない。$4\times n$ の盤には閉じた巡回が無いことが知られている。
観察 4.3 検算で、一度探し方を誤った。行き先の少ないマスへ進む規則を乱数でくり返すだけでは、$6\times6$ の閉じた巡回が $300$ 回で一つも見つからなかった。その規則は開いた巡回はよく見つけるが、最初へ戻ることは気にしない。枝を刈る探索に替えて見つけた。
5. 分離子
観察 5.1 分離子は、マスの数の偶奇(二色の数が等しいか)である。奇数なら二色の数が一つずれ、閉じた巡回が無く、巡回は多い色からしか始まらない。偶数なら二色が等しくなり、その縛りは消える。
観察 5.2 論文601・348 と並べる。601 は、15 パズルの局面の半分が届かないのは盤が二色に塗れるからだと示した。348 は、全部を一度ずつ回る並べ方が、繋ぐだけより高くつくことを示した。ここでは同じ二色の塗り分けが閉じた巡回を禁じ、全探索という高い手間を払わずに答を言い当てる。
観察 5.3 言わないこと。巡回の総数の一般式は扱わない。偶数でも閉じた巡回が無い盤の分類も扱わない。示したのは、$5\times5$ の全探索と塗り分けの数えの一致、偶数の盤で閉じた巡回を見つけたことである。
6. 点呼と結び
- $5\times5$ の巡回は $1728$ 本(計算 2.1):向きを区別して。
- 閉じた巡回は $0$ 本(計算 2.1):最初へ戻れない。
- 少ない色から始まる巡回は $0$ 本(計算 2.1):多い色からだけ。
- 角から $304$ 本(計算 2.1):四隅は多い色。
- ナイトは一手ごとに色を替える(観察 3.1):本稿の芯。
- $13$ 対 $12$ で多い色に始まり多い色に終わる(観察 3.1):戻る一手が無い。
- 塗り分けが全探索を言い当てる(観察 3.2):二つの道筋。
- $6\times6$・$8\times8$ には閉じた巡回がある(計算 4.1):見つけて確かめた。
- 乱数の規則では $6\times6$ の閉じた巡回が見つからなかった(観察 4.3):探し方を替えた。
- 分離子はマスの数の偶奇(観察 5.1):論文601 と同じ塗り分け。
結び:ナイトで盤の全マスを一度ずつ回り、最初のマスへ戻れるか。マスの数が奇数の盤では、戻れない。$5\times5$ を全部探すと、$1728$ 本の巡回のうち最初へ戻れるものは $0$ 本で、巡回はすべて $13$ マスの色から始まり、$12$ マスの色からは一本も始まらなかった。ナイトは一手ごとに色を替えるからである。$25$ マスの道筋は多い色で始まり多い色で終わり、その二つを一手で結ぶことはできない。塗り分けは、道筋を一本も調べずに全探索の結果を言い当てた。分離子は、マスの数の偶奇である。$6\times6$ と $8\times8$ では二色が等しく、閉じた巡回が見つかった。既刊との位置、論文601 の二色の塗り分けが、ここでは閉じた巡回を禁じ、論文348 の高くつく並べ方の答を先に言い当てる。正直に言えば、巡回の総数の一般式にも、偶数でも巡回が無い盤にも入っていない。
参考文献
- Schwenk, A. J. (1991). Which rectangular chessboards have a knight’s tour? Mathematics Magazine.
- Warnsdorff, H. C. (1823). Des Rösselsprunges einfachste und allgemeinste Lösung.
- 山岸勇輝 (2026). 『同じグラフで、繋ぐのは安く、並べるのは高い』[論文348]. Zenodo. 10.5281/zenodo.22683555
- 山岸勇輝 (2026). 『15 パズルの局面の半分は、どう動かしても届かない』[論文601]. Zenodo. 10.5281/zenodo.22805752
作成にあたって:本稿の着想と内容は、著者自身の考察に基づくものです。文章の構成整理や英訳、数式の確認には AI(大規模言語モデル)の助力を得ました。最終的な内容の解釈や誤りがあれば、それらはすべて著者の責に帰します。お気づきの点があれば、ご教示いただければ幸いです。
書誌
山岸勇輝(2026)「マスの数が奇数の盤には、ナイトが最初のマスへ戻る巡回が無い」[論文625]. Zenodo.
DOI: 10.5281/zenodo.23014535
日付の証拠(OpenTimestamps):日本語版の .ots・英語版の .ots・SHA256SUMS
予備の置き場所(ミラー。中身は上と同じです):PDF 日本語・PDF English・SHA256SUMS
住所:https://www.yamagishiyuuki.com/yoi/625・DOI 10.5281/zenodo.23014535・CC BY 4.0・プレプリント(査読を経ていません)・ORCID 0009-0006-8587-3450
引用するとき
山岸勇輝 (2026). マスの数が奇数の盤には、ナイトが最初のマスへ戻る巡回が無い [論文625]. YOI: https://www.yamagishiyuuki.com/yoi/625 ・ DOI: 10.5281/zenodo.23014535
Yamagishi, Y. (2026). On a Board with an Odd Number of Squares, No Knight's Tour Returns to Its Start [Paper 625]. YOI: https://www.yamagishiyuuki.com/yoi/625; DOI: 10.5281/zenodo.23014535
@misc{yamagishi2026yoi625,
author = {Yamagishi, Yuuki},
title = {On a Board with an Odd Number of Squares, No Knight's Tour Returns to Its Start},
year = {2026},
howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/625},
doi = {10.5281/zenodo.23014535},
note = {Preprint, edition 1}
}
指紋(SHA-256)と確かめ方
da3f6332957e890fda1994ce5c6d121e30758ec59cd6de412417dd6c6e9063d4 yamagishi_yoi625_v1_jp.pdf8388bb7bea6f2c64e5f0a4966baa6674fa6afd094fcef14ec1224d1a3bf952f3 yamagishi_yoi625_v1_en.pdfPDF と .ots を同じ場所に保存し、opentimestamps.org に .ots、続けて PDF を落とすと、記録された日時が表示されます。PDF が 1 バイトでも変わっていれば通りません。