ホーム > 家族のギャラリー > ペントミノを解く > 第5章 C言語版の高速化あれこれ > 11. 配置方向を途中で切り替える

11. 配置方向を途中で切り替える

1. ピースは短辺に沿って置くで説明したように、ピースは長い辺に沿って置くより短い辺に沿って配置していったほうが無効な置き方が早くみつかり、自然に枝刈りが行われる。

この特性を利用して、2001年1月のヘキソミノプロジェクトの際に、ピースが埋まってきたら配置方向を切り替えることを試してみた。図11-1に示すように、A1座標からピースのはめ込みを始めると、A列からF列までは、縦方向が短い辺だが、G列になると横方向の方が短い辺になる。このため、G列まで来たら配置の方向を切り替える。

この方法は、ボードが大きいヘキソミノでは非常に有効で、4倍ほどの高速化になった。ペントミノでは、それほどの効果は無かったが探索回数は930万回から875万回へと55万回ほど減り、若干時間短縮になった。

この方法をとるには、各ピースについて基点の位置を変えたものを予め2種類用意しなければならず、メモリと多少の処理時間を要するが、前にも書いたように前処理の時間は、1千万回近い探索の時間に比べれば僅かなので無視できる。

図11-1 途中で配置方向を切り替える

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