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