解数独 （leetcode 37

leetcode系列

---

使用二维递归，不管在哪一层都对矩阵进行全部遍历

一、核心操作

1. 建立判断是否有效函数，对 i j 位置是否能放入k进行判断，由于此时还没有放置k，则可以直接对行列进行遍历，但是对于每一个小九宫格的遍历需要使用 先除再乘 的方式就可以将其重置为小九宫格的起始位置，再对其进行行列遍历即可
2. 建立二维回溯函数，从每一行开始遍历，再遍历每一行的每一列，对于需要填充的位置，先判断一下数字1-9能不能填进去，如果都不能填进去则说明这个数独没有结果；如果可以放进去，再进行常规的回溯操作

提示：小白个人理解，如有错误敬请谅解！

二、外层配合操作

1. 无

三、核心模式代码

代码如下：

class Solution {
public:bool isValid(int row, int col, int k, vector<vector<char>>& board){for(int i=0;i<9;i++){if(board[i][col]==k)return false;}for(int j=0;j<9;j++){if(board[row][j]==k)return false;}int startX=row/3*3;int startY=col/3*3;for(int i=startX;i<startX+3;i++){for(int j=startY;j<startY+3;j++){if(board[i][j]==k)return false;}}return true;}bool backTracking(vector<vector<char>>& board){for(int i=0;i<board.size();i++){for(int j=0;j<board.size();j++){if(board[i][j]!='.')continue;for(char k='1';k<='9';k++){if(isValid(i,j,k,board)){board[i][j]=k;if(backTracking(board))return true;board[i][j]='.';}}return false;}}return true;}void solveSudoku(vector<vector<char>>& board) {backTracking(board);}
};

---

总结

1. 一定要先判断 i j 位置能不能放入数字k，如果不能放入就尝试下一个数字，如果能放入这个数字再往里放，然后再回溯
2. 通过整数除法的特性，将 row/3*3 即可将结果变为0或3或6，这样就将一个随机的数变为每个小九宫格的起始位置