题目描述
编写一个程序，通过填充空格来解决数独问题。 数独的解法需 遵循如下规则： 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图） 数独部分空格内已填入了数字，空白格用 ’.’ 表示。
Example 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”]] 解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
Constraints:
- board.length == 9
- board[i].length == 9
- board[i][j] 是一位数字或者 ‘.’
- 题目数据 保证 输入数独仅有一个解
解题思路
- 回溯思路
- 使用行，列，方格来表示此时是否有值
- 相应的模版：
backtrack(当前进度): if 当前进度 == 最终进度： 结果集.加入(进度状态） else: for 下一节点 in 当前进度下可以到达的节点: if 节点 满足 限制状态： 修改进度状态为下一节点 修改限制状态为下一节点 backtrack(下一节点) 修改限制状态回当前进度 修改进度状态回当前进度 //最后这两行改回就是所谓的“回溯”
C++代码
class Solution {
private:
// 必要的数据 模拟整个棋盘,行 列 方格
bool mCol[9][9];
bool mRow[9][9];
bool mCell[9][9];
// 存在待插入数据的位置（即空白的格的坐标），行列为first， second
vector<pair<int, int>> mSpace;
public:
void solveSudoku(vector<vector<char>>& board) {
if(board.size() == 0){
return;
}
for(int i = 0; i < board.size(); i++){
for(int j = 0; j < board[0].size(); j++){
char c = board[i][j];
if(board[i][j] == '.'){
mSpace.push_back({i, j});
}else{
mRow[i][c - '1'] = true;
mCol[j][c - '1'] = true;
mCell[i / 3 * 3 + j / 3][c - '1'] = true;
}
}
}
dfs(board, 0);
}
bool dfs(vector<vector<char>>& board, int index){
if(index == mSpace.size()){
return true;
}
int row = mSpace[index].first;
int col = mSpace[index].second;
for(auto c = '1'; c <= '9'; c++){
int num = c - '1';
if(!mRow[row][num] && !mCol[col][num] && !mCell[row / 3 * 3 + col / 3][num]){
board[row][col] = c;
mRow[row][num] = true;
mCol[col][num] = true;
mCell[row / 3 * 3 + col / 3][num] = true;
if(dfs(board, index + 1)){
return true;
}
mRow[row][num] = false;
mCol[col][num] = false;
mCell[row / 3 * 3 + col / 3][num] = false;
}
}
return false;
}
};
