6. ピース配置の事前計算にXピース考慮
高速化の試み 4.に書いたように現アルゴリズムは完成したボードの回転とミラー反転をさけるために、Xピースを配置してから、他のピースの配置を始める方法をとっている。
このため、図6-1のようにXピースが配置されると、(c)〜(f)の4つはXピースとぶつかってしまう。 これを活用し、Xピースを配置した後でボード上の全ての座標に対してその座標に置けるピースと方向を決める。これによりピースの置き方をさらに絞り込む。
Xピースの置き場所は、7通りあるので全座標のピース配置計算を 7回行わなければならないが、このための枝刈りコストはそれほど大きくない。それにボードの左半分だけ再計算すればよい。
図6-1の例では、A1座標で L ピースが置ける置き方は(a),(b)の2通りであり、ボードへのピースの置き方の探索数が 2/6 に減少したことになる。当初の8通りから比べると2/8となる。
さらに、見てわかるように図6-1(a)の置き方は禁止だ。この枝刈りについては、次の高速化の試みを参照。
(a) (b) (c) (d) (e) (f) 図6-1 置けるピースと方向を事前計算 この方法によるピースの置き方の総数は以下の通り。
No. Xピースの位置 ピースの置き方数 - Xピースなし 2,024 1 Xピースの中心が B3 のとき 1,508 2 Xピースの中心が C2 のとき 1,491 3 Xピースの中心が C3 のとき 1,326 4 Xピースの中心が D2 のとき 1,422 5 Xピースの中心が D3 のとき 1,239 6 Xピースの中心が E2 のとき 1,405 7 Xピースの中心が E3 のとき 1,222 表6-1 ボード上のピースの置き方数
【↑高速化インデックスへ】