N 皇后
- 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例1：
输入：n = 4
输出：[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
解题思路
- 1、使用回溯算法来生成所有不同的N皇后问题的解决方案。
- 2、在每一行中，依次尝试放置皇后，并检查是否符合规则，即不在同一行、同一列、同一对角线上。
- 3、使用递归回溯的方法，尝试放置皇后，并继续向下一行递归放置。
- 4、如果当前行放置皇后后，无法找到合适的位置，则回溯到上一行重新尝试。
解题步骤
1、初始化棋盘： 创建一个大小为 n×n 的棋盘，用二维数组表示，初始时所有位置都为空（用 ‘.’ 表示）。
2、回溯搜索： 从第一行开始逐行放置皇后，在放置每一行的皇后时， 都需要检查当前位置是否合法。
如果合法，则将皇后放置在该位置，并继续递归地放置下一行的皇后；
如果不合法，则尝试下一个位置。在递归的过程中，需要记录已经放置的皇后的位置，以便进行回溯。3、递归结束条件： 当放置了所有的皇后时，即递归到达了棋盘的最后一行，
此时找到了一个可行解，将该解保存下来。然后回溯到上一行，尝试放置下一个皇后，继续搜索其他解。4、合法性检查： 在放置皇后时，需要检查当前位置是否与已放置的皇后冲突。
具体地，需要检查当前位置的同一列、同一行、左上对角线和右上对角线是否已经存在皇后。 如果存在冲突，则当前位置不合法，需要尝试下一个位置。5、保存解： 当找到一个合法的解时，将该解保存到结果集中，
并继续搜索其他可能的解。6、回溯： 在搜索过程中，如果发现当前位置无法放置皇后，或者已经找到了一个解，
则需要回溯到上一步，撤销当前操作，尝试其他可能的选择。7、返回结果： 当搜索结束时，返回所有找到的合法解。
java实现
public class NQueens {
public List<List<String>> solveNQueens(int n) {
//保存结果集
List<List<String>> result = new ArrayList<>();
//初始化棋盘
char[][] board = new char[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(board[i], '.');
}
//放置皇后
backtrack(result, board, 0);
return result;
}
//回溯
private void backtrack(List<List<String>> result, char[][] board, int row) {
if (row == board.length) {
result.add(constructSolution(board));
return;
}
for (int col = 0; col < board.length; col++) {
///判断放置位置是否符合规则
if (isValid(board, row, col)) {
board[row][col] = 'Q';
backtrack(result, 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;
//获取行的差值，用于下面左上方、右上方对角线对应的位置
//对于[row][col]因i= row-d 转换成[i+d,col]，所以[i,col-d]一定在其左上方
// 随着i从0到row变化，d的值也在改变，d=1，board[i][col - d]就是[row][col]左上方的格子，
// d=2，board[i][col - d]就是[row][col]左上方的左上方的格子
int d = row - i;
// 检查左上方对角线是否有皇后冲突
if (col - d >= 0 && board[i][col - d] == 'Q') return false;
// 检查右上方对角线是否有皇后冲突
if (col + d < board.length && board[i][col + d] == 'Q') return false;
}
return true;
}
//记录解决方案
private List<String> constructSolution(char[][] board) {
List<String> solution = new ArrayList<>();
for (char[] row : board) {
solution.add(String.valueOf(row));
}
return solution;
}
public static void main(String[] args) {
NQueens nQueens = new NQueens();
List<List<String>> solutions = nQueens.solveNQueens(4);
for (List<String> solution : solutions) {
for (String row : solution) {
System.out.println(row);
}
System.out.println();
}
}
}
时间空间复杂度
时间复杂度：O(N!)，其中N是棋盘的大小。因为每一行都有N种放置皇后的可能性，总共有N行。
空间复杂度：O(N^2)，存储所有可能的棋盘状态。