算法 |
您所在的位置：网站首页 › 数独唯一解的条件是什么 › 算法 |
算法
|
算法-回溯-解数独
1 题目概述
1.1 题目出处
https://leetcode-cn.com/problems/sudoku-solver/ 1.2 题目描述
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皇后 2.2 代码 class Solution { // 存放数字所在的行set Map rowMap = new HashMap(); // 存放数字所在的列set Map columnMap = new HashMap(); // 存放数字所在的块set Map blockMap = new HashMap(); public void solveSudoku(char[][] board) { // 进行初始化 for(int k = 1; k for(int j = 0; 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 // 说明此位置不合法，只能尝试下一个数字 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 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 return backtrack(board, surplus, i + 1, 0); } } } } 2.3 时间复杂度
前面的回溯法，在判断每个数字是否能放置时，需要为每个数字都维护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 for(int j = 0; 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 // 说明此位置不合法，只能尝试下一个数字 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 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 return backtrack(board, surplus, i + 1, 0); } } } } 3.3 时间复杂度
换用二维数组试试。 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 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 // 说明此位置不合法，只能尝试下一个数字 continue; } board[i][j] = (char)(k + '0'); rowSets[k][i] = 1; columnSets[k][j] = 1; blockSets[k][blockId] = 1; boolean result; if(j 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 return backtrack(board, surplus, i + 1, 0); } } } } 4.3 时间复杂度
|
上图中答案被标成红色。
【本文地址】