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が作成した木製の作品が飾られているそうです。

また、Uncrossed、つまり交差していない3D ナイト・ツアーの最長経路を登録できるサイトもありました。交差せずにすべてのマスを通ることは残念ながらできないので、一番長い経路を見つけようというわけです。

ところで、最初のマスに戻らず、カドからスタートして反対側のカドでゴールするツアーはあるのでしょうか?

これは見つけることができました。なんでカドからカドへ行きたいかというと、まっすぐに伸びた1本の線の一部分がナイト・ツアーになっていたら絵的におもしろいかなと思ったからです。

イメージが浮かんだので夜景と合わせてみました。タイトルは"Knight in Night"。PCならクリックで大きな画像になります。

道路標識のポールとかどうでしょう。これは4x4x4のツアーです。

8x8x8が解けたのなら、もっと大きな立方体で試したくなります。1辺を2倍にして、16x16x16=4096マスにしても解けるのでしょうか?

解けました。8x8x8のときより密になっていい感じです。

もっと大きいのいきます。1辺をさらに3倍にして、48x48x48=110592マスです。一気に10万マスを超えました。このサイズだとびっしりです。すきまに飛び込んで反対側に抜ける冒険をしてみたくなります。

さらに1辺を2倍強、100x100x100=100万マスでも解けました。でも1辺が2倍になるとマスの数は8倍、1辺が3倍なら27倍に膨れ上がりますので、CGを作るのは厳しくなってきます。

以上3D ナイト・ツアーで遊んでみました。行き詰まって乗り越えて楽しかったです。

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

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

活動を充実させたい。

ありがとう!

あのこね anoconne

ふつうのサラリーマンです。忙しいことを理由に10年以上、制作を楽しむことをあきらめて過ごしましたが、限界なので、しまいこんできた想いを形にしていきたいです。プログラミングや、素人ですが、映像、漫画、曲作りに興味があります。
コメントを投稿するには、 ログイン または 会員登録 をする必要があります。