Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.
A sudoku puzzle...< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PGltZyBzcmM9"https://www.cppentry.com/upload_files/article/49/1_ex8r8__.png" alt="\">
...and its solution numbers marked in red.
问题描述：给定一个数独棋盘，得到数独的解。
规范的数独题目应该只有一个解，因此，将这道题目当作只有一个解来看待。
这样一步一步来走，前面已经放置的数字又影响后面放置的数字，是不是有点类似于N皇后问题呢？其实，这道题完全可以按照N皇后问题的方法来解。
下面给出带注释的代码，因此，就不做过多解释了。
#include#include #define MAXN 9 //数独棋盘边长 #define TRI 3 //宫的边长 char sudoku[MAXN][MAXN]; //保存数独棋盘 int flag[MAXN][MAXN]; //标志某个格的数字是否是初始化就存在的，这样的格不用放置数字 int sol_cnt; //解的个数 //将文件中的数独读入到sudoku中 //文件中是这样保存的8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4.. //其中"."代表空的格 void set_sudoku() { FILE *fp; if((fp = fopen("sudoku", "r")) == NULL) { printf("open file error!\n"); exit(-1); } char ch = 0; int i = 0, j = 0; for(i = 0; i < MAXN; ++i) { for(j = 0; j < MAXN; ++j) { if((ch = fgetc(fp)) != EOF) { if(ch == '.') { sudoku[i][j] = '.'; flag[i][j] = 0; } else { sudoku[i][j] = ch - '0'; flag[i][j] = 1; } } } } if(fclose(fp) == EOF) { printf("close file error!\n"); exit(-1); } } //打印数独棋盘 void print_sudoku() { int i = 0, j = 0; for(i = 0; i < MAXN; ++i) { for(j = 0; j < MAXN; ++j) { if(sudoku[i][j] == '.') printf("%c ", sudoku[i][j]); else printf("%d ", sudoku[i][j]); } printf("\n"); } printf("\n"); } //用于在宫内和宫之间进行遍历 //宫内是从上到下，从左到右遍历，宫内最后一个元素的下一个元素就是下一个宫的第一个元素 //宫之间也是从上到下，从左到右遍历 void get_next(int ln, int col, int *next_ln, int *next_col) { if(!((ln + 1) % TRI) && !((col + 1) % TRI)) { if(ln == 8 && col == 8) { *next_ln = ln + 1; *next_col = col + 1; } else if(ln != 8 && col == 8) { *next_ln = ln + 1; *next_col = 0; } else { *next_ln = ln - 2; *next_col = col + 1; } } else if(((ln + 1) % TRI) && !((col + 1) % TRI)) { *next_ln = ln + 1; *next_col = col - 2; } else { *next_ln = ln; *next_col = col + 1; } } //判断digit是否在(ln, col)所在的宫内 //只考虑初始有数字和之前放置的数字是否与digit相等 int in_square(int ln, int col, int digit) { int s_ln = (ln / TRI) * TRI, s_col = (col / TRI) * TRI; int next_ln = 0, next_col = 0; int cnt = 9; while(cnt--) { if(sudoku[s_ln][s_col] == digit && (s_ln < ln || s_col < col || flag[s_ln][s_col] == 1)) return 1; get_next(s_ln, s_col, &next_ln, &next_col); s_ln = next_ln; s_col = next_col; } return 0; } //判断digit是否在(ln, col)所在的行和列 //只考虑初始有数字和之前放置的数字是否与digit相等 int is_valid(int ln, int col, char digit) { int i = 0; for(i = 0; i < MAXN; ++i) { if(sudoku[i][col] == digit && (i < ln || flag[i][col] == 1) || sudoku[ln][i] == digit && (i < col || flag[ln][i] == 1)) { return 0; } } return 1; } //放置一个数字，以(0, 0)为起始，通过get_next()获取下一个放置的位置 //如果当前要放置的位置初始时已经有数字，就直接放置下一个位置，就用1-9来依次尝试 void place_digit(int ln, int col) { if(ln == MAXN && col == MAXN) { ++sol_cnt; print_sudoku(); return; } int next_ln = 0, next_col = 0; get_next(ln, col, &next_ln, &next_col); if(flag[ln][col] == 1) { place_digit(next_ln, next_col); return; } char digit = 0; for(digit = 1; digit < 10; ++digit) { sudoku[ln][col] = '.'; if(!in_square(ln, col, digit) && is_valid(ln, col, digit)) { sudoku[ln][col] = digit; place_digit(next_ln, next_col); } } } int main(int argc, char *argv[]) { set_sudoku(); print_sudoku(); place_digit(0, 0); printf("%d solutions!\n", sol_cnt); return 0; }
在网上找了个所谓的最难数独，对它进行求解：
好了，下面就对文章开头的题目进行求解，其实思路完全一样，只不过用的是C++，其中多了对容器的操作。
To Be Continued!