Leetcode 37 解数独

2023-12-14 17:32:16

题意理解

? ? ? ? 填充数独。每个九宫格内,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 rowIndex=0;rowIndex<board.length;rowIndex++){
            for(int colIndex=0;colIndex<board.length;colIndex++){
                //是否需要填数字
                if(board[rowIndex][colIndex]!='.') continue;
                //控制数字选择
                for(char num='1';num<='9';num++){
                    //判断填入该数字是否合法
                    if(isValid(board,rowIndex,colIndex,num)){
                        board[rowIndex][colIndex]= num;
                        boolean result=backtracking(board);
                        if(result==true) 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 j=0;j<board.length;j++) if(board[rowIndex][j]==num) return false;
        //列判断
        for(int i=0;i<board.length;i++) if(board[i][colIndex]==num) return false;
        //九宫格判断
        int startI=Math.floorDiv(rowIndex,3)*3,startJ=Math.floorDiv(colIndex,3)*3;//九宫格左上角起始位置
        for(int i=0;i<9;i++){//遍历九宫格的9个位置
            if(board[startI+Math.floorDiv(i,3)][startJ+i%3]==num) return false;
        }
        return true;
    }

2.分析

时间复杂度:O(9^{9\times 9})

空间复杂度:O(9×9)

????????作为一个数独,最大9行,9列,共81个格子

? ? ? ? 每个格子有1-9的选择

文章来源:https://blog.csdn.net/lt_BeiMo/article/details/134992511
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。