--/--/--

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
2013/07/27

スネークキューブ

スネークキューブというパズルをご存知でしょうか。



最初は蛇のような形の物をクネクネと動かしながら立方体を作るパズルです。


このパズルは最初の蛇のような形にある規則があります。


まず立方体が4個横一列に連続することはありません。
4個横一列に並ぶと3*3*3の立方体が作れないからです。

また2個連続している部分や3個連続している部分があります。

例えば下の画像では左から
右上に3個連続、折れて右下に2個連続、右上に2個連続・・・
という風に連続しています。



数字だけを抜き出せば
3,2,2,3,2,3,2,2,3,3,2,2,2,3,3,3,3
と表せます。

この数字の並びをクネクネと呼ぶことにすると、
3*3*3の立方体を作ることが出来るクネクネは全部で何種類あるでしょうか。

ここで注意しなければいけないことは
3,2,2 というクネクネと
2,2,3 というクネクネは同じ物であるという事です。

そんなことを注意しながら
3*3*3の立方体を作れるクネクネの総数を求めるプログラムを書いてみました。

手順は大きく分けて2つです

①クネクネを生成
②生成したクネクネが3*3*3の立方体になるか確認


クネクネを生成する時は
2か3を追加していって
立方体の合計が27以上になったら終了です。

この時合計が27を超えたものは破棄、
合計が27でも、その反転 (ex: 2,2,3 ←→ 3,2,2)
を見て、反転のほうが値が小さい (ex: 223<322) ときは
それも破棄します。

生成したクネクネが3*3*3の立方体を作れるか確認するのは
3*3*3の格子点のグラフのハミルトン路を求めるのに似ています

考え方はこんな感じ

① 以下のいずれかで解があれば終了
  1.スタート地点を(0,0,0)とする
  2.スタート地点を(0,1,0)とする
  3.スタート地点を(0,1,1)とする

②スタート地点からクネクネによって決まる数2or3だけ進む。
この時進む方向は上下左右前後の6通り。
3*3*3の立方体からはみ出たり、もうすでに通ったところと被ったりするところはfalseとする。
また1回前に進んだ方向と同じ方向には進めない。


それで結果の方はと言いますと以下の通り。

(前略)
3 3 3 2 2 2 2 2 2 2 2 2 2 2 3 2 3 3 3
3 3 3 2 2 2 2 2 2 2 2 2 3 2 2 2 3 3 3
3 3 3 2 2 2 2 2 2 2 3 2 2 2 2 2 3 3 3
3 3 3 2 2 2 3 2 2 2 2 3 2 2 2 3 3 3
3 3 3 2 2 2 3 2 2 2 3 2 3 2 3 3 3
3 3 3 2 2 3 2 2 2 3 3 3 2 3 3 3
3 3 3 2 3 2 2 2 3 2 2 2 3 2 3 3 3
ansNum=2065


全部で2065種のクネクネで立方体が作れるようです。
ただこれが求めたかっただけなんですけど、随分と長い道のりでした。

コメント

非公開コメント

No title

補足ですが
立方体が作れるクネクネは2065個で
立方体が作れないクネクネは14104個っぽいです。
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。