ナイト・ツアー (Knight's Tour) という有名なパズルがあります。タイトル画像はNightですが、チェスの駒のKnight。8x8のチェスボード上でナイトを移動させ、64マスすべて1度だけ通るツアーをさがせ、というパズルです。

64マスもあって難しそうですが、次の図のように、すべてのマスを通って最初にいたマスに戻ることもできます。

Wikipediaによると、このような最初のマスに戻るツアーだけで26534728821064通りもあるようです。Wikipediaに書かれているように、ツアーを見つけるアルゴリズムやヒューリスティックがいくつかあります。

3D ナイト・ツアーはあるのだろうか？と思いました。8x8という平面のチェスボード上ではなく、8x8x8の立方体の中の512マスをすべて1度だけ通ることができるだろうか？

3Dのナイトは図のように24箇所のマスに移動できることとします。

プログラムを書いて実行してみると、最初のマスに戻るツアーが見つかりました。いけちゃうんですね。

ところでネット上には3D ナイト・ツアーの事例がいろいろ見つかります。たとえばSt. Olaf Collegeには、数学者のLoren Larsonが作成した木製の作品が飾られているそうです。交差していない3D ナイト・ツアーの最長経路を登録できるサイトもありました。交差せずにすべてのマスを通ることはできないため、一番長い経路を見つけようという試みです。更新するのは難易度が高そうです。

あれ、ローレン・ラーソン？この名前昔から知ってるぞ！中高生のころ好きだった「数学発想ゼミナール」はローレン・C・ラーソンの本じゃないか！このnoteを最初に書いてから1年半後に気づきました。笑。すごいめぐり合わせだなぁ。

最初のマスに戻らず、カドからスタートして反対側のカドでゴールするツアーはあるのでしょうか？まっすぐに伸びた1本の線の一部分がナイト・ツアーになっていたら絵的におもしろそうです。

見つけることができました。

夜景と合わせて"Knight in Night"にしてみました。いくつかの作品をRaribleでNFTにしたので、興味があったら購入して保有してください。気に入っている作品です。

道路標識のポールは4x4x4のツアーにしてみました。

もっと大きな立方体でも試したい。1辺を2倍にして、16x16x16=4096マスで解いてみます。8x8x8のときより密になっていい感じです。

次は1辺をさらに3倍にして、48x48x48=110592マスです。一気に10万マスを超えました。びっしりです。中になにかいそう。すきまに飛び込んで反対側に抜ける冒険をしてみたくなります。

100x100x100=100万マスでもツアーは見つけられますが、1辺の長さの3乗で体積が増えていくので、立体を作るのはどんどん厳しくなっていきます。