ホーム > 家族のギャラリー > ペントミノを解く > 第5章 C言語版の高速化あれこれ > 2. 次に置く場所の孤立(1,2個)チェック

2. 次に置く場所の孤立(1,2個)チェック

ピースを置いたときに、置き方によっては次のピースを置く場所に5個分のスペースができないことがあります。各ピースは5個の要素の集まりなので、1〜4個しかスペースがなければ絶対に完成しない置き方になります。

よって、次のピースを置くときにこのような孤立スペースになっていないかをチェックして、実際にピースを置けるかどうかの探索回数を削減するものです。図2-1、図2-2のように次にピースを置く位置(図2-1, 図2-2の赤い×)が、1つのスペースしかない閉じた空間か、2つのスペースしかない閉じた空間かをチェックしています。3つの孤立スペースもチェックするのを試してみましたが、チェック時間がかかる割に探索回数はあまり減らず、かえって遅くなりました。

このチェックを行う場合、×の左側と上側の場所はすでに埋まっている場所なので、右側と下側が閉じていないかチェックすればよいので判定条件が簡単です。つまり速いです。

 
図2-1   図2-2

しかし、このチェック方法では、もし、2つめにVピースを置いて図2-3のようになったとしてもB2座標はチェックされません。図2-4も同様です。このような場合、ピースを置く位置がB2座標になるまで、無駄な配置であることが見つからないことになります。それまでの間に数個のピースが無駄に配置されることになり、処理速度の低下を招きます。これを改善するのが、次に説明する5の倍数の空きスペースチェックです。

 
図2-3   図2-4

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