题目描述
请编写一个程序，给数独中剩余的空格填写上数字，空格用字符'.'来表示，假设给定的数独只有唯一的解法。
示例1：
输入：
[[.,.,9,7,4,8,.,.,.],[7,.,.,.,.,.,.,.,.],[.,2,.,1,.,9,.,.,.],[.,.,7,.,.,.,2,4,.],[.,6,4,.,1,.,5,9,.],[.,9,8,.,.,.,3,.,.],[.,.,.,8,.,3,.,2,.],[.,.,.,.,.,.,.,.,6],[.,.,.,2,7,5,9,.,.]]
返回值：
[[5,1,9,7,4,8,6,3,2],[7,8,3,6,5,2,4,1,9],[4,2,6,1,3,9,8,7,5],[3,5,7,9,8,6,2,4,1],[2,6,4,3,1,7,5,9,8],[1,9,8,5,2,4,3,6,7],[9,7,5,8,6,3,1,2,4],[8,3,2,4,9,1,7,5,6],[6,4,1,2,7,5,9,8,3]]
题目分析
算法获取数独的结果，计算过程就是将空格中的数字进行1~9的枚举，当该数字满足横向、列向、块内与已出现的数字不重复，则进行下一个空格的数字枚举，直到所有的空格都选择了满足条件的数字，数独完成，如图示例1：
解题思路
方法1：dfs递归回溯，暴力法判断
dfs递归回溯，对数组进行遍历，碰到空格就进行1~9的数字选择，同时也要对数字进行遍历判断是否与已经出现的数字重复，判断的方法可以直接采用暴力遍历该位置的同行、列、块的所有数据，dfs的过程如下：
dfs(){
// 顺序遍历数组，找到空格的位置x,y
// 对空格位置进行1~9的选择
for(int i=1;i<=9;i++){
// 判断选择的数字是否满足条件
// 满足 dfs下一个空格，直到所有空格都被填上数字
// 不满足跳过
}
}
// 判断数字是否符合条件
isValid(x, y){
// 循环该行（x确定）的所有数字，看是否重复
for(int i=0;i<9;i++) board[x][i];
// 循环该列（y确定）的所有数字，看是否重复
for(int i=0;i<9;i++) board[i][y];
// 循环该块的所有数字，看是否重复（这里对块进行的编号，从左到右，从上到下）
for(int i=0;i<9;i++) board[x/3*3+i/3][y/3*3+i%3];
}
方法2：dfs递归回溯，使用set判断
使用set记录每行每列每个块已经出现过的数字，可以加快判断数字是否满足条件的速度。因为有些数字已经遍历过，但每次判断都要重新遍历一遍，会增加很多时间，通过使用set来存储已知的数字，在判断数字上由原来的O(n)优化到O(1)（hashset）；
具体需要使用3n个set来存储n行，n列，n个块对应的数字。
代码实现
方法1：dfs递归回溯，暴力法判断
import java.util.*;
public class Solution {
boolean flag = false;
public void solveSudoku(char[][] board) {
// 进行递归回溯
dfs(board, 0, 0);
}
public void dfs(char[][] board, int i, int j){
if(i == board.length){
// 已经遍历所有的数，说明已经获得结果
flag = true;
return ;
}
// 找到第i行中要填的数
while(j<board.length && board[i][j] != '.'){
j++;
}
if(j == board.length){
// 遍历完一行数，遍历下一行
dfs(board, i+1, 0);
}
if(i<board.length && j<board.length){
for(char x='1';x<='9';x++){
// 不符合数独条件
if(!isValid(board, i, j, x)) continue;
// 进行选择
board[i][j] = x;
dfs(board, i, j+1);
// 如果已经完成了选择，可以不用撤销选择，也不用再遍历后面的情况
if(flag) break;
// 撤销选择
board[i][j] = '.';
}
}
}
public boolean isValid(char[][] board, int x, int y, char ch){
for(int i=0;i<board.length;i++){
// 判断以x,y为坐标的行、列、块中是否存在字符ch
if(board[x][i] == ch) return false;
if(board[i][y] == ch) return false;
if(board[x/3*3+i/3][y/3*3+i%3] == ch) return false;
}
return true;
}
}
时间复杂度：最差为，n是数独的数组长度（题目中只设定为9），m是空格的数量加1，对每一个空格都需要列举n种情况，但实际上不会对所有情况进行穷举，只要某一种情况下能够满足所有数字条件，就会直接返回结果，因为使用了暴力判断，所以每次数字的遍历都需要n的时间来判断，所以额外加一个n的乘积；
空间复杂度：最差为，n是数独的数组长度,，最多需要的递归空间。
方法2：dfs递归回溯，使用set判断
import java.util.*;
public class Solution {
// 记录每行、每列、每个3X3块中已经出现的数字
List<Set<Character>> row = new ArrayList<>();
List<Set<Character>> col = new ArrayList<>();
List<Set<Character>> block = new ArrayList<>();
boolean flag = false;
public void solveSudoku(char[][] board) {
for(int i=0;i<board.length;i++){
// 创建对应的set
row.add(new HashSet<Character>());
col.add(new HashSet<Character>());
block.add(new HashSet<Character>());
}
for(int i=0;i<board.length;i++){
for(int j=0;j<board.length;j++){
if(board[i][j] != '.'){
// 先将已知的数字填入对应的set中
row.get(i).add(board[i][j]);
col.get(j).add(board[i][j]);
block.get(i/3*3+j/3).add(board[i][j]);
}
}
}
dfs(board, 0, 0);
}
public void dfs(char[][] board, int i, int j){
if(i == board.length){
// 已经遍历所有的数
flag = true;
return ;
}
// 找到第i行中要填的数（空格）
while(i<board.length && j<board.length && board[i][j] != '.'){
j++;
}
if(j == board.length){
// 遍历完一行数，遍历下一行
dfs(board, i+1, 0);
}
for(char x='1';x<='9';x++){
int bi = i/3*3+j/3;
// 符合数独条件
if(!row.get(i).contains(x) && !col.get(j).contains(x) && !block.get(bi).contains(x)){
// 进行选择
board[i][j] = x;
row.get(i).add(board[i][j]);
col.get(j).add(board[i][j]);
block.get(bi).add(board[i][j]);
dfs(board, i, j+1);
if(flag) break;
// 撤销选择
row.get(i).remove(board[i][j]);
col.get(j).remove(board[i][j]);
block.get(bi).remove(board[i][j]);
board[i][j] = '.';
}
}
}
}
时间复杂度：最差为，n是数独的数组长度（题目中只设定为9），m是空格的数量，对每一个空格都需要列举n种情况，但实际上不会对所有情况进行穷举，只要某一种情况下能够满足所有数字条件，就会直接返回结果，因为使用了set来加快数字的判断，所以时间上会比暴力法判断快；
空间复杂度：，n是数独的数组长度,，在遍历的过程中使用了存储所有数字的set(row, col, block)，存储的数据大小为，同时最多需要的递归空间。
京公网安备 11010502036488号