代码注释如下
#include <iostream>
using namespace std;
const int N = 10;
bool col[N][N], rol[N][N], cell[3][3][N];
char g[N][N];
bool dfs(int x, int y) { //用bool这样在找到一个方案就可以迅速退出
if(y == 9) x++, y = 0; //若y超出边界,则第二行开始y = 0,x++
if(x == 9) {
for(int i = 0; i < 9; i++)
cout << g[i] << endl;
return true;//这里返回true让下面for里面中间的dfs直接结束,不在回溯,少枚举很多情况
//并且是输出唯一解
}
if(g[x][y] != '.') return dfs(x, y + 1);
//g[x][y] == '.'
for(int i = 0; i < 9; i++) {
if(!col[y][i] && !rol[x][i] && !cell[x / 3][y / 3][i]) {
g[x][y] = i + '1';
col[y][i] = rol[x][i] = cell[x / 3][y / 3][i] = true;
if(dfs(x, y + 1)) return true;//剪枝,dfs返回值是true上面输出了答案,不用再回溯,并且
//这一枝递归直接结束。
//恢复操作
g[x][y] = '.';
col[y][i] = rol[x][i] = cell[x / 3][y / 3][i] = false;
}
}
return false;//如果某个方案失败,需要返回false让上面回溯
//不加这个也不会输出结果,因为如果这一枝递归没成功,返回false上面才能回溯
}
int main() {
for(int i = 0; i < 9; i++) {
cin >> g[i];
for(int j = 0; j < 9; j++) {
if(g[i][j] != '.') {
int x = g[i][j] - '1'; //1-9映射到0-8(方便cell的下取整操作)
rol[i][x] = true;
col[j][x] = true;
cell[i / 3][j / 3][x] = true;
}
}
}
dfs(0, 0);
return 0;
}
补充
//这样写也是对的,只不过没有剪枝,时间复杂度高些
bool dfs(int x, int y)
{
if (y == 9) x ++, y = 0;
if (x == 9)
{
for (int i = 0; i < 9; i ++ ) cout << g[i] << endl;
return true;
}
if (g[x][y] != '.') return dfs(x, y + 1);
for (int i = 0; i < 9; i ++ )
if (!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i])
{
g[x][y] = i + '1';
row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;
dfs(x, y + 1);//不同点
row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;
g[x][y] = '.';
}
//没有返回值
}