其实和迷宫问题类似思想都是填写每个位置如果重复换数字，填不下去了就回溯，但是这个题目有两个难点：
1.如果判断横方向竖方向还有，9宫格里面是否重复，判断比较难。
2.迷宫问题只有方向4个状态量，可是解数独状态量有填写9个数字加上4个方向，两组状态量，递归体怎么填写是很困难的。
①先说判断
②再说两组状态量
一开始我尝试代码，这种形式
for（1~9尝试） for（四个方向遍历） dfs（）
但是这样做会有一个很大的问题，你不知道递归终止的条件，什么意思？
下面这段代码演示四个方向递归的搜索过程，假如说中间有点不能访问，我们又要从该点向四个方向dfs，那么访问完所有点，最后一个点是哪个，这是不确定的。
#include<iostream> using namespace std; char broad[9][9]; int dx[4] = { 0,1,-1,0 }; int dy[4] = { 1,0,0,-1 }; void dfs(int a1, int b1) { system("cls"); for (int i = 0; i < 9; i++) { cout << endl; for (int j = 0; j < 9; j++) { cout << broad[i][j] << " "; } } for (int i = 0; i < 4; i++) { broad[a1][b1] = '#'; int x = a1 + dx[i]; int y = b1 + dy[i]; if (x >= 0 && x <= 8 && y >= 0 && y <= 8&&broad[x][y]=='*') { cout << endl; cout << x << " " << y << endl; dfs(x, y); } } } int main() { memset(broad, '*', sizeof(broad)); dfs(0, 0); int x = 0, y = 0; }
解决办法就是
> dfs(x + (y + 1) / 9, (y + 1) % 9);
改段代码意思就是，当y走到8了，x换行，y又从0开始，保证顺序按每行从左往右，结束换行。这样dfs结束的点就是x=9的时候。
最终代码：
#include<iostream> #include<string.h> using namespace std; char a[9][9]; bool r[9][10]; bool c[9][10]; bool b[9][10]; bool judge(int x, int y) { int num = a[x][y]-'0'; int block = x / 3 * 3 + y / 3; if (r[x][num] == 1 || c[y][num] == 1 || b[block][num] == 1) { return false; } return true; } void dfs(int x, int y) { if (x == 9) { for (int i = 0; i < 9; i++) { cout << endl; for (int j = 0; j < 9; j++) { cout << a[i][j] << " "; } } exit(0); } if (a[x][y] == '.') { for (char ch = '1'; ch <= '9'; ++ch) { a[x][y] = ch; if (judge(x, y)) { int num = ch - '0'; int block = (x / 3) * 3 + y / 3; r[x][num] = 1; c[y][num] = 1; b[block][num] = 1; dfs(x + (y + 1) / 9, (y + 1) % 9); r[x][num] = 0; c[y][num] = 0; b[block][num] = 0; } a[x][y] = '.'; } } else { dfs(x + (y + 1) / 9, (y + 1) % 9); } } int main() { //4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4...... memset(r, 0, sizeof(r)); memset(c, 0, sizeof(c)); memset(b, 0, sizeof(b)); for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { cin >> a[i][j]; if (a[i][j] != '.') { //错误原因。。。。之前一直输入没判断 int num = a[i][j] - '0'; r[i][num] = 1; c[j][num] = 1; int block = i / 3 * 3 + j / 3; b[block][num] = 1; } } } dfs(0, 0); }
