LeetCode刷题Java版037.解数独
作者：沉默王二
发布时间：2022-09-05T14:05:05.958+0800
037.解数独
题意
编写一个程序，通过填充空格来解决数独问题。
数独的解法需遵循如下规则：
-
数字 1-9 在每一行只能出现一次。
-
数字 1-9 在每一列只能出现一次。
-
数字 1-9 在每一个以粗实线分隔的 3x3 九宫格内只能出现一次。
数独的部分空格内已填入了数字，空白格用 '.' 表示。
难度
困难
示例
输入：board = [
["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
唯一有效的解决方案如下所示：
分析
解数独，这个问题通常会在一些趣味杂志或者团建活动上碰到过，朴素的解法往往是去猜一个数字，然后判断符不符合条件，符合就去猜下一个数字。
计算机在面对这类问题的时候，因为处理速度比人脑快得多多多多，所以可以挨个枚举每个 “坑” 应该填写的数字，然后加以检验，就可以得出答案了。
题目要求保证唯一解，所以我们需要记录每一个 . 的位置，然后逐个枚举合法的数字，确定与当前的每一行、每一列、每个九宫格都没有冲突，如果没有冲突，就去枚举下一个，如果有冲突的话，就表示之前填写的数字有问题，直接回溯到之前的状态，更换新的数字。
但是，要记住一点，就是我们回溯的时候……
必须要把状态恢复到之前的样子！
必须要把状态恢复到之前的样子！
必须要把状态恢复到之前的样子！
因为之后的操作，跟上次失败的操作，在逻辑关系上，是并行的，如果没有回溯到失败之前的状态，直接向下执行，那么之前失败的状态就会对现在的判断造成影响，逻辑关系就变成了上次失败之后的。
基于上述的思路，我们能够写出如下的代码：
class Solution {
private boolean[][] inCol = new boolean[9][9]; private boolean[][][] inBlock = new boolean[3][3][9]; private List<int[]> list = new ArrayList<int[]>(); private boolean victory = false; private void DFS(char[][] board,int step){ if(step == list.size()){ victory = true; return ; } int posX = list.get(step)[0],posY = list.get(step)[1]; for(int number = 0;number < 9;number++){//枚举1-9看哪个填入是符合现在的状态的 if(inRow[posX][number] || inCol[posY][number] || inBlock[posX / 3][posY / 3][number]) continue; //如果填这个数不会造成冲突 inRow[posX][number] = true; inCol[posY][number] = true; inBlock[posX / 3][posY / 3][number] = true; //打上标记，防止之后重复填写这个数字 board[posX][posY] = (char)(number + '0' + 1); DFS(board,step + 1);//继续向下枚举 if(victory) return; //如果不成功的话 状态要回溯回去 避免造成影响 board[posX][posY] = '.'; inRow[posX][number] = false; inCol[posY][number] = false; inBlock[posX / 3][posY / 3][number] = false; } } public void solveSudoku(char[][] board) { for(int i = 0;i < 9;i++) for(int j = 0;j < 9;j++){ if(board[i][j] == '.')//记录还没有填的位置 list.add(new int[]{i,j}); else{ inRow[i][board[i][j] - '0' - 1] = true; inCol[j][board[i][j] - '0' - 1] = true; inBlock[i / 3][j / 3][board[i][j] - '0' - 1] = true; } } DFS(board,0); }}
执行效果也算不错。
但是我们能不能对一些小的细节进行优化呢？百尺竿头更进一步嘛。
在上面的代码中，我们是用两个二维数组和一个三维数组来记录每行每列每个九宫格（3X3） 数字的出现与否 的。
但是，它们最多一共只会有 9 个数字出现（1-9 嘛），所以我们其实可以用一个九位的二进制来表示这个行/列/九宫格里面数字的出现情况。这样可以带来一点的常数优化。
在枚举的时候，如果需要将对应位置的0变为1的话，只需要inRow[x] |= (1 << number)，这样子就可以把inRow[x]的第number位二进制位变为1了。
反过来，回溯的时候我们要怎么样，才能将1变为0而不影响到其他位置呢？
有两种方式，一个是直接异或也就是inRow[x] ^= (1 << number)，因为我们已经知道number位是1，再异或一次，就变成0了。
另外一种方式是把1 << number整体取反inRow[x] &= ~(1 << number)，这样子只有number位是0，就可以使number位变成0了。
代码相较于之前的也不用改太多，就状态的记录那部分稍微修改一下即可：
class Solution {
private int[] inCol = new int[9]; private int[][] inBlock = new int[3][3]; private List<int[]> list = new ArrayList<int[]>(); private boolean victory = false; private void DFS(char[][] board,int step){ if(step == list.size()){ victory = true; return ; } int posX = list.get(step)[0],posY = list.get(step)[1]; for(int number = 0;number < 9;number++){ if(((inRow[posX] & (1 << number)) != 0) || ((inCol[posY] & (1 << number)) != 0) || ((inBlock[posX / 3][posY / 3] & (1 << number)) != 0)) continue; //如果填这个数不会造成冲突 inRow[posX] |= (1 << number);//换为二进制进行判断 inCol[posY] |= (1 << number); inBlock[posX / 3][posY / 3] |= (1 << number); board[posX][posY] = (char)(number + '0' + 1); DFS(board,step + 1); if(victory) return; //如果不成功的话 状态要回溯回去 board[posX][posY] = '.'; inRow[posX] &= ~(1 << number); inCol[posY] &= ~(1 << number); inBlock[posX / 3][posY / 3] &= ~(1 << number); } } public void solveSudoku(char[][] board) { for(int i = 0;i < 9;i++) for(int j = 0;j < 9;j++){ if(board[i][j] == '.') list.add(new int[]{i,j}); else{ inRow[i] |= 1 << (board[i][j] - '0' - 1); inCol[j] |= 1 << (board[i][j] - '0' - 1); inBlock[i / 3][j / 3] |= 1 << (board[i][j] - '0' - 1); } } DFS(board,0); }}
换了位运算之后，常数减小了一部分，效率有很明显的提高。
总结
本题其实就是简单的暴力枚举策略：将所有可能的情况都枚举一遍以获得最优解。当遇到问题规模比较小的情况，这样子的策略其实是最容易想到的，而且在较小的问题规模上，这个策略的实际运行效率也非常不错。
这就是最明显的能体现出计算机的计算速度的策略，而这时候，位运算优化等等的细节能够提供的帮助就非常大了。但是到了问题规模更大的情况，我们就需要另寻他法了。
力扣链接：https://leetcode.cn/problems/sudoku-solver/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。
一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 750 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！
037.解数独
题意
编写一个程序，通过填充空格来解决数独问题。
数独的解法需遵循如下规则：
-
数字 1-9 在每一行只能出现一次。
-
数字 1-9 在每一列只能出现一次。
-
数字 1-9 在每一个以粗实线分隔的 3x3 九宫格内只能出现一次。
数独的部分空格内已填入了数字，空白格用 '.' 表示。
难度
困难
示例
输入：board = [
["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
唯一有效的解决方案如下所示：
分析
解数独，这个问题通常会在一些趣味杂志或者团建活动上碰到过，朴素的解法往往是去猜一个数字，然后判断符不符合条件，符合就去猜下一个数字。
计算机在面对这类问题的时候，因为处理速度比人脑快得多多多多，所以可以挨个枚举每个 “坑” 应该填写的数字，然后加以检验，就可以得出答案了。
题目要求保证唯一解，所以我们需要记录每一个 . 的位置，然后逐个枚举合法的数字，确定与当前的每一行、每一列、每个九宫格都没有冲突，如果没有冲突，就去枚举下一个，如果有冲突的话，就表示之前填写的数字有问题，直接回溯到之前的状态，更换新的数字。
但是，要记住一点，就是我们回溯的时候……
必须要把状态恢复到之前的样子！
必须要把状态恢复到之前的样子！
必须要把状态恢复到之前的样子！
因为之后的操作，跟上次失败的操作，在逻辑关系上，是并行的，如果没有回溯到失败之前的状态，直接向下执行，那么之前失败的状态就会对现在的判断造成影响，逻辑关系就变成了上次失败之后的。
基于上述的思路，我们能够写出如下的代码：
class Solution {
private boolean[][] inCol = new boolean[9][9]; private boolean[][][] inBlock = new boolean[3][3][9]; private List<int[]> list = new ArrayList<int[]>(); private boolean victory = false; private void DFS(char[][] board,int step){ if(step == list.size()){ victory = true; return ; } int posX = list.get(step)[0],posY = list.get(step)[1]; for(int number = 0;number < 9;number++){//枚举1-9看哪个填入是符合现在的状态的 if(inRow[posX][number] || inCol[posY][number] || inBlock[posX / 3][posY / 3][number]) continue; //如果填这个数不会造成冲突 inRow[posX][number] = true; inCol[posY][number] = true; inBlock[posX / 3][posY / 3][number] = true; //打上标记，防止之后重复填写这个数字 board[posX][posY] = (char)(number + '0' + 1); DFS(board,step + 1);//继续向下枚举 if(victory) return; //如果不成功的话 状态要回溯回去 避免造成影响 board[posX][posY] = '.'; inRow[posX][number] = false; inCol[posY][number] = false; inBlock[posX / 3][posY / 3][number] = false; } } public void solveSudoku(char[][] board) { for(int i = 0;i < 9;i++) for(int j = 0;j < 9;j++){ if(board[i][j] == '.')//记录还没有填的位置 list.add(new int[]{i,j}); else{ inRow[i][board[i][j] - '0' - 1] = true; inCol[j][board[i][j] - '0' - 1] = true; inBlock[i / 3][j / 3][board[i][j] - '0' - 1] = true; } } DFS(board,0); }}
执行效果也算不错。
但是我们能不能对一些小的细节进行优化呢？百尺竿头更进一步嘛。
在上面的代码中，我们是用两个二维数组和一个三维数组来记录每行每列每个九宫格（3X3） 数字的出现与否 的。
但是，它们最多一共只会有 9 个数字出现（1-9 嘛），所以我们其实可以用一个九位的二进制来表示这个行/列/九宫格里面数字的出现情况。这样可以带来一点的常数优化。
在枚举的时候，如果需要将对应位置的0变为1的话，只需要inRow[x] |= (1 << number)，这样子就可以把inRow[x]的第number位二进制位变为1了。
反过来，回溯的时候我们要怎么样，才能将1变为0而不影响到其他位置呢？
有两种方式，一个是直接异或也就是inRow[x] ^= (1 << number)，因为我们已经知道number位是1，再异或一次，就变成0了。
另外一种方式是把1 << number整体取反inRow[x] &= ~(1 << number)，这样子只有number位是0，就可以使number位变成0了。
代码相较于之前的也不用改太多，就状态的记录那部分稍微修改一下即可：
class Solution {
private int[] inCol = new int[9]; private int[][] inBlock = new int[3][3]; private List<int[]> list = new ArrayList<int[]>(); private boolean victory = false; private void DFS(char[][] board,int step){ if(step == list.size()){ victory = true; return ; } int posX = list.get(step)[0],posY = list.get(step)[1]; for(int number = 0;number < 9;number++){ if(((inRow[posX] & (1 << number)) != 0) || ((inCol[posY] & (1 << number)) != 0) || ((inBlock[posX / 3][posY / 3] & (1 << number)) != 0)) continue; //如果填这个数不会造成冲突 inRow[posX] |= (1 << number);//换为二进制进行判断 inCol[posY] |= (1 << number); inBlock[posX / 3][posY / 3] |= (1 << number); board[posX][posY] = (char)(number + '0' + 1); DFS(board,step + 1); if(victory) return; //如果不成功的话 状态要回溯回去 board[posX][posY] = '.'; inRow[posX] &= ~(1 << number); inCol[posY] &= ~(1 << number); inBlock[posX / 3][posY / 3] &= ~(1 << number); } } public void solveSudoku(char[][] board) { for(int i = 0;i < 9;i++) for(int j = 0;j < 9;j++){ if(board[i][j] == '.') list.add(new int[]{i,j}); else{ inRow[i] |= 1 << (board[i][j] - '0' - 1); inCol[j] |= 1 << (board[i][j] - '0' - 1); inBlock[i / 3][j / 3] |= 1 << (board[i][j] - '0' - 1); } } DFS(board,0); }}
换了位运算之后，常数减小了一部分，效率有很明显的提高。
总结
本题其实就是简单的暴力枚举策略：将所有可能的情况都枚举一遍以获得最优解。当遇到问题规模比较小的情况，这样子的策略其实是最容易想到的，而且在较小的问题规模上，这个策略的实际运行效率也非常不错。
这就是最明显的能体现出计算机的计算速度的策略，而这时候，位运算优化等等的细节能够提供的帮助就非常大了。但是到了问题规模更大的情况，我们就需要另寻他法了。
力扣链接：https://leetcode.cn/problems/sudoku-solver/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。
一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 750 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！
037.解数独
题意
编写一个程序，通过填充空格来解决数独问题。
数独的解法需遵循如下规则：
-
数字 1-9 在每一行只能出现一次。
-
数字 1-9 在每一列只能出现一次。
-
数字 1-9 在每一个以粗实线分隔的 3x3 九宫格内只能出现一次。
数独的部分空格内已填入了数字，空白格用 '.' 表示。
难度
困难
示例
输入：board = [
["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
唯一有效的解决方案如下所示：
分析
解数独，这个问题通常会在一些趣味杂志或者团建活动上碰到过，朴素的解法往往是去猜一个数字，然后判断符不符合条件，符合就去猜下一个数字。
计算机在面对这类问题的时候，因为处理速度比人脑快得多多多多，所以可以挨个枚举每个 “坑” 应该填写的数字，然后加以检验，就可以得出答案了。
题目要求保证唯一解，所以我们需要记录每一个 . 的位置，然后逐个枚举合法的数字，确定与当前的每一行、每一列、每个九宫格都没有冲突，如果没有冲突，就去枚举下一个，如果有冲突的话，就表示之前填写的数字有问题，直接回溯到之前的状态，更换新的数字。
但是，要记住一点，就是我们回溯的时候……
必须要把状态恢复到之前的样子！
必须要把状态恢复到之前的样子！
必须要把状态恢复到之前的样子！
因为之后的操作，跟上次失败的操作，在逻辑关系上，是并行的，如果没有回溯到失败之前的状态，直接向下执行，那么之前失败的状态就会对现在的判断造成影响，逻辑关系就变成了上次失败之后的。
基于上述的思路，我们能够写出如下的代码：
class Solution {
private boolean[][] inCol = new boolean[9][9]; private boolean[][][] inBlock = new boolean[3][3][9]; private List<int[]> list = new ArrayList<int[]>(); private boolean victory = false; private void DFS(char[][] board,int step){ if(step == list.size()){ victory = true; return ; } int posX = list.get(step)[0],posY = list.get(step)[1]; for(int number = 0;number < 9;number++){//枚举1-9看哪个填入是符合现在的状态的 if(inRow[posX][number] || inCol[posY][number] || inBlock[posX / 3][posY / 3][number]) continue; //如果填这个数不会造成冲突 inRow[posX][number] = true; inCol[posY][number] = true; inBlock[posX / 3][posY / 3][number] = true; //打上标记，防止之后重复填写这个数字 board[posX][posY] = (char)(number + '0' + 1); DFS(board,step + 1);//继续向下枚举 if(victory) return; //如果不成功的话 状态要回溯回去 避免造成影响 board[posX][posY] = '.'; inRow[posX][number] = false; inCol[posY][number] = false; inBlock[posX / 3][posY / 3][number] = false; } } public void solveSudoku(char[][] board) { for(int i = 0;i < 9;i++) for(int j = 0;j < 9;j++){ if(board[i][j] == '.')//记录还没有填的位置 list.add(new int[]{i,j}); else{ inRow[i][board[i][j] - '0' - 1] = true; inCol[j][board[i][j] - '0' - 1] = true; inBlock[i / 3][j / 3][board[i][j] - '0' - 1] = true; } } DFS(board,0); }}
执行效果也算不错。
但是我们能不能对一些小的细节进行优化呢？百尺竿头更进一步嘛。
在上面的代码中，我们是用两个二维数组和一个三维数组来记录每行每列每个九宫格（3X3） 数字的出现与否 的。
但是，它们最多一共只会有 9 个数字出现（1-9 嘛），所以我们其实可以用一个九位的二进制来表示这个行/列/九宫格里面数字的出现情况。这样可以带来一点的常数优化。
在枚举的时候，如果需要将对应位置的0变为1的话，只需要inRow[x] |= (1 << number)，这样子就可以把inRow[x]的第number位二进制位变为1了。
反过来，回溯的时候我们要怎么样，才能将1变为0而不影响到其他位置呢？
有两种方式，一个是直接异或也就是inRow[x] ^= (1 << number)，因为我们已经知道number位是1，再异或一次，就变成0了。
另外一种方式是把1 << number整体取反inRow[x] &= ~(1 << number)，这样子只有number位是0，就可以使number位变成0了。
代码相较于之前的也不用改太多，就状态的记录那部分稍微修改一下即可：
class Solution {
private int[] inCol = new int[9]; private int[][] inBlock = new int[3][3]; private List<int[]> list = new ArrayList<int[]>(); private boolean victory = false; private void DFS(char[][] board,int step){ if(step == list.size()){ victory = true; return ; } int posX = list.get(step)[0],posY = list.get(step)[1]; for(int number = 0;number < 9;number++){ if(((inRow[posX] & (1 << number)) != 0) || ((inCol[posY] & (1 << number)) != 0) || ((inBlock[posX / 3][posY / 3] & (1 << number)) != 0)) continue; //如果填这个数不会造成冲突 inRow[posX] |= (1 << number);//换为二进制进行判断 inCol[posY] |= (1 << number); inBlock[posX / 3][posY / 3] |= (1 << number); board[posX][posY] = (char)(number + '0' + 1); DFS(board,step + 1); if(victory) return; //如果不成功的话 状态要回溯回去 board[posX][posY] = '.'; inRow[posX] &= ~(1 << number); inCol[posY] &= ~(1 << number); inBlock[posX / 3][posY / 3] &= ~(1 << number); } } public void solveSudoku(char[][] board) { for(int i = 0;i < 9;i++) for(int j = 0;j < 9;j++){ if(board[i][j] == '.') list.add(new int[]{i,j}); else{ inRow[i] |= 1 << (board[i][j] - '0' - 1); inCol[j] |= 1 << (board[i][j] - '0' - 1); inBlock[i / 3][j / 3] |= 1 << (board[i][j] - '0' - 1); } } DFS(board,0); }}
换了位运算之后，常数减小了一部分，效率有很明显的提高。
总结
本题其实就是简单的暴力枚举策略：将所有可能的情况都枚举一遍以获得最优解。当遇到问题规模比较小的情况，这样子的策略其实是最容易想到的，而且在较小的问题规模上，这个策略的实际运行效率也非常不错。
这就是最明显的能体现出计算机的计算速度的策略，而这时候，位运算优化等等的细节能够提供的帮助就非常大了。但是到了问题规模更大的情况，我们就需要另寻他法了。
力扣链接：https://leetcode.cn/problems/sudoku-solver/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。
一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 750 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！
知识星球
扫码加入星球
查看更多优质内容
https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412