パズルプログラミング勉強会

第１課題：ペントミノ

見てはいけないソース：pentomino.c by パソコン初心者

参考：５×４×３の立体版

パズル勉強会の最初の課題は、この有名なパズルを解くプログラムに挑戦するということだった。 勉強会の、第１回、第２回がこのパズルのために与えられたが、 初心者はプログラミングが遅く、残念ながら間に合わなくて、今ごろ(2001年7月22日) プログラミングに成功し、総数も2339通りと正しく出たのである。 まだ、なんとかプログラムが初心者並には書けることが判明した。

プログラムは、ちょっと６４ビット整数を使ってみようということで始めた。 それで、利用したのが、GNUのCコンパイラ(GCC)である。 他のコンパイラでは全然試していないので、他の場合に動くかどうかは知らない。

動作環境は、先日から使いだしたKondara(Linux)で、CPUはCeleronの700MHzであり、 -O2 でコンパイルしたとき、 2339通り解き終えるのに 8.910sec(user) かかった。 何の最適化もしていないのだから、まあまあかな。

汎用的に作るだけの才能がないので、１０×６専用に作ってある。 １２×５にすら対応していない、とても横着な、いい加減なプログラムなので、 見ても役に立たないと思う。

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

$pentomino
Total Count : 2339
Tryal Count : 10760346


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

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

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

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

$pentomino -s
F . . . . . . . . . 
F F F . . . . . . . 
. F . . . . . . . . 
. . . . . . . . . . 
. . . . . . . . . . 
. . . . . . . . . . 

F . . . . . . . . . 
F F F . . . . . . . 
W F . . . . . . . . 
W W . . . . . . . . 
. W W . . . . . . . 
. . . . . . . . . . 

実際に動かすと、総数が2339通り、ああでもない、こうでもないとコンピュータが試行する回数は 10760346回にも及んでいる。この試行回数は、既にダメなのが簡単に人間なら分かっている場合でも、 ただただ、左側から、上から下に順に調べるという阿呆なアルゴリズムなので、ダメなのである。

たとえば、次の例は、ピース I によって、空き領域が２つに分断され、それぞれの領域の面積が ５の倍数でないので、どうやってもピースが収まらないのがあきらかである。 しかし、このプログラムは、ピース I をここに置いて、さらに先を詰めようとする馬鹿者なのである。 まあ、プログラムが馬鹿というより、作った奴が馬鹿なのであるが。

+---+---+---+---+---+---+---+---+---+---+
| F | V   V   V | P   P   P | .   .   . |
+   +---+---+   +       +---+           +
| F   F   F | V | P   P | .   .   .   . |
+---+   +---+   +---+---+---+---+---+---+
| W | F | U | V | U | I   I   I   I   I |
+   +---+   +---+   +---+---+---+---+---+
| W   W | U   U   U | .   .   .   .   . |
+---+   +---+---+---+                   +
| L | W   W | N   N | .   .   .   .   . |
+   +---+---+---+   +---+---+           +
| L   L   L   L | N   N   N | .   .   . |
+---+---+---+---+---+---+---+---+---+---+

10×6のボードをどう表現するかが重要である。まあ、２次元配列を使ったり、 各ピースは、基準位置を決めて、 そこから残り4マス(セル)の相対座標(x,y)で表現したりするのがごく普通のやりかただと思う。

しかし、初心者は、普通にプログラムを組むのは好きでないので、このボードを、 １つの64ビット整数で表現できないかと考えたのである。 4ビット余ってしまうが、それは無視することにした。 それから、各ピースの全ての置き方を、初期化というか前処理で、全部調べ尽くすことにした。 ボードからはみ出すような置き方は、すべて前処理で調べて、 ボードに収まる置き方の全てを蓄えておくのである。 こうすることで、実際に填めるときに、ボードの外側にはみ出すかどうかのチェックを一切していない。 ボードを64ビットデータで表現し、また各ピースの特定の置き方も64ビットデータで表現しているので、 この2つの64ビットデータのANDをとることで、ぶつかっておけないかどうかが一発で分かる。 配列を使っていたら、この部分がかなり手間がかかる。 また、ピースを置くのはORになり、取り除くのはXORでできる。このあたりはなかなか簡単である。 こんなことをすると、とても時間がかかったり、メモリを浪費すると思うだろうが、決してそんなことはない。 今は、メモリは安い。とくに最近は激安と聞く。 1/1000秒も計算するのは大変なことなのである。

しかし、表示も楽をしようと思ってしまい、実は１次元の配列も使ってしまった。 入るかどうかの検査は64ビット整数で高速にやり、どのピースがはまっているかは、 char型の１次元配列に頼ったのである。軟弱であり、これらのために、少々速度は落ちた。

この問題、思いっきりプログラムを改善すれば、私のコンピュータでも１秒くらいで 解けてもいいかなと思っている。そのためには、いかに効率的に枝刈りをするかであろう。 枝刈りをするのに時間がかかっていては、ちっとも高速にならない。

12種類のピースだが、人間がやる場合、できるだけ入れやすいピースを最後に残しておくだろう。 つまり、どの順番で調べていくかが重要なのである。しかし、まったく枝刈りをしないばあい、 12種類のピースをどの順番で確かめても、結局調べる総数は同じになる。 実際に、プログラムのデータ部分を入れ換えて調べてみた。 これは、考えてみれば当り前である。ピースの調べる順番の入れ換えは、 この探索によりできる木の枝の順番を入れ換える操作に過ぎないのだから、 総数はまったく同じである。

細かい解説は省略しよう。 なんたって、設計とかは何もせず、一気に書き下したのだから、記録が何もないのである。 詳しくは、プログラムを読むと何か分かるかも知れない。 自分でも簡単に忘れてしまいそうだから、ちょっとだけだがコメントを入れておいた。

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