class Solution {
private:
bool line[9][9];
bool column[9][9];
bool block[3][3][9];
bool valid;
vector<pair<int, int>> spaces;
public:
void dfs(vector<vector>& board, int pos) {
if (pos == spaces.size()) {
valid = true;
return;
}
auto [i, j] = spaces[pos];
for (int digit = 0; digit < 9 && !valid; ++digit) {
if (!line[i][digit] && !column[j][digit] && !block[i / 3][j / 3][digit]) {
line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
board[i][j] = digit + '0' + 1;
dfs(board, pos + 1);
line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = false;
}
}
}
void solveSudoku(vector<vector<char>>& board) {
memset(line, false, sizeof(line));
memset(column, false, sizeof(column));
memset(block, false, sizeof(block));
valid = false;
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (board[i][j] == '.') {
spaces.emplace_back(i, j);
}
else {
int digit = board[i][j] - '0' - 1;
line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
}
}
}
dfs(board, 0);
}
};
这是力扣上的原题中的官方解答递归方法，来个负责任的大佬
问： spaces.emplace_back(i, j);他这是如何进行填充的呢，随机吗，如果是随机，，他这个数如果不合适怎么办，我全程都看不到筛选的函数啊。
问：valid = false;这个vaild起什么作用呢，我觉得有他没他不重要，是这样吗？
问：auto [i, j] = spaces[pos];这个代码涉及到的语法是什么呢，为什么不能写成 auto spacesi,j;呢
问： void dfs(vector<vector>& board, int pos)声明这个函数到底它的作用是什么呢？ line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = false;到最后不都应该会被判定成 line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;吗？这看得我头晕。。。
来个负责任的大佬，希望能讲详细一点
已添加详细的注释
class Solution {
private:
// 分别标记每个单元格行，列，所属块内可以填写的数字
bool line[9][9]; // 例：第一维表示共有九行，第二维标记该行可以填充的数字
bool column[9][9];
bool block[3][3][9];
bool valid; // 标记数独是否解出
vector<pair<int, int>> spaces; // 空缺位置的行列坐标
public:
void dfs(vector<vector<char>>& board, int pos) {
// 如果空缺位置按照标记填充结束，结束搜索
if (pos == spaces.size()) {
valid = true;
return;
}
// 取出第pos个空缺位置的坐标
auto [i, j] = spaces[pos];
// 如果数独还未求解出来，往空缺位置按0-9顺序填数
for (int digit = 0; digit < 9 && !valid; ++digit) {
// 如果这个数可以被填进去
if (!line[i][digit] && !column[j][digit] && !block[i / 3][j / 3][digit]) {
// 将数标记
line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
// 将数填写到答案中
board[i][j] = digit + '0' + 1;
// 给下一个空缺处填写数字
dfs(board, pos + 1);
// 这个数可以填进去，但之后的数不能填进去，所以这个数不能填在这儿，则重新换个数填空
line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = false;
}
// 如果不可以被填写进去，就换个数字填
}
}
void solveSudoku(vector<vector<char>>& board) {
// 将各标记置为默认值false
memset(line, false, sizeof(line));
memset(column, false, sizeof(column));
memset(block, false, sizeof(block));
valid = false;
// 将各标记按照题中所给数据进行初始化
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (board[i][j] == '.') {
spaces.emplace_back(i, j);
}
else {
int digit = board[i][j] - '0' - 1; // 数独中的数字
// 为各标记数组设置标记
line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
}
}
}
// dfs来搜索存在的可行解，从第“0”个空缺位置开始
dfs(board, 0);
}
};
问： spaces.emplace_back(i, j);他这是如何进行填充的呢，随机吗，如果是随机，，他这个数如果不合适怎么办，我全程都看不到筛选的函数啊。
space是动态数组，填充的是按行列顺序的空缺处的坐标，不是随机填充的。筛选的那步是dfs里面的判断。
问：valid = false;这个vaild起什么作用呢，我觉得有他没他不重要，是这样吗？
皮一下，我删了之后代码提交不通过，所以很重要。
问：auto [i, j] = spaces[pos];这个代码涉及到的语法是什么呢，为什么不能写成 auto spacesi,j;呢
C++的智能类型推断，后面的类型为pair<int,int>，所以等价于pair<int,int> [i, j]。因为这样写spacei和j都是pair<int,int>类型。
问： void dfs(vector& board, int pos)声明这个函数到底它的作用是什么呢？ line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = false;到最后不都应该会被判定成 line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;吗？这看得我头晕。。。
来个负责任的大佬，希望能讲详细一点
将第i行的digit标记为已填入，同理列和块。
问： spaces.emplace_back(i, j);他这是如何进行填充的呢？
spaces是一个vector数组，数组中每一项为pair<int, int>，保存了数独方块的坐标，比如[0,0],[0,1]。
函数初始化时判断没有填充数字的位置，然后保存到这个spaces数组中。
问：valid = false;这个vaild起什么作用呢，我觉得有他没他不重要，是这样吗？
valid表示数独是否有正确的解。后面在dfs循环中用到了这个变量，当数独有解时停止递归调用dfs函数。
问：auto [i, j] = spaces[pos];这个代码涉及到的语法是什么呢，为什么不能写成 auto spacesi,j;呢
c++新特性auto，会自动推导出变量类型；
这里相当于： pair<int, int> x = spaces[pos]; i = x.first; j = x.second
问： void dfs(vector& board, int pos)声明这个函数到底它的作用是什么呢？ line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = false;到最后不都应该会被判定成 line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;吗？
这个函数里面对数独求解，深度优先算法。
算法的解答：对数独中空白的位置，按1-9设置一个数字，判断是否能满足数独条件（就是这段判断!line[i][digit] && !column[j][digit] && !block[i / 3][j / 3][digit]）
如果可以设置，则暂时将该位置设置为具体的数字，并标记设置为true，然后继续递归处理下一个空格。
如果递归处理不符合时，则说明该位置设置该值不行，所以再标记为false。
继续尝试下一个数字
涉及到递归的，讲解上还是有点不清楚，自己可以简单添加打印日志看递归前后的输出也可以清楚一点。
你确定你这个能编译通过？？？