![]()
代码实现
#include <bits/stdc++.h> using namespace std; const int N = 10; int a[N][N]; bool col[N][N], row[N][N], st[3][3][N]; bool dfs(int x, int y) { // 出口 if(y == 10) { x ++; y = 1; } if(x == 10) return true; if(a[x][y]) return dfs(x, y+1); // 已经填值了 for(int i = 1; i <= 9; i++) { if(row[x][i] || col[y][i] || st[(x-1)/3][(y-1)/3][i]) continue; // 剪枝 // 递归搜索 row[x][i] = col[y][i] = st[(x-1)/3][(y-1)/3][i] = 1; a[x][y] = i; if(dfs(x, y+1)) return true; // 已经找到结果 // 回溯 row[x][i] = col[y][i] = st[(x-1)/3][(y-1)/3][i] = 0; a[x][y] = 0; } return false; // 前面有填错了 } int main() { for(int i = 1; i <= 9; i++) { for (int j = 1; j <= 9; j++) { int x; cin >> x; a[i][j] = x; if(x) row[i][x] = col[j][x] = st[(i-1)/3][(j-1)/3][x] = 1; // 标记 } } dfs(1,1); for(int i = 1; i <= 9; i++) { for (int j = 1; j <= 9; j++) cout << a[i][j] << " "; cout << endl; } return 0; }
