贸易公司网站设计,建设部网站158号文件,插画网站,万网上传网站题意理解#xff1a; 填充数独。每个九宫格内#xff0c;9个数字各出现一个次#xff0c;每行#xff0c;每列上#xff0c;9个数字各出现一次。数独部分空格内已填入了数字#xff0c;空白格用 . 表示。 这道题要比N皇后问题更难#xff1a; N皇后只放置N个皇后的位置 填充数独。每个九宫格内9个数字各出现一个次每行每列上9个数字各出现一次。数独部分空格内已填入了数字空白格用 . 表示。 这道题要比N皇后问题更难 N皇后只放置N个皇后的位置但是数独需要填满整个结构。 N皇后每个位置只有放与不放两种状态但是数独每个位置都有1-9个选择。 所以我们不止要遍历数独上的每个位置还要遍历1-9的数字以保证在合适的位置放上合适的数字。 图摘自《代码随想录》 解题思路 N皇后、数独问题都可以使用回溯法来解决。 其实都是可以将问题解决看作一个一个步骤前一个步骤会对后一个步骤产生影响且每个步骤都有n个选择。这是一大类问题。 所以仍旧可以将其解决方案抽象为一个树结构。 图摘自《代码随想录》 1.暴力回溯剪枝优化
前提条件判断该位置填某数字是否合法
这与寻找N皇后合法的摆放位置不同我们只要求得将数独填完得唯一解即可所以这里我们用到的回溯方法可以设置返回值。
第一个for循环遍历每一行
第二个for函数相当于遍历每一个行的每一个位置。
由于每个位置又有1-9的选择所以还需要一个for循环来控制数字选择——选择到正确值则向下递归要么找到正确解要么找不到。
某位置找不到正确解时board状态向上回溯——return false。
回溯的三个步骤确定返回值和参数列表有返回值指示是否能获得唯一的解。 确定终止条件找到唯一解即终止。 确定单层递归逻辑递归的目的是找到满足条件的唯一解。 public void solveSudoku(char[][] board) {backtracking(board);}//回溯求唯一解public boolean backtracking(char[][] board){//终止条件找到唯一解时即返回//遍历该行的每一个位置for(int rowIndex0;rowIndexboard.length;rowIndex){for(int colIndex0;colIndexboard.length;colIndex){//是否需要填数字if(board[rowIndex][colIndex]!.) continue;//控制数字选择for(char num1;num9;num){//判断填入该数字是否合法if(isValid(board,rowIndex,colIndex,num)){board[rowIndex][colIndex] num;boolean resultbacktracking(board);if(resulttrue) return true;board[rowIndex][colIndex] .;}}//换了9个数字都没有return true,则额说明这样下去找不到合适解return false;}}return true;}//判断在board的 rowIndex, colIndex填入num是否合法public boolean isValid(char[][] board,int rowIndex,int colIndex,char num){//行判断for(int j0;jboard.length;j) if(board[rowIndex][j]num) return false;//列判断for(int i0;iboard.length;i) if(board[i][colIndex]num) return false;//九宫格判断int startIMath.floorDiv(rowIndex,3)*3,startJMath.floorDiv(colIndex,3)*3;//九宫格左上角起始位置for(int i0;i9;i){//遍历九宫格的9个位置if(board[startIMath.floorDiv(i,3)][startJi%3]num) return false;}return true;} 2.分析 时间复杂度O() 空间复杂度O(9×9) 作为一个数独最大9行9列共81个格子 每个格子有1-9的选择
