Leetcode 37. 解数独
1.题目基本信息
1.1.题目描述
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。
1.2.题目地址
https://leetcode.cn/problems/sudoku-solver/description/
2.解题方法
2.1.解题思路
回溯
2.2.解题步骤
第一步，使用数组记录每一行、每一列、每一块的各个数字的存在状态，分别记为rows、cols、blocks，其中rows[i][j]=True表示j+1数字在下标为i的行中，反之亦然，cols和blocks也同理。与此同时，使用spaces记录所有为空的点的坐标，在后续的回溯中将其遍历填充。
第二步，构建回溯函数
- 函数传入当前处理的空坐标在spaces数组中的下标spaceIndex，返回内容为spaces[spaceIndex:]能否构建完整的合法的数独组合。
- 回溯本质上还是递归，所以第一步判断边界条件，当spaceIndex=len(spaces)时，根据返回内容的性质，可知返回True；
- 第二步，遍历1-9，如果当前位置的行、列、块都没有该数字，则可以将该数字填入当前的spaceIndex的位置，同时标记rows、cols、blocks该位置为True，标记完后，递归spaceIndex+1处的下一个空位置，获取spaces[spaceIndex+1:]是否能构建合法的数独，记为valid，然后将rows、cols、blocks回溯为False（回溯是为了不影响后面在spaceIndex状况的for循环），如果递归返回valid为True，则可以直接退出for循环，代表已经构建了合法的数独，直接返回valid即可；如果经过9次的for循环都没有构建合法的数独，代表spaces[spaceIndex:]不能构建合法的数独，返回False。
注意：在递归的过程中，会将board进行修改，最终的回溯退出时，构建的数独为合法数独组合，此时的board即为题解，由于题目已经声明了数独一定有解，所以spaceIndex=0时的回溯函数一定返回True
3.解题代码
Python代码
class Solution:
# 回溯
# 第一步，使用数组记录每一行、每一列、每一块的各个数字的存在状态，分别记为rows、cols、blocks，其中rows[i][j]=True表示j+1数字在下标为i的行中，反之亦然，cols和blocks也同理。与此同时，使用spaces记录所有为空的点的坐标，在后续的回溯中将其遍历填充。
# 第二步，构建回溯函数
# > 函数传入当前处理的空坐标在spaces数组中的下标spaceIndex，返回内容为spaces[spaceIndex:]能否构建完整的合法的数独组合。
# > 回溯本质上还是递归，所以第一步判断边界条件，当spaceIndex=len(spaces)时，根据返回内容的性质，可知返回True；
# > 第二步，遍历1-9，如果当前位置的行、列、块都没有该数字，则可以将该数字填入当前的spaceIndex的位置，同时标记rows、cols、blocks该位置为True，标记完后，递归spaceIndex+1处的下一个空位置，获取spaces[spaceIndex+1:]是否能构建合法的数独，记为valid，然后将rows、cols、blocks回溯为False（回溯是为了不影响后面在spaceIndex状况的for循环），如果递归返回valid为True，则可以直接退出for循环，代表已经构建了合法的数独，直接返回valid即可；如果经过9次的for循环都没有构建合法的数独，代表spaces[spaceIndex:]不能构建合法的数独，返回False。
# 注意：在递归的过程中，会将board进行修改，最终的回溯退出时，构建的数独为合法数独组合，此时的board即为题解，由于题目已经声明了数独一定有解，所以spaceIndex=0时的回溯函数一定返回True
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
# 从spaces中第一个位置开始遍历回溯；返回spaces[spaceIndex:]能不能填充成合法的数独，并在判断过程中设置board，在合法的数独填充时退出回溯
def backtrack(spaceIndex):
if spaceIndex==len(spaces):
return True
valid=False
for i in range(9):
row,col=spaces[spaceIndex]
if not rows[row][i] and not cols[col][i] and not blocks[row//3*3+col//3][i]:
board[row][col]=str(i+1)
rows[row][i]=cols[col][i]=blocks[row//3*3+col//3][i]=True
valid=backtrack(spaceIndex+1)
rows[row][i]=cols[col][i]=blocks[row//3*3+col//3][i]=False
if valid:
break
return valid
# 第一步，记录当前数独数组的行、列、块的状态；rows[i][j]指下标为i的行的数字j+1是否存在，cols和blocks同理
rows=[[False]*9 for _ in range(9)]
cols=[[False]*9 for _ in range(9)]
blocks=[[False]*9 for _ in range(9)]
spaces=[] # 空的位置的坐标列表
for i in range(9):
for j in range(9):
if board[i][j]!=".":
num=int(board[i][j])
rows[i][num-1]=True
cols[j][num-1]=True
blocks[i//3*3+j//3][num-1]=True
else:
spaces.append((i,j))
# print(rows,"\n",cols,"\n",blocks)
# print(spaces)
# print(backtrack(0))
backtrack(0)
C++代码
class Solution {
private:
vector<vector<bool>> rows;
vector<vector<bool>> cols;
vector<vector<bool>> blocks;
vector<pair<int,int>> spaces;
public:
bool backtrack(int spaceIndex,vector<vector<char>>& board){
if(spaceIndex==spaces.size()){
return true;
}
bool valid=false;
for(int i=0;i<9;++i){
int row=spaces[spaceIndex].first,col=spaces[spaceIndex].second;
if(!rows[row][i] && !cols[col][i] && !blocks[row/3*3+col/3][i]){
board[row][col]=(i+1)+'0';
rows[row][i]=cols[col][i]=blocks[row/3*3+col/3][i]=true;
valid=backtrack(spaceIndex+1,board);
rows[row][i]=cols[col][i]=blocks[row/3*3+col/3][i]=false;
}
if(valid)break;
}
return valid;
}
void solveSudoku(vector<vector<char>>& board) {
rows=vector<vector<bool>>(9,vector<bool>(9,false));
cols=vector<vector<bool>>(9,vector<bool>(9,false));
blocks=vector<vector<bool>>(9,vector<bool>(9,false));
for(int i=0;i<9;++i){
for(int j=0;j<9;++j){
if(board[i][j]!='.'){
int num=board[i][j]-'0';
rows[i][num-1]=true;
cols[j][num-1]=true;
blocks[i/3*3+j/3][num-1]=true;
}else{
spaces.push_back(pair<int,int>(i,j));
}
}
}
backtrack(0,board);
}
};
4.执行结果
