当前位置: 首页> 房产> 建材 > 东莞建站公司速推全网天下首选_兰州快速seo整站优化招商_关键词调词平台_网站关键词优化建议

东莞建站公司速推全网天下首选_兰州快速seo整站优化招商_关键词调词平台_网站关键词优化建议

时间:2025/7/10 4:21:59来源:https://blog.csdn.net/m0_51437455/article/details/142753766 浏览次数:0次
东莞建站公司速推全网天下首选_兰州快速seo整站优化招商_关键词调词平台_网站关键词优化建议

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时的回溯函数一定返回Truedef 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 Truevalid=Falsefor 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]=Truevalid=backtrack(spaceIndex+1)rows[row][i]=cols[col][i]=blocks[row//3*3+col//3][i]=Falseif valid:breakreturn 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]=Truecols[j][num-1]=Trueblocks[i//3*3+j//3][num-1]=Trueelse: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.执行结果

在这里插入图片描述

关键字:东莞建站公司速推全网天下首选_兰州快速seo整站优化招商_关键词调词平台_网站关键词优化建议

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: