Open youngyangyang04 opened 3 months ago
private void backtracking(int n, int row, char[][] board) {
if (row == n) {
result.add(construct(board));
return;
}
for (int col = 0; col < n; col++) {
if (isValid(row, col, board, n)) {
board[row][col] = 'Q'; // 1. 操作
backtracking(n, row + 1, board); // 2. 递归
board[row][col] = '.'; // 3. 回溯
}
}
}
// 深度1: backtracking(4,0,board), construct(board) = ["....","....","....","...."]
i = 0:board[0][0] = 'Q',递归 backtracking(4,1,board)。回溯。
i = 1:board[0][1] = 'Q',递归 backtracking(4,1,board)。回溯。
i = 2:board[0][2] = 'Q',递归 backtracking(4,1,board)。回溯。
i = 3:board[0][3] = 'Q',递归 backtracking(4,1,board)。回溯。
// 深度2: 例: backtracking(4,1,board), construct(board) = [".Q..","....","....","...."]
i = 0:不满足 isValid(1, 0, board, 4) == true(同列),继续遍历
i = 1:不满足 isValid(1, 1, board, 4) == true(斜线),继续遍历
i = 2:不满足 isValid(1, 2, board, 4) == true(斜线),继续遍历
i = 3:board[1][3] = 'Q',递归 backtracking(4,2,board)。回溯。
// 深度3: 例: backtracking(4,2,board), construct(board) = [".Q..","...Q","....","...."]
i = 0:board[2][0] = 'Q',递归 backtracking(4,3,board)。回溯。
i = 1:不满足 isValid(2, 1, board, 4) == true(同列),继续遍历
i = 2:不满足 isValid(2, 2, board, 4) == true(斜线),继续遍历
i = 3:不满足 isValid(2, 3, board, 4) == true(同列),继续遍历
// 深度4: 例: backtracking(4,3,board), construct(board) = [".Q..","...Q","Q...","...."]
i = 0:不满足 isValid(3, 0, board, 4) == true(同列),继续遍历
i = 1:不满足 isValid(3, 1, board, 4) == true(同列),继续遍历
i = 2:board[3][2] = 'Q',递归满足 row == 4,加入result。回溯。
i = 3:不满足 isValid(3, 3, board, 4) == true(同列),继续遍历
https://www.programmercarl.com/0051.N%E7%9A%87%E5%90%8E.html