3D ナイト・ツアー
ナイト・ツアー (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乗で体積が増えていくので、立体を作るのはどんどん厳しくなっていきます。
いいなと思ったら応援しよう！
