C言語 ナンプレを自動でとくプログラム
このページは以下の読者を対象にしています
プログラムの説明
全体の流れ：
- ファイルから問題を読み込む
- 問題を表示する
- 問題を解く
- 結果を表示する
データ構造： 要素数81のint型の配列に数字を入れていく。空白は0を入れる。
typedef int NumPlace[81];でNumPlace型を作った.
要素数とマスの関係は下記の通り
0 1 2 3 4 5 6 7 8
9 10 11 …
各関数詳細
問題読み込み関数：引数 出力先のNumPlace型変数 標準入力でファイル名を受け取る。 ファイルがなかった場合は強制終了ではなく、再度受け付け。 引数で指定されたNumPlace型の変数に書き込む。 空白には0,数字はint型。 ナンプレ表示関数： 引数で受け取ったNumPlace型を9*9のマスで表現。 見やすくなるよう、3*3マス毎に仕切りを表示。 数字探索関数：引数 min_num :探索する最小の数, index :対象のマス目(配列要素数), 探索するNumPlace 引数indexから行、列、3*3のブロックの左上のマス、対角線上にいるかを判断。 要素数11のint型の配列out_num[11]を用意して0に。out_num[10] は番兵 同じ行、列、3*3のブロック、対角線にいれば対角線上の数字を使い、順にout_num[数字] = 1としていく。 min_num以上でout_num[要素] = 0となる要素が求める数字。10なら番兵なので0を返す. 次の空白探索関数：引数 index:探索開始のマス目, 探索するNumPlace 返り値：次の空白のマス目。無ければ81 NumPlaceの要素をIndexから順に１つずつ上げ、値が0となった要素を返す。 空白がなければ81を返す 解答関数：引数 index:現在マス目, 答えを入れる出力先NumPlace。返り値：代入した値 再帰を用いて解く。 マスindexに入る数字を数字探索関数により取得。0ならreturn。値があれば次の空白探索 関数を用いて、次の探索先を決定。無い(=81が返ってきた)ならreturn。 あれば再帰呼び出しする。再帰で呼び出した関数の返り値が0なら、前回入れた値より大 きな数字でマスindexに入る数字を探索。これを繰り返す。
入力ファイル
- ;で始まる行はコメント.ファイル中に複数あって良い.
- 1行9文字で9行のデータ.データの1行につき,ナンバープレースの1行を上から順番に書く.
- 値がないところはスペースであける.
例
5 6 ;
1 2 ;
236 1 9 ;
214 8 ;
9 2;
398 6 ;
;
127 8 3 ;61
4 8 ;
1 4 ;
これを好きなファイル名でプログラム場所に保存しておく。後でscanfでファイル名を入力する。
使用プログラム
gcc で動作確認済み
/*対角線ナンバープレースを解くプログラムを作成 各行，各列で1~9の数字は重複しない 太線で区切られた9マスでも，1~9の数字は重複し ない 2本の対角線上も1~9の数字が入る 空いているマスを全部埋める 問題ファイルを各自作成し，それぞれプログラム で読み込ませて解を表示 複数解がある場合は最初に見つかった１つを表 示すれば良い */ #include <stdio.h> #include <stdlib.h> #include <string.h> #define STR_SIZE 256 /* データ構造： 要素数81のint型の配列に数字を入れていく。空白は0を入れる. typedef int NumPlace[81];でNumPlace型を作った. 要素数とマスの関係は下図参照 0 1 2 3 4 5 6 7 8 9 10 11 … */ typedef int NumPlace[81]; // 問題読み込み関数：引数 出力先のNumPlace型変数 void GetProblem(NumPlace problem); void ShowNumPlace(NumPlace numplace); //ナンプレ表示関数 //数字探索関数：引数 min_num :探索する最小の数, index :対象のマス目(配列要素数), 探索するNumPlace int GetPossibleNum(int min_num, int index, NumPlace numplace); /* 次の空白探索関数：引数 index:探索開始のマス目, 探索するNumPlace 返り値：次の空白のマス目。無ければ81 */ int NextIndex(int index, NumPlace numplace); /* 解答発見関数：引数 index:現在マス目, 答えを入れる出力先NumPlace。 返り値：代入した値 */ int SetPossibleNum(int index, NumPlace numplace); //問題を解く void SolveNumPlace(NumPlace problem, NumPlace ans); int main(int argc, char const *argv[]) { NumPlace problem; GetProblem(problem); //ファイルから問題を読み込む ShowNumPlace(problem); //問題を表示する NumPlace ans; SolveNumPlace(problem, ans); //問題を解く ShowNumPlace(ans); //結果を表示する return 0; } /* 問題読み込み関数：引数 出力先のNumPlace型変数 標準入力でファイル名を受け取る。 ファイルがなかった場合は強制終了ではなく、再度受け付け。 引数で指定されたNumPlace型の変数に書き込む。 空白には0,数字はint型 */ void GetProblem(NumPlace problem) //問題を配列に収納 { for (int i = 0; i < 81; i++) problem[i] = 0; //0クリア FILE *fp = NULL; while (fp == NULL) { printf("File name of problem:"); char filename[STR_SIZE] = {}; scanf("%s", filename); if ((fp = fopen(filename, "r")) == NULL) fprintf(stderr, "error: there is no file named %s\r\n", filename); } char str[STR_SIZE]; int posi = 0; while (fgets(str, sizeof(str) / sizeof(str[0]), fp) != NULL) { for (size_t i = 0; i < strlen(str); i++) { if (str[i] == ';' || str[i] == '\n') break; else if (str[i] == ' ') ++posi; else problem[posi++] = str[i] - '0'; } } fclose(fp); } /* ナンプレ表示関数： 引数で受け取ったNumPlace型を9*9のマスで表現。 見やすくなるよう、3*3マス毎に仕切りを表示。 */ void ShowNumPlace(NumPlace numplace) { for (int i = 0; i < 9; i++) { if (i % 3 == 0) { for (int m = 0; m < 3; m++) { printf("+"); for (int k = 0; k < 3 * 3; k++) printf("-"); } printf("+\n"); } for (int j = 0; j < 9; j++) { int target = numplace[i * 9 + j]; if (j % 3 == 0) printf("|"); if (target == 0) printf(" "); else printf("% d ", target); } printf("|\n"); } for (int m = 0; m < 3; m++) { printf("+"); for (int k = 0; k < 3 * 3; k++) printf("-"); } printf("+\n"); } /* 数字探索関数：引数 min_num :探索する最小の数, index :対象のマス目(配列要素数), 探索するNumPlace 引数indexから行、列、3*3のブロックの左上のマス、対角線上にいるかを判断。 要素数11のint型の配列out_num[11]を用意して0に。out_num[10] は番兵 同じ行、列、3*3のブロック、対角線にいれば対角線上の数字を使い、 順にout_num[数字] = 1としていく。 min_num以上でout_num[要素] = 0となる要素が求める数字。 10なら番兵なので0を返す. */ int GetPossibleNum(int min_num, int index, NumPlace numplace) { int out_num[11] = {}; //1ならその数字は使えない. out_num[10] は番兵 int row = index / 9; int columon = index % 9; int box = (columon / 3) * 3 + (row / 3) * 3 * 9; //boxの右上のindex // 横にみてすでにある数字を消す(配列の該当数字の要素を1に) for (int i = 0; i < 9; i++) out_num[numplace[row * 9 + i]] = 1; //縦に見る for (int i = 0; i < 9; i++) out_num[numplace[columon + i * 9]] = 1; //box内を見る for (int i = 0; i < 3; i++) { for (int k = 0; k < 3; k++) out_num[numplace[box + k + i * 9]] = 1; } // 右下への斜めを見る if (row == columon) { for (int i = 0; i < 9; i++) out_num[numplace[i + i * 9]] = 1; } //左下への斜めを見る if ((row + columon) == 8) { for (int i = 0; i < 9; i++) out_num[numplace[8 * (i + 1)]] = 1; } //min_num以上の値で可能性のあるものを返す int ans = min_num; while (out_num[ans] == 1) ++ans; if (ans > 9) ans = 0; return ans; } /* 次の空白探索関数：引数 index:探索開始のマス目, 探索するNumPlace 返り値：次の空白のマス目。無ければ81 NumPlaceの要素をIndexから順に１つずつ上げ、値が0となった要素を返す。 空白がなければ81を返す */ int NextIndex(int index, NumPlace numplace) { int i = index; for (; i < 81; i++) { if (numplace[i] == 0) break; } return i; } /* 解答発見関数：引数 index:現在マス目, 答えを入れる出力先NumPlace。 返り値：代入した値 再帰を用いて解く。 マスindexに入る数字を数字探索関数により取得。0ならreturn。 値があれば次の空白探索関数を用いて、次の探索先を決定。 無い(=81が返ってきた)ならreturn。あれば再帰呼び出しする。 再帰で呼び出した関数の返り値が0なら, 前回入れた値より大きな数字でマスindexに入る数字を探索.これを繰り返す。 */ int SetPossibleNum(int index, NumPlace numplace) { int num = 0; while (1) { num = GetPossibleNum(num + 1, index, numplace); numplace[index] = num; if (num == 0) break; int next_index = NextIndex(index + 1, numplace); if (next_index >= 81) break; if (SetPossibleNum(next_index, numplace) != 0) break; } return num; } void SolveNumPlace(NumPlace problem, NumPlace ans) { for (int i = 0; i < 81; i++) ans[i] = problem[i]; printf("\n\nans\n"); SetPossibleNum(NextIndex(0, problem), ans); if (ans[0] == 0) printf("could not solve\n"); }
出力結果例
PS C:ディレクトリ場所> .\a.exe File name of problem:q2.txt +---------+---------+---------+ | | 5 | 6 | | 1 | | 2 | | 2 3 6 | 1 | 9 | +---------+---------+---------+ | 2 | 1 4 | 8 | | | | 9 2 | | 3 | 9 8 | 6 | +---------+---------+---------+ | 1 2 7 | 8 | 3 | | 4 | | 8 | | | 1 | 4 | +---------+---------+---------+ ans +---------+---------+---------+ | 9 7 8 | 2 5 4 | 3 6 1 | | 5 4 1 | 3 6 9 | 7 2 8 | | 2 3 6 | 8 7 1 | 4 9 5 | +---------+---------+---------+ | 6 9 2 | 1 4 5 | 8 7 3 | | 4 8 5 | 7 3 6 | 9 1 2 | | 7 1 3 | 9 8 2 | 6 5 4 | +---------+---------+---------+ | 1 2 7 | 4 9 8 | 5 3 6 | | 3 6 4 | 5 2 7 | 1 8 9 | | 8 5 9 | 6 1 3 | 2 4 7 | +---------+---------+---------+
