题目：https://leetcode.cn/problems/sudoku-solver/
代码：
class Solution {
public void solveSudoku(char[][] board) {
// 三个布尔数组 表明 行, 列, 还有 3*3 的方格的数字是否被使用过
boolean[][] rowUsed = new boolean[9][10];
boolean[][] colUsed = new boolean[9][10];
boolean[][][] boxUsed = new boolean[3][3][10];
// 初始化数据
for (int row = 0; row < board.length; row++) {
for (int col = 0; col < board[row].length; col++) {
// char类型转成int数字
int num = board[row][col] - '0';
if (1 <= num && num <= 9) {
//是数字，标记已使用
rowUsed[row][num] = true;
colUsed[col][num] = true;
boxUsed[row / 3][col / 3][num] = true;
}
}
}
// 从(0,0)的位置开始递归尝试填充求解
if (trySolveSudoku(board, rowUsed, colUsed, boxUsed, 0, 0)) {
System.out.println("成功求解");
} else {
System.out.println("未找到有效解");
}
}
/**
* 尝试从(row,col)位置开始求解
*
* @param board
* @param rowUsed
* @param colUsed
* @param boxUsed
* @param row
* @param col
* @return
*/
private boolean trySolveSudoku(char[][] board, boolean[][] rowUsed, boolean[][] colUsed, boolean[][][] boxUsed, int row, int col) {
// 边界校验, 如果row和col都大于边界，证明求解完成，且有有效解，返回true
if (col == board[0].length) {
//跳下一行
col = 0;
row++;
if (row == board.length) {
return true;
}
}
// 该位置非空白，不需要求解，递归下一个位置
if (board[row][col] != '.') {
return trySolveSudoku(board, rowUsed, colUsed, boxUsed, row, col + 1);
}
// 尝试填充1~9进行求解
for (int num = 1; num <= 9; num++) {
//数字在 行、列、方格 中是否已经被使用（true表示被使用，非有效解，尝试下一个数字num+1）
boolean used = (rowUsed[row][num] || colUsed[col][num] || boxUsed[row / 3][col / 3][num]);
if (used) {
continue;
}
//未被使用，标记该数字被使用，且在棋盘中填充该数字
rowUsed[row][num] = true;
colUsed[col][num] = true;
boxUsed[row / 3][col / 3][num] = true;
board[row][col] = (char) ('0' + num);
//尝试下一个位置的解
if (trySolveSudoku(board, rowUsed, colUsed, boxUsed, row, col + 1)) {
//成功求解代表本次位置填写的数字num有有效解，直接返回true
return true;
}
//代表本地位置填写的数字num无有效解，需要回滚本次的变动并尝试下一个数字num+1
rowUsed[row][num] = false;
colUsed[col][num] = false;
boxUsed[row / 3][col / 3][num] = false;
board[row][col] = '.';
}
//1~9都没有有效解，返回false
return false;
}
}
思路：
采用深度遍历暴力求解的办法，挨个在空白格尝试填充数字1~9，并判断本次填充是否有效；如果有效则继续填充下一个，直到全部填充完成；无效则尝试下一个数字，当1~9全部尝试后均无法找到有效解，则证明本题无解。
其中涉及到几个点：
1、遍历填充方式
以board[0][0]为原点建立一个坐标轴，从（0,0）开始向右遍历，超过边界之后换行从（1,0）开始继续遍历，直到（9,9）为止。
在遍历的过程中，碰到空白格（也就是’.’）才进行尝试1~9数字的填充。
2、如何快速判断填充的数字是否有效
在是否有效的判断，采用了3个布尔类型的数组来辅助。因为数独要求的是 行、列、以及3*3方格 中均不能出现重复数字，所以对应分别定义多维数组，用来标识第n行n列n个位置的方格，最后一维采用了个长度为10的数组（实际上长度为9就够用了，只是为了方便定义了10，其中0不使用），代表数字0-9，值为布尔类型，true代表在本条件下已经被使用了，false未被使用。
例如：rowUsed[0][9] 代表数字9已经在第0行被使用了。boxUsed[1][1][9] 代表数字9已经在中间那个大方格中被使用了。
3、有了1和2两点，剩下的就是递归以及结束条件的判断了，具体可以参考代码。
测试样例代码：
public static void main(String[] args) {
char[][] board = new char[9][9];
Solution solution = new Solution();
String str = "[[\"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\"]]";
JSONArray y = JSONUtil.parseArray(str);
for (int i = 0; i < y.size(); i++) {
JSONArray x = y.getJSONArray(i);
for (int j = 0; j < x.size(); j++) {
board[i][j] = x.getChar(j);
}
}
solution.solveSudoku(board);
System.out.println(Arrays.deepToString(board));
}
上述代码为求解之后，官方题解参考代码的理解。自己求解的思路差不多，只不过用到了栈以及判断数字是否有效的方法效率不够高，官方的求解办法更好。归档留存附上自己求解代码：
class Solution {
public void solveSudoku(char[][] board) {
//遍历棋盘，计算需要填充数字的坐标，并放入待填充坐标栈
Stack<Point> waitFill = new Stack<>();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
waitFill.push(new Point(i, j));
}
}
}
//递归遍历
this.tryFill(board, waitFill);
System.out.println(board);
}
private boolean tryFill(char[][] board, Stack<Point> waitFill) {
if (waitFill.isEmpty()) {
//没有需要填充的
return true;
}
Point point = waitFill.pop();
//1-9尝试当前坐标
for (int k = 1; k <= 9; k++) {
char c = (char) ('0' + k);
boolean valid = true;
//判断行
if (valid) {
for (int i = 0; i < 9; i++) {
if (board[point.i][i] == c) {
valid = false;
break;
}
}
}
//判断列
if (valid) {
for (int i = 0; i < 9; i++) {
if (board[i][point.j] == c) {
valid = false;
break;
}
}
}
//判断所在九宫格
//计算九宫格开始位置
if (valid) {
int ni = point.i / 3 * 3;
int nj = point.j / 3 * 3;
for (int i = ni; i < ni + 3; i++) {
for (int j = nj; j < nj + 3; j++) {
if (board[i][j] == c) {
valid = false;
break;
}
}
}
}
//判断结果
if (valid) {
board[point.i][point.j] = c;
boolean res = this.tryFill(board, waitFill);
if (res) {
return res;
}
}
}
board[point.i][point.j] = '.';
waitFill.push(point);
return false;
}
/**
* 坐标点
*/
class Point {
public int i;
public int j;
public Point(int i, int j) {
this.i = i;
this.j = j;
}
}
}
