全解が求まって、一応正しいらしきことは分かったが、やはり高速にしたいものである。もちろん、ガリガリとプログラムをいじって高速にするというのもあるだろうが、そこはちゃんと方針をもって、つまり戦略的に高速化に挑戦していこうと思う。まあ、実際できるかどうかは分からぬが、戦略こそが重要であろう。
まず、対称性のチェックというのがどうも嫌である。求まった解に対して、対称移動を実際に行って、解として採択して良いかどうかを調べるというのは、どう考えても無駄が多い筈である。１つのユニークな解に対して４つの対称解があり、その１つについてだけ答えにしているのであるから、かなり無駄が多いように思われる。つまり、４つに３つは無駄なことをやっている訳である。馬鹿みたいではないか。
もし、何らかの方法で、対称な解は絶対に除かれるなら、求まったものをそのまま解としてしまえば良い。プログラムも実に簡単になると思われる。
と考えたが、そんな魔法の様な対称性除去の方法が存在するだろうか。
ちょっと閃いたのが、上の図の関係である。８通りの向きのあるピースについて、その中の特定の２つの向きを取り出すと、残り６通りの向きは盤の対称移動と同じ移動でできてしまうことが分かる。
２つの特定のピースだが、まず何でもよいから１つ選ぶ。ここでは、F0を選んだ。 F0の上下、左右の反転の繰り返しでできるのは、F2,F4,F6 である。これらを取り除くと、 F1,F3,F5,F7の４つが残る。この中から１つ、たとえば F1を取り出すと、F3,F5,F7 は、 F1に対する上下、左右の反転の繰り返しでできる。つまり、F0とF1だけをピースFの配置パターンとして認めることにするとどうだろうか。
まず、ある解、つまり全部のピースが詰まった解があった場合を考えて、それの対称移動を全部求めてみよう。
つまり、F2,F4,F6のパターンがあっても、許される対称移動をすれば、必ずF0になることが分かろう。同様にして、F3,F5,F7のパターンがあっても必ずF1にすることができる。ということは、Fの配置パターンとして、F0とF1しか認めなければ、上のような場合、解としては１つになる。
これは、ずいぶん簡単な変更である。というか、プログラムを短くすれば、対称性までちゃんと除去できるという、極めて優れたアイデアではないだろうか。
まず、消す部分であるが、対称性のチェックのために作成した関数全部である。
copyboard() 盤面の複製
udmirror() 上下反転
lrmirror() 左右反転
compareboard() 盤面の大小比較
isunique() ユニーク検査
以上は不要なので、ごっそり消してしまおう。
これに伴って、解の候補が見つかったときの foundanswer() は、もう候補ではなく、解に決まっているので無条件に解として取り扱う。そのために、isunique() を呼び出していた部分がきれいに無くなる。
void foundanswer( void )
{
++answercount;
if( printsw ) {
printf( "Answer No. %d\n", answercount );
printboard( board );
}
}
あとは、ピースFの配置データに関する部分である。いままでは、８つの配置パターンがあったが、以下のように、たった２行だけになる。6行削除である。
PieceForm AllPieces[] = {
{ 'F', {{ 0, 0},{ 1, 0},{ 1, 1},{ 1, 2},{ 2, 1}} },
{ 'F', {{ 0, 0},{ 0, 1},{ 1, 1},{ 1, 2},{ 2, 1}} },
{ 'I', {{ 0, 0},{ 0, 1},{ 0, 2},{ 0, 3},{ 0, 4}} },
これに伴って、AllPiecesの中の各ピースに対する配置データがどのように入っているかを示す部分が変更になる。
/* F I L N P T U V W X Y Z */
const int base[PN] = { 0, 2, 4,12,20,28,32,36,40,44,45,53 };
しかし、この部分は、いまのところ AllPieces[] が変更されると、それに伴って手作業で変更しなくてはならず、わずらわしい。そのうち何とかしようと思うが、今回はそのままにしておき、先を急ごう。
これらの変更を加えたのがpentomino20.c である。
出力結果はまったく同じなので、省略する。
実行しているところを見ると、かなり違いがある。pentomino19.cでは、最初は勢い良く解が求まるのだが、最後の方になるにしたがって、次第に表示の勢いがなくなってくるのである。最後の解が表示されてから終るまでの間にしばしの待ち時間が存在した。
しかし、ピースFによる対称性除去を加えたら、表示のペースが最初から最後までほぼ一定な感じである。
さて、実行時間はどのくらい向上したであろうか。
Celeron 700MHz の Kondara(Linux)上で、コンパイラとしてGCCを使い、 gcc -O2 でコンパイルし実行した場合に、ユーザタイムが 22.40秒であった。60%も実行時間が短くなった。さすがに 1/4にはならなかった。
| ソースプログラム
| 実行時間(秒)
| 方法
|
| pentomino20.c
| 22.40
| ピースF による対称性の除去
|
| pentomino19.c
| 55.78
| 全部求めてから対称性を除去
|
もっと高速にできるかなぁ。
２００２年１月５日
