【暴力搜索】解数独，你会吗?!!
【暴力搜索】解数独，你会吗?!!
37. 解数独
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例 1：
输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
提示：
board.length == 9board[i].length == 9board[i][j]是一位数字或者'.'- 题目数据 保证 输入数独仅有一个解
解题思路：暴力搜索 + 布尔值数组判断
首先这道题如果是暴力搜索加上判断合法性的时候使用暴力检查的话，那么也是可以的话，所谓的暴力检查就是选了这个数字后，去遍历它所在的行、列、九宫格是否存在相同元素，这样子的话其实效率不高，所以这里我们考虑使用我们在 36. 有效的数独 这道题用到的布尔值数组判断的技巧，相当于哈希表的功能，起到了空间换时间的效果！
如下图所示，这是填数独的决策树：
可以看到我们仍然需要对每个位置进行暴力搜索，也就是两层 for 循环，当判断当前数字没问题之后，则递归到下一层去进行暴力搜索，此时因为我们在上一层会先将该数字填入表中，所以下一层进来的时候就是遍历到上一层数字的后面！如果此时 发现枚举了 1~9 数字之后都无法满足数独要求，此时说明上面某一层的策略是错的，则让当前向上返回一个 false（注意不是返回空，而是需要一个布尔值！），这样子当上一层发现接收到的是 false 的时候，此时就需要进行回溯处理，恢复现场，执行下一个数字的递归判断！
这也就说明了 递归函数头在设计的时候，必须是 bool 值类型返回值，它和 void 的区别就在于 void 类型返回的话上一层不知道下一层是否成功，则会往下执行，进行恢复现场的操作，但是我们的需求是如果下一层成功的返回了，那么我们就不需要进行恢复现场的操作，因为这道题最终就是要让整个表填满，这就是为什么需要 bool 值作为返回值的原因，而不能是 void 类型！
可能直接想象有点抽象，下面给出回溯三部曲的操作，如下所示：
// 对当前符合要求的数字进行处理
row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;
board[i][j] = '0' + num;
// 递归处理
if(dfs(board) == true)
return true;
// 恢复现场（只有上面为false才需要恢复）
board[i][j] = '.';
row[i][num] = col[j][num] = grid[i/3][j/3][num] = false; 可以看出，如果下一层返回的是 true 的话，说明该数字后面的数字都填完并且是符合要求的，直接返回即可！而如果返回的 false 的话，则说明下面某一层出现了数字不匹配的情况，则说明当前或者上面某一层错误，则要进行下面的恢复现场操作，然后进行枚举其它的数字可能！
而如果是下面返回值是空类型的情况，就不行了，如下所示：
// 对当前符合要求的数字进行处理
row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;
board[i][j] = '0' + num;
// 递归处理
dfs(board);
// 恢复现场（无论失败成功，最后都会恢复现场，导致表又恢复原状了）
board[i][j] = '.';
row[i][num] = col[j][num] = grid[i/3][j/3][num] = false; 说完这个问题之后，我们就来思考一下，什么时候才会返回成功和失败呢❓❓❓
答案很明显，就是当前 如果 1~9 数字填入该位置都是不符合的话，说明上面某一层填的数字策略是错误的，则此时返回 false 即可！而如果说 两层 for 循环结束了，说明最后一个数字也填写完毕了，此时也没发生不匹配的情况，则可以返回 true 了！
最后需要考虑的问题就是引入了布尔值数组来提高判断是否符合数独要求的问题，这其实和 36. 有效的数独 这道题是一样的，只不过我们在进行填数独之前，得先了解当前表中的已有数字的情况，所以就需要 先做个初始化，遍历一下原表，将原表中已有的数字映射到对应的布尔值数组中，将其设为 true！
然后无非就是遍历过程中判断三个数组对应位置是否出现过元素，只需要判断其是否为 true 即可，true 就表示出现过，则直接 continue 就行，而至于如何判断三个数组对应位置是否出现过元素，我们已经在 36. 有效的数独 介绍过了，这里就不再赘述，细节可以参考那道题的笔记！
class Solution {
private:
bool row[9][10];
bool col[9][10];
bool grid[3][3][10];
public:
void solveSudoku(vector<vector<char>>& board) {
init(board); // 进行原表数字映射到上述布尔值数组的初始化操作
dfs(board); // 进行递归处理
}
// 初始化布尔值数组
void init(vector<vector<char>>& board)
{
for(int i = 0; i < 9; ++i)
{
for(int j = 0; j < 9; ++j)
{
if(board[i][j] != '.')
{
int tmp = board[i][j] - '0';
row[i][tmp] = col[j][tmp] = grid[i/3][j/3][tmp] = true;
}
}
}
}
bool dfs(vector<vector<char>>& board)
{
for(int i = 0; i < 9; ++i)
{
for(int j = 0; j < 9; ++j)
{
if(board[i][j] != '.') // 只有空白处我们才进行处理
continue;
for(int num = 1; num <= 9; ++num)
{
// 如果该数字已经出现过，则直接continue
if(row[i][num] || col[j][num] || grid[i/3][j/3][num])
continue;
// 对当前符合要求的数字进行处理
row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;
board[i][j] = '0' + num;
// （重点理解）
// 如果下一层返回的是true的话，说明该数字后面的数字都填完并且是符合要求的，直接返回即可
// 而如果返回的false的话，则说明下面某一层出现了数字不匹配的情况，则说明当前或者上面某一层错误，则要恢复现场
if(dfs(board) == true)
return true;
// 恢复现场（只有上面为false才需要恢复）
board[i][j] = '.';
row[i][num] = col[j][num] = grid[i/3][j/3][num] = false;
}
return false; // （重点理解）
}
}
return true; // （重点理解）
}
};腾讯云开发者
