Open youngyangyang04 opened 1 month ago
private boolean backtracking(char[][] board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
for (char c = '1'; c <= '9'; c++) {
if (isValid(i, j, c, board)) {
board[i][j] = c; // 处理
if (backtracking(board)) return true; // 递归
board[i][j] = '.'; // 回溯
}
}
return false;
}
}
}
return true;
}
// 深度1: 第一个 '.': i = 0, j = 2, board = [["5","3",".",".","7",".",".",".","."],...]
c = '1':board[0][2] = '1',满足 isValid == true,递归返回 false(后续无解), 回溯。
c = '2':board[0][2] = '2',满足 isValid == true,递归返回 false(后续无解), 回溯。
c = '3':board[0][2] = '3',不满足 isValid == true(同行), 继续遍历(剪枝)。
c = '4':board[0][2] = '4',满足 isValid == true,递归返回 true(后续有解), 返回 true。
// 深度2: 例: 第二个 '.': i = 0, j = 3, board = [["5","3","4",".","7",".",".",".","."],...]
c = '1':board[0][3] = '1',不满足 isValid == true(同列), 继续遍历(剪枝)。...
c = '6':board[0][3] = '6',满足 isValid == true,递归返回 true(后续有解), 返回 true。
// 深度3: 例: 第三个 '.': i = 0, j = 5, board = [["5","3","4","6","7",".",".",".","."],...]
c = '1':board[0][5] = '1',不满足 isValid == true(同框), 继续遍历(剪枝)。...
c = '8':board[0][5] = '8',满足 isValid == true,递归返回 true(后续有解), 返回 true。
// 深度n: 以此类推
https://www.programmercarl.com/0037.%E8%A7%A3%E6%95%B0%E7%8B%AC.html