ナイト・ツアーはどんなパズルですか？
ナイト・ツアーは、チェスのナイト1つで盤のすべてのマスをちょうど1回ずつ踏むパズルです。ナイト巡回、騎士の巡歴とも呼ばれます。
ナイトはチェスでただ1つ、ほかの駒を跳び越える駒です。縦か横に2マス進んでから横に1マス曲がり、L字の形に着地します。このゲームではスタートのマスを選んだあと、緑の輪で光るマスを1つずつ押して進みます。通ったマスには1、2、3と順番の数字が真ちゅうのボタンのように残り、マスとマスの間は金色の線で結ばれます。すべてのマスを踏み終えると、重なった線が星や花のような模様になります。
ルールは正確にはどうなっていますか？
ルールは2つです。ナイトの動きでしか進めず、一度踏んだマスはもう踏めません。盤のマスの数だけ踏めば終わりです。
| 盤 | マス数 | スタートできるマス | 閉じたツアー |
|---|---|---|---|
| 5×5 | 25マス | 四隅と同じ色の13マス | なし |
| 6×6 | 36マス | すべてのマス | あり |
| 7×7 | 49マス | 四隅と同じ色の25マス | なし |
| 8×8 | 64マス | すべてのマス | あり |
ナイトは跳ぶたびに明るいマスと暗いマスを交互に踏みます。そのためマス数が奇数の5×5と7×7の盤は片方の色が1マス多く、多いほうの色（四隅と同じ色）からスタートしないと完走できません。ゲームでは完走できるマスにだけ緑の点が出ます。探索プログラムで、5×5の13マスと7×7の25マスすべてから実際に完走できることを確かめています。
ワーンスドルフの規則とは何ですか？
ワーンスドルフの規則は、行けるマスのうち、そこへ行ったときに次の行き先がいちばん少ないマスを先に選ぶ方法です。1823年にドイツのH. C. フォン・ワーンスドルフが発表しました。
行き先の少ないマスは、後回しにするほど孤立しやすくなります。代表は隅や端のマスです。そうしたマスを先に片づけ、行き先の多い中央を最後まで残しておくと、行き止まりに追い込まれることがぐっと減ります。たとえば今行けるマスが3つで、それぞれから次に行ける先が2つ、5つ、3つなら、2つのマスへ行きます。この規則を守るだけで、8×8の盤もたいてい一度で完走できます。
このゲームのヒントは、まずワーンスドルフの順で道をさがし、行き詰まったら戻って別の枝を調べる探索プログラムで、本当に完走できる次のマスを教えます。すでに完走できない道に入っていたら、何手前まで戻れば助かるかをさがしてそのマスを青く光らせ、そのマスを押すと一気にそこまで戻ります。
閉じたツアーとは何ですか？
閉じたツアーは、最後に踏んだマスから最初のマスへナイトがもう一度跳べる形で終わった完走です。始まりと終わりがつながって輪になるので、周遊ツアーとも呼ばれます。
閉じたツアーで終わると、最後のマスと最初のマスの間に光る点線が引かれ、スタートのマスのまわりを星の輪が回り、結果画面に閉じたツアーの回数が出ます。閉じたツアーはマス数が偶数の盤でしかできません。輪になるには明るいマスと暗いマスが同じ数だけ必要だからです。このゲームでは6×6と8×8でねらえます。
ナイト・ツアーはいつからあるのですか？
ナイト・ツアーは千年以上の歴史をもつパズルです。知られている最も古い例は、9世紀のインドの詩人ルドラタの詩論書『カーヴィヤーランカーラ』で、詩の音節を半分の盤の上にナイトの動きの順に並べたものです。
その後イスラム世界のチェスの書物にもナイトの巡回問題が載り、1759年には数学者レオンハルト・オイラーがこの問題をくわしく研究して、閉じたツアーの作り方や対称なツアーをいくつも発表しました。1823年にはワーンスドルフが手作業でも使える規則を示しました。今ではナイト・ツアーはグラフ理論でハミルトン路を説明する代表的な例で、1997年にブレンダン・マッケイは8×8の盤の閉じたツアーが向きを区別せずに13,267,364,410,532通りあると数えました。
完走するコツはありますか？
- 隅と端から片づけましょう。隅のマスは出入りの道が2つしかないので、後回しにすると孤立しやすくなります。
- 行き先がいちばん少ないマスへ。ワーンスドルフの規則そのままです。迷ったら盤の端に近いほうを選びます。
- 赤く点滅するマスに注意。もうたどり着けなくなったマスは赤く表示されます。そのマスが最後のマスになれないなら、すでに失敗した道なので早めに戻しましょう。
- 戻すのをためらわない。1手、5手のボタンのほかに、通ったマスを2回押すとそこまで一気に戻ります。
- 小さい盤から始めましょう。6×6はどこからスタートしても完走できて練習に向いています。5×5と7×7はスタートの制限があるぶん、かえって手ごわいです。
操作方法
- スマホ・マウス: 最初に緑の点があるマスを押してスタートを決めるか、ランダムにスタートを押します。そのあと緑の輪のマスを押すか、ナイトをドラッグして置くと、放物線を描いて跳んで着地します。
- 戻す: 1手ボタンは1つ前のマスへ、5手ボタンは5つ前へ戻ります。通ったマスを1回押すと何手戻るかが表示され、もう1回押すとそこまで戻ります。出直しはスタートのマスから選び直します。
- キーボード: 矢印キーでマスを選び、EnterかSpaceで跳びます。ZかBackspaceで1手、Xで5手戻す、Hでヒント、スタートを選ぶときにRでランダムにスタートします。
- 今日の問題: その日はだれでも同じ盤の大きさと同じスタートのマスで遊び、終えると今日の問題の記録にかかった時間が残ります。
途中の盤面、盤の大きさごとのベスト記録、閉じたツアーの回数はこのブラウザーの中だけに保存され、サーバーには送られません。結果をシェアで送ったリンクを開いた人は、同じ大きさ、同じスタートのマスで挑戦できます。