算法-回溯-解数独

以你之姓@ 2022-12-07 11:49 178阅读 0赞

# 算法-回溯-解数独 #

# 1 题目概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/sudoku-solver/

## 1.2 题目描述 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70_pic_center]  
上图中答案被标成红色。

Note:

*  给定的数独序列只包含数字 1-9 和字符 ‘.’ 。
 *  你可以假设给定的数独只有唯一解。
 *  给定数独永远是 9x9 形式的。

# 2 低效的回溯法 #

## 2.1 思路 ##

这段转自[组合总和-解题思路][-]

回溯法的解体框架是什么呢，解决一个回溯问题，实际上就是一个决策树的遍历过程。一般来说，我们需要解决三个问题：

*  路径：也就是已经做出的选择。
 *  选择列表：也就是你当前可以做的选择。
 *  结束条件：也就是到达决策树底层，无法再做选择的条件。

其中最关键的点就是：在递归之前做选择，在递归之后撤销选择。

LinkedList result = new LinkedList();
    public void backtrack(路径，选择列表){ 
        if(满足结束条件){ 
            result.add(结果);
            return;
        }
        for(选择：选择列表){ 
            做出选择;
            backtrack(路径，选择列表);
            撤销选择;
        }
    }

这里我们每次回溯递归时，就从1到9遍历，并按行、列、Block判断是否冲突，如果冲突则不选继续看下一个数字；如果不冲突就填入该数字，并继续backtrack下一个格子。

我们算法顺序是从左到右，从上到下。

可参考[算法-回溯-N皇后][-_-N]

## 2.2 代码 ##

class Solution { 
        // 存放数字所在的行set
        Map<Integer, Set<Integer>> rowMap = new HashMap<>();
    
        // 存放数字所在的列set
        Map<Integer,Set<Integer>> columnMap = new HashMap<>();
    
        // 存放数字所在的块set
        Map<Integer,Set<Integer>> blockMap = new HashMap<>();
    
        public void solveSudoku(char[][] board) { 
            // 进行初始化
            for(int k = 1; k < 10; k++){ 
                rowMap.put(k, new HashSet<Integer>(16));
                columnMap.put(k, new HashSet<Integer>(16));
                blockMap.put(k, new HashSet<Integer>(16));
            }
    
            int surplus = board.length * board.length;
    
            for(int i = 0; i < board.length; i++){ 
                for(int j = 0; j < board.length; j++){ 
                    if(board[i][j] != '.'){ 
                        surplus--;
                        rowMap.get(board[i][j] - '0').add(i);
                        columnMap.get(board[i][j] - '0').add(j);
                        blockMap.get(board[i][j] - '0').add(i/3 * 3 + j/3);
                    }
                }
            }
    
            backtrack(board, surplus, 0, 0);
        }
    
        private boolean backtrack(char[][] board, int surplus, int i, int j){ 
            if(surplus == 0){ 
            	// 结束条件
                return true;
            }
    
            if(board[i][j] == '.'){ 
                int blockId = i/3 * 3 + j/3;
    
                // 说明此位置还没有填数字
                // 从1到9尝试数字
                for(int k = 1; k < 10; k++){ 
                    if(rowMap.get(k).contains(i) || columnMap.get(k).contains(j) || blockMap.get(k).contains(blockId)){ 
                        // 说明此位置不合法，只能尝试下一个数字
                        continue;
                    }
                    board[i][j] = (char)(k + '0');
                    rowMap.get(k).add(i);
                    columnMap.get(k).add(j);
                    blockMap.get(k).add(blockId);
    
                    boolean result;
                    if(j < board.length - 1){ 
                        result = backtrack(board, surplus - 1, i, j + 1);
                    } else{ 
                        result = backtrack(board, surplus - 1, i + 1, 0);
                    }
    
                    if(result == true){ 
                        return true;
                    }
    
                    board[i][j] = '.';
                    rowMap.get(k).remove(i);
                    columnMap.get(k).remove(j);
                    blockMap.get(k).remove(blockId);
                }
                return false;
            }else{ 
                if(j < board.length - 1){ 
                    return backtrack(board, surplus, i, j + 1);
                } else{ 
                    return backtrack(board, surplus, i + 1, 0);
                }
            }
        }
    }

## 2.3 时间复杂度 ##

![在这里插入图片描述][20200915150030620.png_pic_center]  
![在这里插入图片描述][20200915150042231.png_pic_center]

# 3 使用BitSet优化后的回溯法 #

## 3.1 思路 ##

前面的回溯法，在判断每个数字是否能放置时，需要为每个数字都维护HashSet，我们换做BitSet试试。

## 3.2 代码 ##

class Solution { 
        // 存放数字所在的行set
        BitSet[] rowSets = new BitSet[10];
    
        // 存放数字所在的列set
        BitSet[] columnSets = new BitSet[10];
    
        // 存放数字所在的块set
        BitSet[] blockSets = new BitSet[10];
    
        public void solveSudoku(char[][] board) { 
            // 进行初始化
            int surplus = board.length * board.length;
    
            for(int k = 1; k < 10; k++){ 
                rowSets[k] = new BitSet(9);
                columnSets[k] = new BitSet(9);
                blockSets[k] = new BitSet(9);
            }
    
            for(int i = 0; i < board.length; i++){ 
                for(int j = 0; j < board.length; j++){ 
                    if(board[i][j] != '.'){ 
                        surplus--;
                        int num = board[i][j] - '0';
                        rowSets[num].set(i, true);
                        columnSets[num].set(j, true);
                        blockSets[num].set(i/3 * 3 + j/3, true);
                    }
                }
            }
    
            backtrack(board, surplus, 0, 0);
        }
    
        private boolean backtrack(char[][] board, int surplus, int i, int j){ 
            if(surplus == 0){ 
                return true;
            }
    
            if(board[i][j] == '.'){ 
                int blockId = i/3 * 3 + j/3;
    
                // 说明此位置还没有填数字
                // 从1到9尝试数字
                for(int k = 1; k < 10; k++){ 
                    if(rowSets[k].get(i) || columnSets[k].get(j) || blockSets[k].get(blockId)){ 
                        // 说明此位置不合法，只能尝试下一个数字
                        continue;
                    }
                    board[i][j] = (char)(k + '0');
                    rowSets[k].set(i, true);
                    columnSets[k].set(j, true);
                    blockSets[k].set(blockId, true);
    
                    boolean result;
                    if(j < board.length - 1){ 
                        result = backtrack(board, surplus - 1, i, j + 1);
                    } else{ 
                        result = backtrack(board, surplus - 1, i + 1, 0);
                    }
    
                    if(result == true){ 
                        return true;
                    }
    
                    board[i][j] = '.';
                    rowSets[k].set(i, false);
                    columnSets[k].set(j, false);
                    blockSets[k].set(blockId, false);
                }
                return false;
            }else{ 
                if(j < board.length - 1){ 
                    return backtrack(board, surplus, i, j + 1);
                } else{ 
                    return backtrack(board, surplus, i + 1, 0);
                }
            }
        }
    }

## 3.3 时间复杂度 ##

![在这里插入图片描述][20200915153500755.png_pic_center]

# 4 使用BitSet优化后的回溯法 #

## 4.1 思路 ##

换用二维数组试试。

## 4.2 代码 ##

class Solution { 
        // 存放数字所在的行set
        int[][] rowSets = new int[10][9];
    
        // 存放数字所在的列set
        int[][] columnSets = new int[10][9];
    
        // 存放数字所在的块set
        int[][] blockSets = new int[10][9];
    
        public void solveSudoku(char[][] board) { 
            // 进行初始化
            int surplus = board.length * board.length;
    
            for(int i = 0; i < board.length; i++){ 
                for(int j = 0; j < board.length; j++){ 
                    if(board[i][j] != '.'){ 
                        surplus--;
                        int num = board[i][j] - '0';
                        rowSets[num][i] = 1;
                        columnSets[num][j] = 1;
                        blockSets[num][i/3 * 3 + j/3] = 1;
                    }
                }
            }
    
            backtrack(board, surplus, 0, 0);
        }
    
        private boolean backtrack(char[][] board, int surplus, int i, int j){ 
            if(surplus == 0){ 
                return true;
            }
    
            if(board[i][j] == '.'){ 
                int blockId = i/3 * 3 + j/3;
    
                // 说明此位置还没有填数字
                // 从1到9尝试数字
                for(int k = 1; k < 10; k++){ 
                    if(rowSets[k][i] == 1 || columnSets[k][j] == 1 || blockSets[k][blockId] == 1){ 
                        // 说明此位置不合法，只能尝试下一个数字
                        continue;
                    }
                    board[i][j] = (char)(k + '0');
                    rowSets[k][i] = 1;
                    columnSets[k][j] = 1;
                    blockSets[k][blockId] = 1;
    
                    boolean result;
                    if(j < board.length - 1){ 
                        result = backtrack(board, surplus - 1, i, j + 1);
                    } else{ 
                        result = backtrack(board, surplus - 1, i + 1, 0);
                    }
    
                    if(result == true){ 
                        return true;
                    }
    
                    board[i][j] = '.';
                    rowSets[k][i] = 0;
                    columnSets[k][j] = 0;
                    blockSets[k][blockId] = 0;
                }
                return false;
            }else{ 
                if(j < board.length - 1){ 
                    return backtrack(board, surplus, i, j + 1);
                } else{ 
                    return backtrack(board, surplus, i + 1, 0);
                }
            }
        }
    }

## 4.3 时间复杂度 ##

![在这里插入图片描述][20200915154204772.png_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/b06363e416ad4f20a91a5636777bff53.png
[-]: https://leetcode-cn.com/problems/combination-sum/solution/39-zu-he-zong-he-by-ming-zhi-shan-you-m9rfkvkdad/
[-_-N]: https://blog.csdn.net/baichoufei90/article/details/105813329
[20200915150030620.png_pic_center]: /images/20221123/c91cedc74a94418581b8b3c44362ccf9.png
[20200915150042231.png_pic_center]: /images/20221123/cc12fca32dcf4439a8e456c348a807b1.png
[20200915153500755.png_pic_center]: /images/20221123/71f7380bd627460184ee3ab7eaa785b6.png
[20200915154204772.png_pic_center]: /images/20221123/47e7ba0c6c9345ec85be61f50816f1ae.png