8. 置ける方向の事前計算時に次に置く場所の座標を計算
ボード上でピースの配置方法を探索する際には、ひとつのピースを置いた後に次のピースの基点を置く空きスペースを探している(ピースは短辺に沿って置く参照)。このとき、置いたピースの基点からそのピース自身が埋めた場所も含めてループを回して探していた。
しかし、5. 置けるピースの事前計算を行うことにより、ピースのボード上での絶対座標が決まるので、自分自身が埋めたところはスキップできるようになる。この計算を行っておくのが今回の高速化だ。
図8-1に例を示す。緑色の L ピースを図のように置いたとき、次に置ける場所を探す基点を赤の×で表している。
(a) (b) 図8-1 次のピースの置き場所検索の基点を計算しておく 今回の改善は探索の枝刈りではなく、探索時の計算量を削減するものである。よって探索数は減っていないが時間は 3%ほど短縮できた。僅かだが、こうした積み重ねが高速化への道だ(と、思いたい)。
【↑高速化インデックスへ】