回溯算法:N皇后问题
N皇后问题是一个经典的回溯算法应用问题，要求在一个N×N的棋盘上放置N个皇后，使得它们互不攻击。即任何两个皇后都不能位于同一行、同一列或同一对角线上。这个问题可以通过回溯算法来解决，下面详细讲解这个问题的解法。
解题思路
- 逐行放置：一种有效的解决方案是逐行放置皇后，这样可以保证每行只有一个皇后。
- 检查冲突：放置每个皇后时，需要检查当前放置的皇后是否与已放置的皇后冲突（即检查列和对角线）。
- 回溯：如果当前行没有合法的列可以放置皇后，或者放置后无法在后续行找到合法放置位置，则需要回溯到上一行，改变皇后的位置继续尝试。
- 找到解后返回：当所有N个皇后都放置完毕时，记录下当前的棋盘布局作为一个解，然后回溯尝试其他可能的布局。
关键步骤
- 递归函数定义：定义一个递归函数，参数至少包含当前处理的行号和棋盘状态。
- 终止条件：当行号等于N时，说明已经成功放置了N个皇后，记录下当前解。
- 遍历当前行的每一列：尝试在当前行的每一列放置皇后。
- 检查是否可以放置皇后：对于当前选定的列，检查放置皇后后是否会与之前放置的皇后发生冲突。
- 递归尝试放置下一行的皇后：如果当前行的皇后放置成功，递归调用函数尝试放置下一行的皇后。
- 回溯：如果放置当前行的皇后后无法找到合法的解决方案，则需要撤销当前行的皇后放置，尝试当前行的下一列。
代码实现
代码实现中已经包含了详细的注释，解释了每一步的作用。关键点在于如何检查皇后之间是否互相攻击，这可以通过检查同一列和两个对角线来实现。对于对角线的检查，有两种对角线：一种是行号与列号之差相等的对角线，另一种是行号与列号之和相等的对角线。如果两个皇后位于同一对角线上，它们的行号与列号的差或和将相等。
通过回溯算法的深度优先搜索，我们可以找到所有可能的解决方案。每次尝试放置皇后时，如果发现当前选择导致没有合法的解决方案，就回溯到上一步，尝试其他可能的放置方式。这个过程重复进行，直到找到所有合法的解决方案或遍历完所有可能的放置方式。
import java.util.ArrayList;
import java.util.List;
public class NQueens {
// 解集，存放所有可能的解
private List<List<String>> solutions = new ArrayList<>();
// 入口方法，n表示棋盘的大小
public List<List<String>> solveNQueens(int n) {
// 初始化棋盘，用'.'表示空，'Q'表示皇后
char[][] board = new char[n][n];
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
board[i][j] = '.';
}
}
// 从第0行开始尝试放置皇后
backtrack(board, 0);
return solutions;
}
// 回溯方法，row表示当前操作的行
private void backtrack(char[][] board, int row) {
// 如果当前行超过了棋盘的行数，说明找到了一种解法
if (row == board.length) {
solutions.add(construct(board)); // 将当前解法添加到解集中
return;
}
// 尝试在当前行的每一列中放置皇后
for (int col = 0; col < board.length; col++) {
// 检查在[row, col]位置放置皇后是否合法
if (isValid(board, row, col)) {
board[row][col] = 'Q'; // 放置皇后
backtrack(board, row + 1); // 移动到下一行
board[row][col] = '.'; // 回溯，撤销当前行的皇后
}
}
}
// 检查放置皇后是否合法
private boolean isValid(char[][] board, int row, int col) {
// 检查当前列是否有皇后
for (int i = 0; i < row; i++) {
if (board[i][col] == 'Q') {
return false;
}
}
// 检查左上对角线是否有皇后
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') {
return false;
}
}
// 检查右上对角线是否有皇后
for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
if (board[i][j] == 'Q') {
return false;
}
}
return true;
}
// 构建解法
private List<String> construct(char[][] board) {
List<String> solution = new ArrayList<>();
for (int i = 0; i < board.length; i++) {
String row = new String(board[i]);
solution.add(row);
}
return solution;
}
public static void main(String[] args) {
NQueens solution = new NQueens();
List<List<String>> solutions = solution.solveNQueens(4); // 解决4皇后问题
for (List<String> sol : solutions) {
for (String row : sol) {
System.out.println(row);
}
System.out.println();
}
}
}
在这段代码中，solveNQueens方法初始化一个N×N的棋盘，并从第0行开始递归尝试放置皇后。backtrack方法负责在每一行尝试放置皇后，并检查是否合法。如果在当前行找到合法位置放置皇后，就递归调用自己尝试在下一行放置皇后。如果某一行无法放置皇后，则回溯到上一行，改变皇后的位置，再次尝试。
isValid方法用于检查在棋盘的[row, col]位置放置皇后是否会导致攻击现象，即检查当前列和两个对角线是否已经有皇后存在。
回溯算法的关键在于尝试并在遇到无法继续的情况下撤销（回溯）之前的尝试，寻找新的尝试路径。这样，通过枚举所有可能的情况，最终找到所有的解决方案。