ナイト・ツアー

ナイト・ツアー（Knight's Tour）は、チェスを使った数学的パズルの一種。「騎士の巡歴（じゅんれき）」「桂馬拾い」とも呼ばれ、チェスをモチーフにしたパズルの中でも昔からよく知られている。チェスボード上のナイトを移動させ、64マス全てを一回ずつ通過させる。

 解答例 
右図の解答は、レオンハルト・オイラーの創案によるもの。ナイトが通過する順に数字が振られている。またこの図はファイル（縦列）・ランク（横列）の各数字の合計が、すべて260になる。

他の解答例は、以下の通り。

 計算による記録 
近年の計算技術の進展により、非常に大きな盤面に対するナイトツアー問題の解が得られている。2025年、探索順を固定した場合には最大で304×304、探索順をランダム化した場合には最大で48×48の盤面で解が得られた。これらの結果は、決定的アルゴリズムのスケーラビリティの拡大や、探索順序が探索性能に与える影響を示している。

これらの成果に用いられたアルゴリズムのソースコード、解説、画像、結果のシーケンスと検証用コード等々は、次に記載されている。

参考: https://github.com/masakatu-o

 外部リンク 
 The knight's tour（英語）
 Knight's tour notes（英語）
 インタラクティブなナイトツアー・パズル（多言語ウェブ版）

 脚注 

Category:数学パズル
Category:チェス