ホーム >
家族のギャラリー >
ペントミノを解く >
第5章 C言語版の高速化あれこれ >
3. 5の倍数の空きチェック
3. 5の倍数の空きチェック
ピースを置いていない連続した場所が（図3-1の薄緑のスペース）が5の倍数でない限り、ペントミノを完成させることはできません。B2座標が孤立しているので、薄緑のスペースは49個となり5の倍数ではありません。この空きスペースの面積をチェックするのが、5の倍数の空きスペースチェックです。
次にピースを置く場所（図3-1の赤い×）を基準にして、連続したスペースの数を数え、５の倍数でない場合には、Ｖ字ピースの配置は上手くいかないことが分かり、これ以上の無駄な探索を行うことがなくなり、高速な検索が可能になります。
 |
| 図3-1 |
連続した空きスペースには他にも、図3-2のような閉じたスペースのケースがあります。
 |
| 図3-2 |
このチェックを行ったことにより、探索回数は大幅に減ります。しかし、実装していた連続した空きスペースの探索アルゴリズム（下記に説明）は、あまり速くないため全体の処理時間は長くなってしまいました。
5の倍数の空きスペース探索アルゴリズム
連続した空きスペース数を数えるアルゴリズムは以下のように簡単なものです。
まず、次にピースを置く位置をposx, posyとし、search_blank関数を呼び出します。関数内では、呼ばれた位置に空き領域にフラグを立てながら、再帰的に上下左右の空き方向を探し、あたかもボード上を動きまわるように繋がった空き領域にフラグを立てます。
関数から返ってきたら、blank_no にスペースの数が入っているので、この値が５の倍数かチェックします。Ｃ言語だと上記のように、balnk_noを５で割った余りが０かどうかで判定します。（％は余りを求める演算子）最後に立てたフラグをクリアします（この関数は別にあります）。
/* 呼ぶ方法 */
blank_no = 0;
search_blank(posx, posy);
if (blank_no%5==0) { OK の処理 }
else { NGの処理 }
/* 呼ばれる関数 */
void search_blank(int x,int y) {
board[x][y] = VACANT_FLAG;
blank_no++;
if (board[x][y+1]==VACANT) search_blank(x,y+1);
if (board[x+1][y]==VACANT) search_blank(x+1,y);
if (board[x-1][y]==VACANT) search_blank(x-1,y);
if (board[x][y-1]==VACANT) search_blank(x,y-1);
}
※VACANT_FLAG, VACANTは定数値 99999 と 0 です。