ホーム > 家族のギャラリー > ペントミノを解く > 第5章 C言語版の高速化あれこれ > 1. ピースは短辺に沿って置く

1. ピースは短辺に沿って置く

ピースはボードの端から順次はめ込んでいくが、図1-1のように長い辺に沿って置く方法と、図1-2のように短い辺に沿って置く方法がある。図中のピース内の番号は、配置した順番を表している。

図1-1の場合、1行目で5番目まで配置したら、2行目に移って6番目を配置する。すると2行目には空きがないので、3行目の左から空きを探して、7番目を配置、次にI4座標に空きが見つかるので、ここに8番目のピースをはめ込む。

図1-2の場合は短い辺に沿って、まず行方向を探索し、空きが無ければ次の列に移り、ピースをはめ込んでいく。

図1-1 長辺に沿って配置		図1-2 短辺に沿って配置

図1-1と図1-2でどちらも同じ処理時間のように思えますが、実は図1-2の短い辺に沿って置く方が高速です。理由は、図1-2のほうが破綻する置き方（最終的に全てのピースをはめ込めない置き方）がはやく見つかり、探索の枝刈りが行われるため。ちなみに図1-2の例は、8番目に置けるピースがなく、破綻する置き方です。