题目描述
编写一个程序,通过填充空格来解决数独问题。
数独的解法需 遵循如下规则:
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)
数独部分空格内已填入了数字,空白格用 ‘.’ 表示。
样例
输入:
[
["5","3",".",".","7",".",".",".","."],
["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"]
]
算法1
(DFS + 回溯) $O(n^2)$
题目是要求每个空格都是需要对齐进行填充,当然一开始给到的board 数组已经有一些位置是给好数的。空余的位置填上数的要求:同一行不能出现相同的数,同一列不能出现相同的数,同一个3 x 3 的矩阵中也不能出现相同的数。
思路:
1.因为基本是要给每个空格都要进行填充数字,填充的顺序我们按照先填写完一列,再到下一行填写。所以我们是从左到右一个空格一个空格地进行填写。此时就形成一个递归终止条件: 当col 递归到矩阵的右边界: board[0].length 时,就要到下一行的最左边重新开始递归: row ++ ,y = 0.
此时又会有另一个终止条件:如果填充数据顺利的话,当row == board.length 的时候,递归就终止。而且因为题目给好的board 数组中,有一部分是已经填好数的,所以当遇到填好的数时,往下一列继续填充即可。
2.题目中要求:同一行不能出现相同的数,同一列不能出现相同的数,同一个3 x 3 的矩阵中也不能出现相同的数。此时我们就应该像‘N 皇后’ 一样,用3 个容器分别记录对应的状态:boolean[][] row = new boolean[9][9] 一维数组代表第几行,二维数组代表该行存在的数字(因为数组是从0 开始的,而二维数组的长度为9,所以从board 数组获取到对应的数或者在加入对应的数到board 数组时都要进行偏移量的计算)。 记录col 的数组也是如此。值得一提的是记录同一个3 x 3 矩阵的数:boolean[][][] box = new boolean [3][3][9] 因为题目给到的board 是一个矩阵,其中有3 x 3 个小矩阵组成,我们遍历二维矩阵只有row,col 两个变量,如何利用这两个变量来定位是同一个矩阵呢? 因为小矩阵也是3 x 3大小的,board 的长是小矩阵长的3 倍关系,board 的宽是小矩阵的3 倍关系,那row 和col 同时缩小3 倍,得到的位置就是board 的长和宽同时缩小3 倍后的位置,而这个位置就是一个矩阵的位置,那我们就可以利用这个关系来定位是否是同一个矩阵。所以box 的前二维代表着某一个矩阵,第三维代表该矩阵中有的数字。
时间复杂度
参考文献
https://www.bilibili.com/video/BV1M4411Q7td
Java 代码
发现一个奇怪的事情,当代码以下面形式运行时,会报栈溢出异常:
public void solveSudoku(char[][] board) {
if(board.length == 0) return;
boolean[][] row = new boolean[9][9];
boolean[][] col = new boolean[9][9];
boolean[][][] box = new boolean[3][3][9];
//找到原本board 数组中已经用到的数字,并在row,col,box 中标记它们,说明它们已经存在了
//扫描board 数组
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
if(board[i][j] != '.'){
char c = board[i][j];
int num = c - '1';
//true:代表这个数字已经被使用过
row[i][num] = col[j][num] = box[i/3][j/3][num] = true;
}
}
}
dfs(0,0,board,row,col,box);
}
boolean dfs(int x,int y,char[][] board,boolean[][] row,boolean[][] col,boolean[][][] box){
//当y 达到了最右边的边界时
if(y == board[0].length) x ++;y = 0; //去到下一行最左边重新开始
//x,y 都从0 开始,边界是数组的长度,如果能到达这个位置说明之前的位置都已经放好数了
if(x == board.length) return true;
//如果说当前空格是一个数字的话,那就是题目一开始就给好,直接去到下一个空格进行填数独
if(board[x][y] != '.') return dfs(x,y+1,board,row,col,box);
for(int i = 0; i < 9; i++){
//看看当前位置能放1~9 之间的哪个数
if(!row[x][i] && !col[y][i] && !box[x/3][y/3][i]){
board[x][y] = (char)('1' + i);
row[x][i] = col[y][i] = box[x/3][y/3][i] = true;
//去到下一个位置
if(dfs(x,y+1,board,row,col,box)) return true;
//如果上面的dfs(x,y+1,board) 不能够return true,那么就说明当前空格中不能存放当前i 值,所以要进行回溯
board[x][y] = '.';
row[x][i] = col[y][i] = box[x/3][y/3][i] = false;
}
}
//能从上面的for 循环中出来,执行到这里说明1`9 都不能放入到后面的空格中,直接return false
return false;
}
当把dfs(…) 中的:
if(y == board[0].length) x ++;y = 0;
修改成:
if(y == board[0].length){
x ++;y = 0;
}
只有上面这样写才不会报错,具体原因希望能有大佬能指定一下。
修改后代码:
class Solution {
public void solveSudoku(char[][] board) {
if(board.length == 0) return;
boolean[][] row = new boolean[9][9];
boolean[][] col = new boolean[9][9];
boolean[][][] box = new boolean[3][3][9];
//找到原本board 数组中已经用到的数字,并在row,col,box 中标记它们,说明它们已经存在了
//扫描board 数组
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
if(board[i][j] != '.'){
char c = board[i][j];
int num = c - '1';
//true:代表这个数字已经被使用过
row[i][num] = col[j][num] = box[i/3][j/3][num] = true;
}
}
}
dfs(0,0,board,row,col,box);
}
boolean dfs(int x,int y,char[][] board,boolean[][] row,boolean[][] col,boolean[][][] box){
//当y 达到了最右边的边界时
if(y == board[0].length){
x ++;y = 0; //去到下一行最左边重新开始
}
//x,y 都从0 开始,边界是数组的长度,如果能到达这个位置说明之前的位置都已经放好数了
if(x == board.length) return true;
//如果说当前空格是一个数字的话,那就是题目一开始就给好,直接去到下一个空格进行填数独
if(board[x][y] != '.') return dfs(x,y+1,board,row,col,box);
for(int i = 0; i < 9; i++){
//看看当前位置能放1~9 之间的哪个数
if(!row[x][i] && !col[y][i] && !box[x/3][y/3][i]){
board[x][y] = (char)('1' + i);
row[x][i] = col[y][i] = box[x/3][y/3][i] = true;
//去到下一个位置
if(dfs(x,y+1,board,row,col,box)) return true;
//如果上面的dfs(x,y+1,board) 不能够return true,那么就说明当前空格中不能存放当前i 值,所以要进行回溯
board[x][y] = '.';
row[x][i] = col[y][i] = box[x/3][y/3][i] = false;
}
}
//能从上面的for 循环中出来,执行到这里说明1`9 都不能放入到后面的空格中,直接return false
return false;
}
}
x++;
和y=0;
是两个语句,要用大括号框起来。也可以换成空格隔开,改成x++,y=0;
Java 中x++,y=0 会报错,所以只能用大括号括起来了。谢谢评论。
哦,不好意思,我专攻C++
哈哈了解的