八皇后
难度:
标签:
题目描述
Write an algorithm to print all ways of arranging n queens on an n x n chess board so that none of them share the same row, column, or diagonal. In this case, "diagonal" means all diagonals, not just the two that bisect the board.
Notes: This problem is a generalization of the original one in the book.
Example:
Input: 4 Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] Explanation: 4 queens has following two solutions [ [".Q..", // solution 1 "...Q", "Q...", "..Q."], ["..Q.", // solution 2 "Q...", "...Q", ".Q.."] ]
代码结果
运行时间: 34 ms, 内存: 16.4 MB
/*
* 题目思路：
* 1. 使用回溯算法解决N皇后问题。
* 2. 创建一个二维字符数组棋盘，并初始化为'.'。
* 3. 定义一个函数isSafe判断某个位置是否可以放置皇后。
* 4. 使用递归函数solveNQueens进行回溯搜索。
* 5. 如果找到解决方案，将其添加到结果集中。
* 6. 使用Java Streams处理结果。
*/
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
public class NQueensStream {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
char[][] board = new char[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = '.';
}
}
solve(res, board, 0, n);
return res;
}
private void solve(List<List<String>> res, char[][] board, int row, int n) {
if (row == n) {
res.add(construct(board));
return;
}
for (int col = 0; col < n; col++) {
if (isSafe(board, row, col, n)) {
board[row][col] = 'Q';
solve(res, board, row + 1, n);
board[row][col] = '.';
}
}
}
private boolean isSafe(char[][] board, int row, int col, int n) {
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 < n; i--, j++) {
if (board[i][j] == 'Q') return false;
}
return true;
}
private List<String> construct(char[][] board) {
return java.util.Arrays.stream(board)
.map(String::new)
.collect(Collectors.toList());
}
}
解释
方法:
这个题解使用了回溯法和位运算来解决 N 皇后问题。算法的核心是通过递归尝试在每一行放置一个皇后，并使用位运算来高效地检查是否满足不同行、不同列和不同对角线的约束。其中，column、diag1 和 diag2 分别用来表示已占用的列、主对角线和副对角线。avail 变量用来表示当前行中可放置皇后的位置。通过位运算，算法高效地找到可放置皇后的位置，并递归地在下一行继续放置皇后。
时间复杂度:
O(N! * N)
空间复杂度:
O(N)
代码细节讲解
🦆
在算法中，位运算是如何用来检查皇后是否与其他皇后在同一列或对角线上的？
▷🦆
为什么在算法中使用位运算可以提高效率，相比于其他可能的检查方法（如使用二维数组）有什么优势？
▷🦆
在递归函数`solve`中，如何确定变量`avail`代表的可用位置？
▷