ま、通常ルールの数独なら9x9マスですから、1面は基本81マス。1マスが4バイト（32ビットint値）としても324バイトで局面を保存できるので、ま、バックトラックで問題なく処理できるかなと。
ま、単なる思いつきなんですが。
以前、Perlで同様のアルゴリズムを処理させたときも、全パターンを総ナメにした場合でも処理に要する時間はそれほどでもなかったので、Cならもっと早いんだろうなとか思っていて、バックトラックでの処理が一番合理的に思えました。
実装としては再帰で記述するのが一番判り易い気がしました・・・ので、作ってみた。
#define GOBAN_X 9
#define GOBAN_Y 9
#define GOBAN_T 3
#define GOBAN_N 9
/* バックトラック（再帰部分）
引数 座標ix,iy
戻り値 0:成功、-1:失敗
*/
int getans(int ix, int iy, int number, struct GOBAN konkai) {
int cx, cy;
int sx, sy;
int x, y;
/* 次の空き座標をチェック */
while (konkai.number[ix][iy] != 0) {
/* なんか入ってた */
ix++;
if(ix >= GOBAN_X) {
ix = 0;
iy++;
if(iy >= GOBAN_Y) {
/* 全部のマスが埋まったので
正解が導き出されたと判断する
*/
/* 結果をグローバル変数にコピーする */
for (y = 0; y < GOBAN_Y; ++y) {
for (x = 0; x < GOBAN_X; ++x) {
goban.number[x][y] = konkai.number[x][y];
}
}
return 0;
}
}
}
/* 値が入るのか!? */
/* ヨコ列のチェック */
for(cx = 0; cx < GOBAN_X; ++cx) {
if(konkai.number[cx][iy] == number) {
/* 重複した値があったよ */
return -1;
}
}
/* タテ列のチェック */
for(cy = 0; cy < GOBAN_Y; ++cy) {
if(konkai.number[ix][cy] == number) {
/* 重複した値があったよ */
return -1;
}
}
/* 3*3 のチェック */
sx = ix - (ix % GOBAN_T);
sy = iy - (iy % GOBAN_T);
for(cx = 0; cx < GOBAN_T; ++cx) {
for(cy = 0; cy < GOBAN_T; ++cy) {
if(konkai.number[sx + cx][sy + cy] == number) {
/* 重複した値があったよ */
return -1;
}
}
}
/* 一応値は入ったらしい(*^_^*)v */
konkai.number[ix][iy] = number;
/* 次の座標に何の値が入るか調べる */
int check_number;
for(check_number = 1; check_number <= GOBAN_N;) {
/* 再帰させる */
if(getans(ix, iy, check_number, konkai) == 0) {
/* 正解が見つかったとき */
return 0;
}
check_number++;
}
return -1;
}
与えられた碁盤、座標、入れるべき数値に対して、
まず、そのマスが開いているかをチェックします。開いていなければ、問題にその値が入っているということですので、無視して次のコマをチェックします。
次に横、縦、３＊３のマスで入れようとしている数が重複していないかをチェックして、重複していれば諦めます。
で、入れることが可能であれば、次に１〜９の数値が入るのかという事を再帰で調べる・・・と。
１〜９の数値の中で例えば２、４以外は重複しているとなると、まず１、３、５、６、７、８、９の数については縦横、３＊３のマスのチェックで諦めます。２、４についてはその値をいれた上で次のマス、次のマス・・・と調べることになります。
パズルの回答を求めるのにバックトラック法を使うあたり、あまり賢いとは思えないのですが、、、。（敗北感が・・・）
コメント