ナイト・ツアー
ナイト・ツアーとは、チェス盤のすべてのマスをちょうど1回ずつ訪れる、ナイトの手の連なりです。娯楽数学で最も古いパズルの一つで、9世紀のインドの詩には盤の半分を巡るツアーが登場し、レオンハルト・オイラーは1759年にこのパズルを研究しました。
古いパズル
9世紀にインドの詩人ルドラタが書いた『カーヴィヤーランカーラ』では、ある詩句がチェス盤の半分に並べられていて、ナイトの道筋に沿って読めるようになっています。レオンハルト・オイラーは1759年にナイト・ツアーについて初めての数学的研究を書き、ツアーを組み立てる方法や、それを閉じたツアーに変える方法を示しました。
グラフの中の道
各マスを点、ナイトの各手を2つの点を結ぶ線と考えます。すると、ナイト・ツアーはすべての点をちょうど1回ずつ通る道になります。数学者はこれをハミルトン路と呼び、閉じたツアーはハミルトン閉路です。たいていのネットワークでは、このような道を見つけるのはとても難しいことです。ナイトのネットワークは気前がよく、ツアーがとても多いので、よい規則があればすぐに1つ見つかります。
ワーンスドルフの法則
H. C. フォン・ワーンスドルフは1823年にこの法則を示しました。いつも、その先に動ける手がいちばん少なく残るマスへ跳ぶ、というものです。端に沿ったマスは隣が少ないので、この法則はそれらを取り残さず、早めに訪れます。2つのマスが同点のときは選ばなければならず、運の悪い選び方をすると、それでもナイトが行き詰まることがあります。アプリでは、金色の数字がこの法則の選ぶマスを示します。
バックトラックによる探索
「解く」はワーンスドルフの順序に従いますが、それをうのみにはしません。深さ優先で探索し、まだ訪れていないマスにもう到達できなくなったとたん、その枝を捨てて次の手を試します。10×10までの盤では、たいていすぐにツアーを見つけます。あなた自身の道筋でナイトが閉じ込められているときは、まず数手戻ります。
色と閉じたツアー
ナイトの手はどれも、マスの色を変えます。5×5のような一辺が奇数の盤では、隅の色のマスがもう一方の色より1つ多いので、ツアーは隅の色で始まり、隅の色で終わらなければなりません。そこでは閉じたツアーは不可能です。色が交互に並ぶ閉路では、それぞれの色のマスが同じ数になるからです。一辺が偶数の盤では、6×6以上で閉じたツアーがあります。
PictorX で試す
ナイト・ツアーを開き、マスをクリックして始めます。光っているマスは合法な跳び先、金色の数字はワーンスドルフの選択で、盤には手の順番が残ります。「サイズ」で盤を5×5から10×10まで設定でき、「閉じたツアー」を選ぶと「解く」は閉路を探し、「元に戻す」でどの手も取り消せます。完成した道筋は PNG で保存します。
よくある質問
ナイト・ツアーを最初に研究したのは誰ですか？
ツアーは、数学的に研究されるずっと前から知られていました。レオンハルト・オイラーが1759年に初めて数学的に論じ、ワーンスドルフが1823年に自分の法則を示しました。
どの盤にもツアーはありますか？
5×5以上の正方形の盤には開いたツアーがあり、そのうち6×6以上で一辺が偶数の盤には閉じたツアーもあります。2×2、3×3、4×4の盤には、ツアーはまったくありません。
チェス盤にはツアーがいくつありますか？
あるツアーと、それを逆向きにたどった同じツアーを別々に数えると、閉じたツアーは 26,534,728,821,064 通りあります。開いたツアーの数は約1京9600兆です。
PictorX は何かをアップロードしますか？
いいえ。盤はブラウザーのキャンバスに描かれます。「保存」は PNG をダウンロードし、「編集」はその画像を PictorX のエディターで開きます。
関連ツール
ナイト・ツアー
チェスのナイトを跳ばして、盤のすべてのマスをちょうど1回ずつ訪れます。ワーンスドルフのヒントを頼りに自分で遊ぶことも、「解く」が開いたツアーや閉じたツアーを完成させるのを見ることもできます。道筋は PNG で保存できます。
エイトクイーン
チェス盤に8個のクイーンを、どれも互いに攻撃しないように置きます。自分で試したり、バックトラックの探索が1ステップずつ解を見つけるようすを見たり、92通りの解を順に見たりできます。
エイトクイーン問題
エイトクイーン問題の歴史と数学。マックス・ベッツェルとガウス、12のグループに分かれる92通りの解、n クイーン問題、そしてバックトラック。
ハノイの塔
ブラウザで円盤の塔を3本の棒の間で動かします。1回に1枚、大きな円盤を小さな円盤の上に置くことはできません。最短の解は 2ⁿ − 1 手です。
ハノイの塔
ハノイの塔：3本の棒、1回に1枚、大きな円盤は小さな円盤の上に置かない。最短の解は 2ⁿ−1 手。エドゥアール・リュカが1883年に発表したパズルです。
ラングトンのアリ
ブラウザでラングトンのアリを動かしましょう。対称、カオス、104 ステップのハイウェイを観察し、多色の規則、複数のアリ、六角格子、ターマイトも試せます。
試してみますか？
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
ナイト・ツアーを試す