一、题目
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。
示例 1：
![【LeetCode】解数独 [H]（深度优先遍历）](https://johngo-pic.oss-cn-beijing.aliyuncs.com/articles/20230809/7033463ef67714f475a1da0cb4d69bdd.png)
![【LeetCode】解数独 [H]（深度优先遍历）](https://www.johngo689.com/wp-content/themes/justnews/themer/assets/images/lazy.png)
输入：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”]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
![【LeetCode】解数独 [H]（深度优先遍历）](https://johngo-pic.oss-cn-beijing.aliyuncs.com/articles/20230809/ba2309de58dcbd60c6367f18441b89f3.png)
提示：
- board.length == 9
- board[i].length == 9
- board[i][j] 是一位数字或者 ‘.’
- 题目数据 保证 输入数独仅有一个解
二、代码
class Solution {
public void solveSudoku(char[][] board) {
// row[x][y]：y这个数在第x行是否出现过
boolean[][] row = new boolean[9][10];
// col[x][y]：y这个数在第x列是否出现过
boolean[][] col = new boolean[9][10];
// bucket[x][y]：y这个数在第x号宫格内是否出现过
boolean[][] bucket = new boolean[9][10];
// 初始化上面的三个数组
initMaps(board, row, col, bucket);
// 开始暴力递归尝试所有答案，只要找到了一种答案就返回
process(board, 0, 0, row, col, bucket);
}
// 初始化三个辅助数组
public void initMaps(char[][] board, boolean[][] row, boolean[][] col, boolean[][] bucket) {
// 开始遍历数独表，构造辅助数组
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] != '.') {
int num = board[i][j] - '0';
int bid = (i / 3) * 3 + (j / 3);
// 标记该数出现在的位置
row[i][num] = true;
col[j][num] = true;
bucket[bid][num] = true;
}
}
}
}
// DFS
// 当前来到(i,j)这个位置，
// 如果已经有数字，跳到下一个位置上
// 如果没有数字，尝试1~9，不能和row、col、bucket冲突
public boolean process(char[][] board, int i, int j, boolean[][] row, boolean[][] col, boolean[][] bucket) {
// 如果行数已经越界，说明已经尝试完了所有位置，返回true
if (i > 8) {
return true;
}
// 当离开(i，j)，应该去哪？(nexti, nextj)
// 要通过j是否走到结尾了来决定是不是i要向下走一行，j是否要重新回到0
int nexti = j < 8 ? i : i + 1;
int nextj = j < 8 ? j + 1 : 0;
// 如果当前位置不是空，就继续尝试下一个位置
if (board[i][j] != '.') {
return process(board, nexti, nextj, row, col, bucket);
// 当前位置是空，我们来尝试1~9
} else {
// 计算当前数字所在的3*3宫格的编号
int bid = (i / 3) * 3 + (j / 3);
// 在该位置尝试填写1~9，看能不能符合要求
for (int num = 1; num
三、解题思路
一个一个位置玩DFS暴力尝试。将所有可能填入的数字都尝试一边，找到符合条件的答案就返回。题目保证每一个输入只有唯一的一个解。
Original: https://blog.csdn.net/cy973071263/article/details/128428793
Author: 小七mod
Title: 【LeetCode】解数独 [H]（深度优先遍历）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/787569/
转载文章受原作者版权保护。转载请注明原作者出处！