难度困难1559
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
- 数字
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]是一位数字或者'.'- 题目数据 保证 输入数独仅有一个解
解题思路：回溯
这道题比起我们之前写过的 51. N 皇后 还要再难一点，因为 51. N 皇后 只需要我们每行中填充一个皇后即可，但是这道题需要我们将整个表给填满，这个是比较复杂的，并检查数字是否合法，解数独的树形结构要比N皇后更宽更深。
因为这个树形结构太大了，部分结构如图所示：
、
接下来我们按照回溯三部曲：
- 递归函数以及参数
- 这道题和我们之前写过的回溯题不太一样，因为这道题的递归函数返回值需要是 bool 类型！为什么呢❓❓❓因为我们只希望返回一张有效的数独表，而不希望说找到所有的可能，那么我们就可以用 bool 类型来判断，如果得到了一张有效的数独表了，那么直接就返回了！
- 另外由于这道题并不需要我们进行组合等问题，所以不需要 index 等参数！
- 递归终止条件
- 本题递归不需要终止条件，解数独是要遍历整个树形结构寻找可能的叶子节点就立刻返回。不用终止条件会不会死循环❓❓❓ 递归的下一层的棋盘一定比上一层的棋盘多一个数，等数填满了棋盘自然就终止（填满当然好了，说明找到结果了），所以不需要终止条件！
- 单层搜索逻辑
- 在树形图中可以看出我们需要的是一个二维的递归（也就是两个for循环嵌套着递归）因为我们在N皇后那道题中，我们只需要填充每一行的一个皇后，但是这道题由于需要填满，所以我们必须在递归的时候就从同一行的下一个元素开始判断，因此我们不只是需要一个 for 循环，我们需要两个来遍历完所有的数独位置！一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！
- 注意这里return false的地方，这里放return false 是有讲究的。因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！那么会直接返回， 这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！
- 若最后两层 for 循环都遍历完了，那么最后一次递归进来的时候，直接判断到最下面的 return true 语句，直接返回，那么上一层接收到了 true，又返回给上一层，以此循环直到返回到了根部，根部最后也直接 return true，不再去执行 for 循环！
判断棋盘是否合法
判断棋盘是否合法有如下三个维度：
- 同行是否重复
- 同列是否重复
- 9宫格里是否重复：就得先找到是在第几个九宫格内，再for循环查看
class Solution {
public:
bool isValid(vector<vector<char>>& board, int row, int col, char c)
{
// 判断每行每列是否出现过
for(int i = 0; i < 9; ++i)
{
if(board[row][i] == c)
return false;
}
for(int i = 0; i < 9; ++i)
{
if(board[i][col] == c)
return false;
}
// 判断一个九宫格内是否重复出现
int rown = row / 3; // 行在第几个九宫格
int coln = col / 3; // 列在第几个九宫格
for(int i = rown*3; i < rown*3 + 3; ++i)
{
for(int j = coln*3; j < coln*3 + 3; ++j)
{
if(board[i][j] == c)
return false;
}
}
return true;
}
bool backtracking(vector<vector<char>>& board)
{
for(int i = 0; i < board.size(); ++i) // 遍历行
{
for(int j = 0; j < board[i].size(); ++j) // 遍历列
{
if(board[i][j] == '.')
{
for(char c = '1'; c <= '9'; ++c) // 遍历1到9的字符分别看看符不符合
{
if(isValid(board, i, j, c) == true) // 检测放置该字符是否合法
{
board[i][j] = c; // 放置
if(backtracking(board) == true) // 递归，如果符合了直接return，因为我们只需要找一张正确的棋盘
return true;
board[i][j] = '.'; // 回溯
}
}
return false; // 走到这里说明给我们的棋盘本身是不对的才会9个数字字符都不符合
}
}
}
return true; // 这个是用于最后一次递归的时候返回给之前所有的backtracking，结合树形结构理解一下！
}
void solveSudoku(vector<vector<char>>& board) {
backtracking(board);
}
};