見出し画像

3D ナイト・ツアー

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

画像1

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

画像2

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

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

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

画像3

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

画像4

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

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

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

夜景と合わせて"Knight in Night"にしてみました。(PCなら大きめ画像あり)

画像5

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

画像6

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

画像7

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

画像8

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

この記事が気に入ったら、サポートをしてみませんか?気軽にクリエイターを支援できます。

note.user.nickname || note.user.urlname

.

ありがとうございます!
3

あのこね anoconne

ふつうのサラリーマン。プログラミング、映像、漫画、曲作りに興味を持っています。
コメントを投稿するには、 ログイン または 会員登録 をする必要があります。