ホーム > 家族のギャラリー > ペントミノを解く > 第5章 C言語版の高速化あれこれ > 6. ピース配置の事前計算にXピース考慮

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
1Xピースの中心が B3 のとき1,508
2Xピースの中心が C2 のとき1,491
3Xピースの中心が C3 のとき1,326
4Xピースの中心が D2 のとき1,422
5Xピースの中心が D3 のとき1,239
6Xピースの中心が E2 のとき1,405
7Xピースの中心が E3 のとき1,222
表6-1 ボード上のピースの置き方数

【↑高速化インデックスへ】