LeetCode_回溯_递归_困难_37.解数独

超、凢脫俗 2023-10-06 18:53 30阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

## 2.思路 ##

（1）回溯  
思路参考[回溯算法最佳实践：解数独][Link 1]。  
（2）递归（来自[本题LeetCode官方题解][LeetCode]）

## 3.代码实现（Java） ##

//思路1————回溯
    public void solveSudoku(char[][] board) {
        
        backtrack(board, 0, 0);
    }
    
    public boolean backtrack(char[][] board, int i, int j) {
        
        int m = 9, n = 9;
        if (j == n) {
        
            //遍历到最后一列的话就换到下一行重新开始。
            return backtrack(board, i + 1, 0);
        }
        if (i == m) {
        
            //找到一个可行解
            return true;
        }
        if (board[i][j] != '.') {
        
            //当前位置有预设数字，直接处理下一个位置即可
            return backtrack(board, i, j + 1);
        } else {
        
            //处理当前位置
            for (char c = '1'; c <= '9'; c++) {
        
                if (!isValid(board, i, j, c)) {
        
                    continue;
                }
                //将c填入当前位置
                board[i][j] = c;
                if (backtrack(board, i, j + 1)) {
        
                    return true;
                }
                /*
                	此时填入c虽然满足规则，但是会影响其它位置，即不是最终解，所以需要将其还原
    				等其它某些位置填入完成后，才能确定当前位置
    			*/
                board[i][j] = '.';
            }
        }
        //穷举完 1~9，依然没有找到可行解，则说明此路不通
        return false;
    }
    
    //判断board[i][j]处是否可以填入数字字符c
    public boolean isValid(char[][] board, int i, int j, char c) {
        
        for (int k = 0; k < 9; k++) {
        
            //判断行
            if (board[i][k] == c) {
        
                return false;
            }
            //判断列
            if (board[k][j] == c) {
        
                return false;
            }
            //判断当前位置所处的3x3方格
            if (board[(i / 3) * 3 + k / 3][(j / 3) * 3 + k % 3] == c) {
        
                return false;
            }
        }
        return true;
    }

//思路2————递归（来自本题LeetCode官方题解以及网友注释）
    class Solution {
        
        //存储每一行存在的数字 
        private int[] line = new int[9];
        //存储每一列存在的数字
        private int[] column = new int[9];
        //存储每一个 3*3宫存在的数字 
        private int[][] block = new int[3][3];
        //判断是否填完所有空格
        private boolean valid = false;
        //用来记录所有空格的位置，整数数组第一个位置为行的位置 ，第二个位置为列的位置
        private List<int[]> spaces = new ArrayList<int[]>();
    
        public void solveSudoku(char[][] board) {
        
            //遍历所有位置
            for (int i = 0; i < 9; ++i) {
        
                for (int j = 0; j < 9; ++j) {
        
                    //如果位置为空，我们把该位置加入spaces中
                    if (board[i][j] == '.') {
        
                        spaces.add(new int[]{
        i, j});
                    } else {
        
                        //不为空则把该数字分别纳入对应的行，列，3*3宫中
                        int digit = board[i][j] - '0' - 1;
                        flip(i, j, digit);
                    }
                }
            }
            //开始搜索
            dfs(board, 0);
        }
    
        public void dfs(char[][] board, int pos) {
        
            //如果spaces被遍历完了，说明我们填完了空格，将valid改为true，通过return结束这个函数
            if (pos == spaces.size()) {
        
                valid = true;
                return;
            }
            //获取第一个空格的位置 
            int[] space = spaces.get(pos);
            //i，j分别为该空格的行数和列数 
            int i = space[0], j = space[1];
            //'|'为or，通过3个或运算可以得到一个9位的二进制数字，从右到左分别代表1-9这个9个数是否可以填入该空格，通过~运算（取反），
            //用1表示该数字是一个可填入的选项，0x1ff为十六进制 ，等同于111111111
            int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;
            //当mask不为0并且 valid为false表示还有数待填入，继续这个循环，mask &= (mask - 1)把最低位的1变为0
            for (; mask != 0 && !valid; mask &= (mask - 1)) {
        
                //这个操作只保留最低位的1
                int digitMask = mask & (-mask);
                //最低位的1后面的位数，digitMask-1将原本1后面的0全部变为了1
                int digit = Integer.bitCount(digitMask - 1);
                //更新行，列，宫
                flip(i, j, digit);
                //把该数填入板中
                board[i][j] = (char) (digit + '0' + 1);
                //继续搜索 
                dfs(board, pos + 1);
                //撤回操作（原理是flip中的~运算，两个 1则为0,0表示这个位置代表的1-9中的那个数 不再是一个可被填入的选项）
                flip(i, j, digit);
            }
        }
    
        public void flip(int i, int j, int digit) {
        
            //^代表异或，只有1个1的时候才为1。比如0011^1001=1010
            //<<代表左移，比如 1<<2=4被加入到下面的三个数组中，在二进制4为100，意味着3这个数字被占用了
            line[i] ^= (1 << digit);
            column[j] ^= (1 << digit);
            block[i / 3][j / 3] ^= (1 << digit);
        }
    }

[Link 1]: https://labuladong.gitee.io/algo/4/30/112/
[LeetCode]: https://leetcode-cn.com/problems/sudoku-solver/solution/jie-shu-du-by-leetcode-solution/