騎士のツアー

ナイトの巡回とは、チェス盤上のナイトが各マスを1回ずつ巡回する一連の動きのことである。ナイトが最初のマスからナイト1手分のマスで終わる場合（同じ経路をたどってすぐに再び盤上を巡回できる）、巡回は閉じている（または再入可能）である。そうでない場合は開いている。^{[1] [2]}

ナイトツアー問題は、ナイトツアーを見つける数学的な問題です。ナイトツアーを見つけるプログラムを作成することは、コンピュータサイエンスの学生によく与えられる問題です。^{[3]ナイトツアー問題のバリエーションには、通常の}8×8とは異なるサイズのチェス盤や、不規則な（長方形でない）ボードが含まれます。

ナイトツアー問題は、グラフ理論におけるより一般的なハミルトン経路問題の一例である。閉じたナイトツアーを見つける問題も同様にハミルトン閉路問題の一例である。一般的なハミルトン経路問題とは異なり、ナイトツアー問題は線形時間で解くことができる。^[4]

騎士の巡回問題に関する最も古い文献は、西暦9世紀に遡る。ルドラタの詩学に関するサンスクリットの著作であるカヴィヤランカラ^{[5] (5.15)では、半盤上の騎士の巡回パターンが、}トゥラガパダバンダ、つまり「馬の歩調の配置」と呼ばれる精巧な詩的表現 ( citra-alaṅkāra )として表現されている。同じ詩が4行に8音節ずつ書かれており、左から右に読むか、巡回中の騎士の軌跡を追って読むことができる。サンスクリット語に使用されているインド語の表記体系は音節であるため、各音節はチェス盤のマス目を表すものと考えることができる。ルドラタの例は以下のとおりである。

翻字:

たとえば、最初の行は左から右に読むことも、最初の四角から 2 行目の 3 番目の音節 (2.3) に移動し、次に 1.5、2.7、4.8、3.6、4.4、3.2 と読むこともできます。

14世紀、シュリー・ヴァイシュナヴァ派の詩人で哲学者のヴェーダーンタ・デーシカは、シュリーランガムの神ランガナータの神聖なサンダルを称賛する1,008節からなる大作「パドゥカ・サハスラム」（第30章「チトラ・パダティ」 ）の中で、それぞれ32文字（アヌシュトゥブ韻律）を含む2つの連続したサンスクリット語の詩を作曲しました。2番目の詩は、 4×8の盤上で左上隅からナイトツアーを実行することで、最初の詩から導き出すことができます。 ^[6]音訳された19番目の詩は次のとおりです。

上記の詩節に対してナイトツアーを実行することで得られる第20詩節は次のとおりです。

sThi thA sa ma ya rA ja thpA

ga tha rA mA dha kE ga vi |

ドゥ・ラン・ハ・サム・サ・ナ・タ・ダ

サ・ディヤ・タ・パ・カラ・サラ ||

デシカは挑戦として、1,008の詩節（上記の特別なチャトランガ・トゥランガ・パダバンダムを含む）すべてを一晩で作曲したと考えられています。 ^[7]

1600年頃または1700年頃に書かれたサンスクリットの儀式、法律、政治に関する百科事典であるバガヴァンタバスカラビの第5巻に報告されているツアーには、3人の騎士のツアーが記述されています。ツアーは再入可能であるだけでなく対称的でもあり、詩は同じツアーに基づいており、異なるマスから始まります。^[8]ニラカンタの作品は、完全に対称的な閉じたツアーという並外れた成果であり、オイラー（1759年）の研究より少なくとも60年先行しています。

ニラカンタの後、騎士の巡回を研究した最初の数学者の一人はレオンハルト・オイラーでした。騎士の巡回を完了するための最初の手順は、1823年にHCフォン・ヴァルンスドルフによって初めて説明されたヴァルンスドルフの規則でした。

20 世紀には、ウリポグループの作家たちがこの技法を採用しました。最も有名な例は、ジョルジュ ペレックの小説『人生 マニュアル』の章の順序を決める10 × 10騎士の巡回です。

2010年の世界チェス選手権の第6試合、ヴィスワナタン・アナンドとヴェセリン・トパロフの間で行われた試合では、アナンドがナイトを13回連続で動かした（ナイトを両方使ったにもかかわらず）。オンライン解説者は、アナンドが試合中にナイトの巡回問題を解こうとしていたと冗談を飛ばした。

シュヴェンク^[10]は、 m ≤ nの任意のm × nボードに対して、次の3つの条件のうち1つ以上が満たされない 限り、閉じたナイトツアーが常に可能であることを証明した。

1. mとnは両方とも奇数である
2. m = 1、2、または4
3. m = 3 かつn = 4、6、または 8。

Cullらと Conradらは、小さい方の寸法が 5 以上の任意の長方形の盤面には、ナイトの巡回 (おそらくは開いている) が存在することを証明しました。^{[4] [11]} m ≤ nの任意のm × n盤面では、次の 3 つの条件の 1 つ以上が満たされない限り、ナイトの巡回が常に可能です。

1. m = 1または2
2. m = 3かつn = 3、5、または6 ^[12]
3. m = 4かつn = 4である。 ^[13]

8 × 8 のボードには、ちょうど 26,534,728,821,064通りの有向閉巡回があります(つまり、同じ経路を反対方向に移動する 2 つの巡回は、回転や反射と同様に別々にカウントされます)。^{[14] [15] [16]}無向閉巡回の数はこの数の半分です。すべての巡回は逆方向にたどることができるためです。6 × 6 のボードには 9,862 通りの無向閉巡回があります。^[17]

コンピューターを使って、与えられた盤上でナイトツアーを見つける方法はいくつかあります。これらの方法には、アルゴリズムもあれば、ヒューリスティックなものもあります。

ナイトの巡礼を力ずくで探すのは、最も小さな盤面以外では非現実的である。 ^[18]例えば、8×8の盤面では、ナイトの巡回数は13,267,364,410,532回^[14]、同じ長さのナイトの移動シーケンスの数ははるかに多い。このような大規模なセットで演算を実行することは、現代のコンピュータ（またはコンピュータネットワーク）の能力をはるかに超えています。しかし、この数の大きさは問題の難しさを示すものではなく、「人間の洞察力と創意工夫を使えば、それほど困難なく」解決できます。^[18]

ボードを小さなピースに分割し、各ピースにツアーを構築し、ピースをつなぎ合わせることで、ほとんどの長方形のボード上で線形時間、つまりボード上のマスの数に比例した時間でツアーを構築することができます。^{[11] [19]}

ワーンスドルフの法則は、 1 人のナイトの巡回を見つけるためのヒューリスティックです。ナイトは常に、最も少ない移動回数で進むマスに進むように移動されます。候補となる各マスの前進回数を計算する際、すでに訪れたマスを再度訪れる移動はカウントしません。前進回数が同じ選択肢が 2 つ以上ある場合もあり、そのような同点を解消する方法はさまざまです。たとえば、ポール^[20]やスクイレルとカル^{[21]が考案した方法などがあります。}

この規則は、より一般的にはどのグラフにも適用できる。グラフ理論的には、各移動は最小次数の隣接頂点に対して行われる。^[22]ハミルトン経路問題は一般にNP困難であるが、実際に発生する多くのグラフでは、このヒューリスティックにより線形時間で解をうまく見つけることができる。^[20]ナイトツアーはそのような特殊なケースである。^[23]

このヒューリスティックは、1823 年に HC von Warnsdorf によって「Des Rösselsprungs einfachste und allgemeinste Lösung」で初めて記述されました。^[23]

ウォーンスドルフの法則を用いて任意の開始位置のナイトツアーを見つけるコンピュータプログラムは、ゴードン・ホーシントンによって書かれ、1984年にCentury/Acorn User Book of Computer Puzzlesという本で出版されました。^[24]

ナイトツアー問題は、ニューラルネットワークの実装によっても解決できます。^[25]ネットワークは、すべての正当なナイトの動きがニューロンによって表されるように設定され、各ニューロンはランダムに「アクティブ」または「非アクティブ」（出力 1 または 0）に初期化されます。1 は、ニューロンがソリューションの一部であることを意味します。各ニューロンには、0 に初期化される状態関数（後述）もあります。

ネットワークの実行が許可されると、各ニューロンは、次の遷移ルール​​に従って、隣接するニューロン (ナイト 1 手分離れたニューロン) の状態と出力に基づいて、状態と出力を変更できます。

$${\displaystyle U_{t+1}(N_{i,j})=U_{t}(N_{i,j})+2-\sum _{N\in G(N_{i,j})}V_{t}(N)}$$

$${\displaystyle V_{t+1}(N_{i,j})=\left\{{\begin{array}{ll}1&{\mbox{if}}\,\,U_{t+1}(N_{i,j})>3\\0&{\mbox{if}}\,\,U_{t+1}(N_{i,j})<0\\V_{t}(N_{i,j})&{\mbox{otherwise}},\end{array}}\right.}$$

ここで、 は離散的な時間間隔を表し、は 平方から 平方 を接続するニューロンの状態、はからへのニューロンの出力、 はニューロンの近傍の集合です。 ${\displaystyle t}$${\displaystyle U(N_{i,j})}$${\displaystyle i}$${\displaystyle j}$${\displaystyle V(N_{i,j})}$${\displaystyle i}$${\displaystyle j}$${\displaystyle G(N_{i,j})}$

発散するケースも考えられますが、ネットワークは最終的に収束するはずです。これは、時刻から時刻までニューロンの状態が変化しない場合に発生します。ネットワークが収束すると、ネットワークはナイトツアーをエンコードするか、同じボード内に 2 つ以上の独立した回路のシリーズをエンコードします。 ${\displaystyle t}$${\displaystyle t+1}$

• アブ・バクル・ビン・ヤヒヤ・アル・スリー
• 8つのクイーンのパズル
• ジョージ・コルタノフスキー
• 最も長い交差していない騎士の道
• 自己回避歩行

• ウィキメディア・コモンズのナイツ・ツアーズに関連するメディア
• OEISシーケンス A001230 (2n x 2n チェス盤上の無向の閉じたナイトの巡回回数)
• Google ブックスの HC von Warnsdorf 1823
• ジョージ・ジェリスによるナイトのツアーの紹介
• ジョージ・ジェリスによるナイトのツアーの完全な記録
• Philip, Anish (2013)。「画像の暗号化のための一般化擬似ナイトツアーアルゴリズム」。IEEE Potentials。32 ( 6): 10–16。doi : 10.1109 /MPOT.2012.2219651。S2CID 39213422  。