データの構造は９＊９の碁盤を用意して、そのなかに１〜９の数が入れば良いので、
int number[9][9];とか、もっとケチれば
char number[9][9];とかすれば良いのですが、再帰を使って処理したいので碁盤その物を値渡ししたい・・・という事になります。
そこで、碁盤その物を構造体として定義してしまいます。
typedef struct GOBAN {こうすると、碁盤その物が一つの変数として扱えるので、関数の呼び出しが楽に行えるかな・・と。
unsigned int number[9][9];
}_GOBAN;
これと前回の部分を組み合わせると、数独の解答をバックトラックで求める基本部分が出来上がりとなります。
その他、問題をファイルから読み込む部分、碁盤を表示する部分等を付け足して、一応完成です。
Cygwin環境のGCCで作りましたけど、この程度ならどの環境に持っていってもそれなりに動くと思います。（Win32のコマンドアプリとしても動作可能だと思う。。Warning五月蝿そうだけど）
全体のソースは以下のとおり。
/*
数独をバックトラック法で解く
*/
#include <stdio.h>
/* 定数 */
#define GOBAN_X 9
#define GOBAN_Y 9
#define GOBAN_T 3
#define GOBAN_N 9
#define CR 0x0d
#define LF 0x0a
/* 構造体 */
typedef struct GOBAN {
unsigned int number[GOBAN_X][GOBAN_Y];
}_GOBAN;
/* グローバル変数 */
struct GOBAN goban;
int calc_count;
/* 関数定義 */
int getans(int, int, int, struct GOBAN);
void init(void);
void display(void);
int readfile(char *);
int kaitou(void);
/* メイン */
int main(int argc, char *argv[]) {
int ret = 0;
int i;
for(i = 1; i < argc; i++) {
calc_count = 0;
init();
readfile(argv[i]);
printf("[quiz]------------------------------------\n");
display();
printf("\n");
ret = kaitou();
if(ret == 0) {
/* 値が見つかった時 */
printf("[answ]------------------------------------\n");
display();
printf("computing ... %d count(s)\n\n", calc_count);
} else {
/* 値が見つかんねー時 */
printf("not found...\n\n");
}
}
return 0;
}
/* 問題を解く */
int kaitou() {
int check_number;
int ret = -1;
for(check_number = 1; check_number <= GOBAN_N; ) {
if(getans(0, 0, check_number, goban) == 0) {
/* その値が正解なのでループ中止 */
ret = 0;
break;
}
check_number++;
}
return ret;
}
/* 碁盤の初期化 */
void init() {
int x, y;
for(y = 0; y < GOBAN_Y; ++y) {
for(x = 0; x < GOBAN_X; ++x) {
/* ひたすらゼロクリア */
goban.number[x][y] = 0;
};
};
}
/* 碁盤の表示 */
void display() {
int x, y;
for(y = 0; y < GOBAN_Y; ++y) {
for(x = 0; x < GOBAN_X; ++x) {
printf("%1d ", goban.number[x][y]);
};
printf("\n");
};
}
/* 碁盤の読み込み
戻り値 成功：0、失敗：-1
*/
int readfile(char *filename) {
FILE *fp;
char buf;
int flg_stop = 0;
int flg_comment = 0;
int x = 0, y = 0;
if((fp = fopen(filename, "r")) == NULL) {
printf("file %s open failed.\n", filename);
return -1;
}
while(fread(&buf, (size_t)1, (size_t)1, fp) != 0) {
if(buf >= '0' && buf <= '9' && flg_stop == 0 && flg_comment == 0) {
goban.number[x][y] = buf - '0';
x++;
if(x >= GOBAN_X) {
x = 0;
y++;
if(y >= GOBAN_Y) {
flg_stop = 1;
}
}
}
if(buf == '#' || buf == '/') {
/* #か/があったらその後はコメントとみなす */
flg_comment = 1;
}
if((buf == CR || buf == LF || buf == '\\') && flg_comment != 0) {
/* 改行か'\'がきたらコメント行じゃないよ */
flg_comment = 0;
}
}
fclose(fp);
return 0;
}
/* バックトラック（再帰部分）
引数 座標ix,iy
戻り値 0:成功、-1:失敗
*/
int getans(int ix, int iy, int number, struct GOBAN konkai) {
int cx, cy;
int sx, sy;
int x, y;
// printf("thinking...\n");
// sleep(1);
calc_count++;
/* 次の空き座標をチェック */
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;
}
}
}
/* 一応値は入ったらしい */
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;
}
コメント