ホーム >
家族のギャラリー >
ペントミノを解く >
第5章 C言語版の高速化あれこれ >
7. ピース配置の事前計算時に5の倍数の空きチェック
7. ピース配置の事前計算時に5の倍数の空きチェック
6. ピース配置の事前計算にＸピース考慮で述べたように図7-1(a)のような配置は、連続したスペースが5の倍数でなくなるので実際には置けない。このようなケースになっていないか、空きスペースの5の倍数チェックを事前計算の段階で行っておき探索数を削減する。
ボードへの配置時に空きスペースの5の倍数チェックを行うと、チェック数が膨大になり枝刈りのコストが高くなる（3. 5の倍数の空きチェック参照）が、置けるピースの事前計算の際ならばそれほどコスト高にならない。（ただし、3*20の場合には事前計算時間の占める割合が増加し、トータル時間が長くなっている。）
結局、A1座標で L ピースが置ける置き方は図7-1(b)のみとなり、ピースの置き方の探索数が、何も考慮しない場合に比べ、1/8 に減少した。
 |
 |
|
| (a) | (b) | |
| 図7-1 置けるピースの事前計算時の枝刈り | ||
同様に図7-2(a)〜(c)のようなパターンも5の倍数の空きチェックで無効な配置を事前に排除できる。
 |
 |
 |
| (a) | (b) | (c) |
| 図7-2 事前計算時の枝刈り（他のパターン） | ||
実際にこの方法で枝刈りを行ったピースの置き方の総数は以下の通り。このチェックを行わなかった場合に比べ、20%前後減っている。これにより、実際にピースが置けるかどうかの探索を行うときの計算量が減り、12%ほどの処理時間短縮になった。
| ||||||||||||||||||||||||||||||||||||
| 表7-1 ボード上のピースの置き方数 |
ただし、ピースの配置によってボードが２つ以上の領域に分割されてしまうケースでは、正しく５の倍数を検出できないことがある。簡単な例として、図7-3のように3*20のボードで示す。
５の空きスペース検出のスタートを、配置したピース（Zピース）より右側から開始すると空きスペースは５となり、置くことができる配置方法にみえる。しかし、Zピースの左側や、Xピースの左側は５の倍数ではないので、この配置方法は実際には不可である。
分断された場合には、それぞれの空き領域内で５の倍数チェックを行えばいいが、そこまで検査してもコストがかかり高速化には繋がらない。とくに、6*10のボードでは殆ど発生しないので無視できる。
 |
| 図7-3 チェックできないケース |