7. ピース配置の事前計算時に5の倍数の空きチェック
6. ピース配置の事前計算にXピース考慮で述べたように図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%ほどの処理時間短縮になった。
No. Xピースの位置 Xピースの考慮後 5の空きチェック後 - Xピースなし 2,024 1,900 1 Xピースの中心が B3 のとき 1,508 1,256 2 Xピースの中心が C2 のとき 1,491 1,169 3 Xピースの中心が C3 のとき 1,326 1,191 4 Xピースの中心が D2 のとき 1,422 1,017 5 Xピースの中心が D3 のとき 1,239 1,062 6 Xピースの中心が E2 のとき 1,405 954 7 Xピースの中心が E3 のとき 1,222 1,027 表7-1 ボード上のピースの置き方数
ただし、ピースの配置によってボードが2つ以上の領域に分割されてしまうケースでは、正しく5の倍数を検出できないことがある。簡単な例として、図7-3のように3*20のボードで示す。
5の空きスペース検出のスタートを、配置したピース(Zピース)より右側から開始すると空きスペースは5となり、置くことができる配置方法にみえる。しかし、Zピースの左側や、Xピースの左側は5の倍数ではないので、この配置方法は実際には不可である。
分断された場合には、それぞれの空き領域内で5の倍数チェックを行えばいいが、そこまで検査してもコストがかかり高速化には繋がらない。とくに、6*10のボードでは殆ど発生しないので無視できる。
図7-3 チェックできないケース
【↑高速化インデックスへ】