３Ｄペントミノ(５×４×３)

ここで紹介したペントミノは２次元の１０×６のサイズ のものであったが、おなじピース形状で、３次元に組み上げることが考えられる。

正方形を立方体にし、小さな立方体が、同一平面上で５つ繋がった１２種のピースを、 ５×４×３の直方体に詰め込むことが考えられる。実際、株式会社テンヨーから、 このパズルは商品として売られていた。名称は、FACOMである。名前から明らかに Ｆ社が思い浮かぶであろうが、Ｆ社の協力で全解が求められていたらしい。

さて、３次元になったら２次元の時と比較して大変かというと、そんなことはまったくない。 そもそも、２次元版が、実際のデータは１次元として持っていて、１次元⇔２次元 の変換が 用意されていたので、今度は１次元⇔３次元の変換を用意すれば良いだけに過ぎない。

そういうことで、プログラムはペントミノをちょっと改造しただけで、 特別の最適化とか何もやっていない。原稿〆切の間に、ちょっと気晴らしで変更した程度の 手抜きであるのは我慢して欲しい。まあ、そんな感じで出来るのは、次元が増えてもほとんど 障害にならないことの証明であろう。実際、解説などを書いている時間の方が長い。

プログラムを実際に動かすと、 Kondara(Linux)で、CPUはCeleronの700MHzで、 -O2 でコンパイルしたとき、3940通り解き終えるのに 約18分かかった。 何の最適化もしていないのだから、まあまあかな。 それより、プログラムの改造に２時間かかっていないところの方が重要かな。

コンパイルして動かすと、

$facom
Total Count : 3940
Tryal Count : 1108709132

$facom -p
No. 1
F Y Y Y Y   I I I I I   W L L L L   
F F F Y Z   N N Z Z Z   W W Z T L   
U F V V V   U N N N V   U W W T V   
U X P P P   X X X P P   U X T T T   

No. 2
F V V V N   I I I I I   W Z Z U U   
F F F V N   W P P P N   W Z P P U   
W F X V L   W X X X N   Z Z X U U   
T L L L L   T T T Y N   T Y Y Y Y   


$faom -l
No. 1
+---+---+---+---+---+   +---+---+---+---+---+   +---+---+---+---+---+   
|   |               |   |                   |   |   |               |   
+   +---+---+   +---+   +---+---+---+---+---+   +   +---+---+---+   +   
|           |   |   |   |       |           |   |       |   |   |   |   
+---+   +---+---+---+   +---+   +---+---+---+   +---+   +---+   +---+   
|   |   |           |   |   |           |   |   |   |       |   |   |   
+   +---+---+---+---+   +---+---+---+---+---+   +   +---+---+   +---+   
|   |   |           |   |           |       |   |   |   |           |   
+---+---+---+---+---+   +---+---+---+---+---+   +---+---+---+---+---+   

$facom -p -l
No. 1
+---+---+---+---+---+   +---+---+---+---+---+   +---+---+---+---+---+   
| F | Y   Y   Y   Y |   | I   I   I   I   I |   | W | L   L   L   L |   
+   +---+---+   +---+   +---+---+---+---+---+   +   +---+---+---+   +   
| F   F   F | Y | Z |   | N   N | Z   Z   Z |   | W   W | Z | T | L |   
+---+   +---+---+---+   +---+   +---+---+---+   +---+   +---+   +---+   
| U | F | V   V   V |   | U | N   N   N | V |   | U | W   W | T | V |   
+   +---+---+---+---+   +---+---+---+---+---+   +   +---+---+   +---+   
| U | X | P   P   P |   | X   X   X | P   P |   | U | X | T   T   T |   
+---+---+---+---+---+   +---+---+---+---+---+   +---+---+---+---+---+   

$facom -s
F . . . .   . . . . .   . . . . .   
F F F . .   . . . . .   . . . . .   
. F . . .   . . . . .   . . . . .   
. . . . .   . . . . .   . . . . .   

F . . . .   I I I I I   . . . . .   
F F F . .   . . . . .   . . . . .   
. F . . .   . . . . .   . . . . .   
. . . . .   . . . . .   . . . . .   

F . . . .   I I I I I   W . . . .   
F F F . .   . . . . .   W W . . .   
. F . . .   . . . . .   . W W . .   
. . . . .   . . . . .   . . . . .   

実際に動かすと、総数が3940通り、ああでもない、こうでもないとコンピュータが試行する回数は 1108709132回にも及んでいる。直線状の「I」形の辺は置き方が限られるので、それをプログラムで チェックする前は、試行回数が負数になってしまった。要するに32ビット符号付で表現できなかったのである。 この試行回数は、既にダメなのが簡単に人間なら分かっている場合でも、 ただただ、左側から、上から下に順に調べるという阿呆なアルゴリズムなので、ダメなのである。

5×4×3の直方体も、結局小立方体が60個なので、64ビット整数で表現している。 基本的なやり方は平面のペントミノの時と同じなので、全て省略する。 5×4×3の立体になった場合に違うところだけを以下で若干説明する。

ピース「Ｆ」の置き方を工夫すると、回転で同じになる答えは全部省くことができる。 しかし、これだけであると、鏡映したものは残ってしまうので、解の総数が２倍になってしまう。 さいごに残った鏡映は、実際にプログラムで解が求まる毎に鏡映パターンを生成し、一定規則で パターンの大小を比較し、元のパターンが小さい場合にだけ解としてカウントしている。

高速化のための種々の工夫はしなかったが、１点だけ簡単だったので加えた。 たった２行だったので、横着者でもなんとかなるレベルである。 それは、ピース「Ｉ」を置ける方向が、３軸のうち１つの方向しかない。 ピース「Ｉ」は、4×3の面に垂直にしか置けなくて、なおかつ「Ｉ」の中心軸方向には 動かせないことを利用している。つまり、ピース「Ｉ」は 4×3=12通りの置き方しかできないのである。

これ以上は面倒なので、解説は省略する。

さて、このプログラム、だれが勝手に改良してくれるのだろう。