题目一：解数读
问题描述
37. 解数独 - 力扣（LeetCode）
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。
提示：
board.length == 9board[i].length == 9board[i][j]是一位数字或者'.'- 题目数据 保证 输入数独仅有一个解
解题思路
看到这一题第一反应是和N皇后有点类似
开始用同样的思路套
但总觉得哪里好像漏了点啥
或者说感觉实现不了在每个格子填上正确的数，要考虑和顾忌的因素有点多了
但这就是回溯算法的本领所在！
往简单了想，剩下的交给递归和回溯！
那么重新品一下题目，由于题目已经规定
board.length == 9board[i].length == 9
就是说这个数独大棋盘是9×9的
然后它会在某些位置给出数字，要求我们去填剩下的格子
简单点看就是不要太在意它是个二维数组
我们要做的仅仅是在这81个数字中空缺的位置按顺序填上合适的数字
到底怎么样合适有isValid函数按照规则判断
不合适也有递归、遍历替我们处理
如果你想问：怎么知道这一格填下去的数字不会影响后续呢？
因为你在填的时候是一直往后一个空格走的，
如果这个plan不合适，它会回溯后换一个分支，就直接倒回去修改，
那这一块让我们用手写画出还是比较复杂的
但对计算机来说不困难，笨笨的暴力搜索就好啦，没有啥技术含量的
ok差不多可以开始敲代码啦！
还是走回溯三部曲
1.确定函数返回值及参数
由于这一题我们会直接在board上修改，并且只有一个解（题目数据 保证 输入数独仅有一个解）
那我们递归过程就需要专注于合不合法，对不对即可，那返回值应当是bool
参数就是需要修改的board，
为什么没有row，或者col呢？请往下看就知道了！
2.确定终止条件
这一题想要终止得到最后结果，那就是正确填完所有格子，
那么我们遍历结束实际上整个流程也结束了，没有必要再加终止条件
3.遍历逻辑
上面讲到我们可以视为在填81个格子中空缺的部分
那么为了明确表示空格位置我们应该用两个for循环嵌套实现
for(int i=0;i<9;i++){//行
for(int j=0;j<9;j++){//列
有数字有空格，需要处理空格那肯定要先找到
所以加上判断空格的语句是空格那么我们就要继续
if ( board [ i ][ j ] == ' . ')
或者选择跳过有数字的格子
if(board [ i ][ j ] != ' . ') continue;
在空格位置我们就要尝试填入数字，
如果作为一个完全不会数独的人来说
他最可能做的就是从1~9挨个试一遍
我们让计算机学他就行
for(int k='1';k<='9';k++)//注意是char
选择一个数字后就要进行合法性判断，那么在这个循环中加入if语句检验
if(isValid(.....))//合法性验证函数等会解决
如果当前填这个数合适，
那么我们就需要填入这个数，再递归填下一个空,再回溯
board[i][j]=k;
backtracking(board);
board[i][j]='.';
其中backtracking(board);语句是一直往下填，填满81格
但我们要的是正确才继续，并且需要返回给上一层，错误就及时止损
所以这一句应该改为
if(backtracking(board)) return true
如果这个递归结束，在当前格试完9个数字，没有合适的
就应该立即返回false
for(int k='1';k<='9';k++){
...
}
return false
那么这整个函数最后肯定还是要一个完整的返回值的
所以在最后要加上返回true,表示完成数独！返回提交答案
return true;
在主函数中直接调用backtracking函数即可
backtracking(board) ;
4.验证合法性
验证函数那我们最后要的肯定是对or错
所以返回值应该是bool型
验证这个格子数值是否合法，
那么需要这整个数独填的咋样了，检查的是哪一格，现在填的什么数
故参数为board，i，j
bool isValid(vector<vector<char>>& board,int row,int col，int value)
需要满足要求：
1）同一行不存在重复的
那就是在row相等的元素中，从0位开始检查是否有和value值一样的
如果有，就返回false
for(int j=0; j<9; j++){
if(board[row][j]==value){
return false;
}
}
2）同一列不存在重复的
逻辑一样，需要检查在col相等的元素中，从0位开始是否有和value值一样的
如果有，就返回false
if(int i=0;i<9;i++){
if(board[i][col]==value){
return false;
}
}
注意！以上都要检查一整行，而不是像N皇后只检查前面部分
数独可能后面有给出数字，那么我们遍历整行才能快速排掉不正确方案
否则可能会导致大量无效的递归调用，最后就超时了！！！
3) 3x3 宫内不存在重复的
这一步稍微有点复杂，但就是要算出它是哪一小片，遍历这一片即可
用/3可以得到片区的序号再由此计算起始行号和起始列号
例如board[4][6]，第二排左边片区
行号4/3=1，起始行号就是1*3，终止行号就是i*3+2
列号6/3=2，起始列号就是2*3，终止列号就是2*3+2
除此以外遍历时要注意避开当前检验的格子，不然肯定有一样的（自己和自己一样）
for(int i=row/3*3;i<=row/3*3+2;i++){
for(int j=col/3*3;j<=col/3*3+2;j++){
if(i!=row && j!==col && board[i][j]==value){
return false;
}
}
都没违反规则则返回true
return true;
完整代码看下面！
code
class Solution {
private:bool isValid(vector<vector<char>>& board,int row,int col,int value){for(int j=0;j<9;j++){if(board[row][j]==value){return false;}}for(int i=0;i<9;i++){if(board[i][col]==value){return false;}}for(int i=row/3*3;i<=row/3*3+2;i++){for(int j=col/3*3;j<=col/3*3+2;j++){if(board[i][j]==value){return false;}}}return true;}bool backtracking(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 k='1';k<='9';k++){if(isValid(board,i,j,k)){board[i][j]=k;if(backtracking(board)) return true;board[i][j]='.';}}return false;}}return true;}
public:void solveSudoku(vector<vector<char>>& board) {backtracking(board);}
};
