解数独
题目描述：
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例 1：
输入：board = [["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"]] 解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
提示：
board.length == 9board[i].length == 9board[i][j]是一位数字或者'.'- 题目数据 保证 输入数独仅有一个解
思路分析：
推荐学习视频：回溯算法二维递归？解数独不过如此！| LeetCode：37. 解数独_哔哩哔哩_bilibili
棋盘搜索问题可以使用回溯法暴力搜索，例如数独、N皇后。对于本题，我们需要对每一个非空格进行判定：
以数独的每列每行为循环，对每一个填入的数字进行列、行、九宫格的检查。并对发生冲突的结果进行回溯。
回溯三要素
- 递归函数以及参数
递归函数的返回值需要是bool类型，因为在找到符合条件的值时，需要把一系列回溯上的值进行保存。
- 递归终止条件
本题不需要终止条件，因为当一行一列确定下来了，尝试了9个数都不行的话，说明这个棋盘找不到解决数独问题的解，直接返回false。
//用于填写数独的函数
private boolean backtracking(char[][] board){
//遍历二维数组，先列后行
for(int i = 0; i < 9; i++){
for(int j = 0; j < 9; j++){
//跳过原始数字
if(board[i][j] != '.')
continue;
//从1到9依次填入，用is_Valid判断
for(char k = '1'; k <='9'; k++){
if(is_Valid(i, j, k, board)){
board[i][j] = k;
// 进入先一层递归，如果找到合适一组立刻返回
if(backtracking(board))
return true;
//数独出现矛盾，回溯，将k值清零
board[i][j] = '.';
}
}
return false;
}
}
return true;
}- 递归单层搜索逻辑
在树形图中可以看出我们需要的是两个for循环嵌套着的。递归一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放9个数字的可能性。
//判断填入的数值是否合格
private boolean is_Valid(int row, int col, char val, char[][] board){
// 同行是否重复或 同列是否重复
for(int i = 0; i < 9; i++){
if(board[row][i] == val || board[i][col] == val){
return false;
}
}
// 9宫格里是否重复
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for(int i = startRow; i < startRow + 3; i++){
for(int j = startCol; j < startCol + 3; j++){
if(board[i][j] == val)
return false;
}
}
return true;
}
}最后测试棋盘数字是否正确，判断棋盘是否合法有如下三个维度：
- 同行是否重复
- 同列是否重复
- 9宫格里是否重复
代码实现注解：
class Solution {
public void solveSudoku(char[][] board) {
backtracking(board);
}
//用于填写数独的函数
private boolean backtracking(char[][] board){
//遍历二维数组，先列后行
for(int i = 0; i < 9; i++){
for(int j = 0; j < 9; j++){
//跳过原始数字
if(board[i][j] != '.')
continue;
//从1到9依次填入，用is_Valid判断
for(char k = '1'; k <='9'; k++){
if(is_Valid(i, j, k, board)){
board[i][j] = k;
// 进入先一层递归，如果找到合适一组立刻返回
if(backtracking(board))
return true;
//数独出现矛盾，回溯，将k值清零
board[i][j] = '.';
}
}
return false;
}
}
return true;
}
//判断填入的数值是否合格
private boolean is_Valid(int row, int col, char val, char[][] board){
// 同行是否重复或 同列是否重复
for(int i = 0; i < 9; i++){
if(board[row][i] == val || board[i][col] == val){
return false;
}
}
// 9宫格里是否重复
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for(int i = startRow; i < startRow + 3; i++){
for(int j = startCol; j < startCol + 3; j++){
if(board[i][j] == val)
return false;
}
}
return true;
}
}
