N 皇后
题目要求
这个问题是著名的 n 皇后问题，要求我们在一个 n×n 的棋盘上放置 n 个皇后，并且保证这些皇后之间不能互相攻击。在国际象棋中，皇后可以攻击同一行、同一列或同一斜线上的其他棋子。因此，n 皇后问题的解决方案要求在棋盘上的每一行、每一列以及每条对角线上都最多只有一个皇后。
具体来说，需要编写一个算法，输入一个整数 n，输出所有符合条件的 n 皇后摆放方案。每个方案都需要用一个 n×n 的矩阵来表示，其中'Q'表示一个皇后的位置，'.'表示空位。
解题思路
解决 n 皇后问题的一个常见方法是使用回溯算法。回溯算法是一种通过试错来寻找所有解决方案的算法，当它发现已不满足求解条件时，它会返回（即“回溯”）并尝试另一种可能的解决方案，直到找到所有可能的解决方案。以下是解决 n 皇后问题的回溯算法的基本步骤：
- 从棋盘的第一行开始，尝试在每一列中放置一个皇后。
- 在放置每一个皇后之前，检查当前的列、行以及两个对角线上是否已经有皇后。如果已经有皇后，则当前位置不能放置皇后，需要尝试下一列。
- 如果找到了一个合法的位置，则放置皇后，并递归地在下一行中寻找合法的皇后位置。
- 如果在当前行找不到合法的位置放置皇后，说明前面的某一步选择错误，需要回溯到上一行，移动皇后的位置。
- 当成功放置了最后一行的皇后时，就找到了一个解决方案。记录下当前棋盘的状态，然后回溯，继续寻找下一个解决方案。
- 重复以上步骤，直到棋盘的所有行都尝试过，找出所有可能的解决方案。
为了有效地检查皇后的放置是否冲突，可以使用三个辅助数组来记录每一列、每个主对角线和每个副对角线上是否已经放置了皇后。主对角线的特点是行号减列号为常数，副对角线的特点是行号加列号为常数，利用这个特性可以快速检查对角线上是否有冲突。
通过这种方法，可以找到所有的 n 皇后问题的解决方案，并以所需的格式返回。
Golang 版本
package main
import (
"fmt"
"strings"
)
func solveNQueens(n int) [][]string {
results := [][]string{}
board := make([][]string, n)
for i := range board {
board[i] = make([]string, n)
for j := range board[i] {
board[i][j] = "."
}
}
columns := make([]bool, n)
diagonals1 := make([]bool, 2*n)
diagonals2 := make([]bool, 2*n)
backtrack(board, 0, n, &results, columns, diagonals1, diagonals2)
return results
}
func backtrack(board [][]string, row, n int, results *[][]string, columns, diagonals1, diagonals2 []bool) {
if row == n {
temp := make([]string, n)
for i := range board {
temp[i] = strings.Join(board[i], "")
}
*results = append(*results, temp)
return
}
for i := 0; i < n; i++ {
if columns[i] || diagonals1[row+i] || diagonals2[row-i+n] {
continue
}
board[row][i] = "Q"
columns[i] = true
diagonals1[row+i] = true
diagonals2[row-i+n] = true
backtrack(board, row+1, n, results, columns, diagonals1, diagonals2)
board[row][i] = "."
columns[i] = false
diagonals1[row+i] = false
diagonals2[row-i+n] = false
}
}
func main() {
n := 4 // or any n you want to solve for
solutions := solveNQueens(n)
for _, solution := range solutions {
for _, row := range solution {
fmt.Println(row)
}
fmt.Println()
}
}
这段代码定义了一个solveNQueens函数，它接受一个整数n作为参数，并返回一个二维字符串切片，其中包含所有可能的 n 皇后解决方案。主要的逻辑是通过回溯算法来实现的，其中backtrack函数是递归调用的核心，用于尝试放置皇后并检查是否有冲突。程序的入口是main函数，它调用solveNQueens函数并打印出所有解决方案。
C++版本
#include <iostream>
#include <vector>
#include <string>
class Solution {
public:
std::vector<std::vector<std::string>> solveNQueens(int n) {
std::vector<std::vector<std::string>> solutions;
std::vector<std::string> board(n, std::string(n, '.'));
std::vector<bool> column(n, false), diag1(2 * n, false), diag2(2 * n, false);
backtrack(0, n, board, solutions, column, diag1, diag2);
return solutions;
}
private:
void backtrack(int row, int n, std::vector<std::string>& board,
std::vector<std::vector<std::string>>& solutions,
std::vector<bool>& column, std::vector<bool>& diag1,
std::vector<bool>& diag2) {
if (row == n) {
solutions.push_back(board);
return;
}
for (int col = 0; col < n; ++col) {
if (column[col] || diag1[row + col] || diag2[row - col + n]) continue;
board[row][col] = 'Q';
column[col] = diag1[row + col] = diag2[row - col + n] = true;
backtrack(row + 1, n, board, solutions, column, diag1, diag2);
board[row][col] = '.';
column[col] = diag1[row + col] = diag2[row - col + n] = false;
}
}
};
int main() {
Solution solution;
int n = 4; // or any n you want to solve for
std::vector<std::vector<std::string>> solutions = solution.solveNQueens(n);
for (const auto& solution : solutions) {
for (const auto& row : solution) {
std::cout << row << std::endl;
}
std::cout << std::endl;
}
return 0;
}
这段 C++代码定义了一个Solution类，其中包含解决 n 皇后问题的solveNQueens方法。该方法返回一个二维字符串向量，其中包含所有可能的解决方案。backtrack是一个私有方法，用于递归地放置皇后并检查是否有冲突。main函数中创建了一个Solution对象，并调用solveNQueens方法，然后打印出所有的解决方案。
Python 版本
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def create_board(state):
board = []
for row in state:
board.append('.' * row + 'Q' + '.' * (n - row - 1))
return board
def backtrack(row):
if row == n:
board = create_board(state)
solutions.append(board)
return
for col in range(n):
if col in cols or (row + col) in diag1 or (row - col) in diag2:
continue
cols.add(col)
diag1.add(row + col)
diag2.add(row - col)
state.append(col)
backtrack(row + 1)
cols.remove(col)
diag1.remove(row + col)
diag2.remove(row - col)
state.pop()
solutions = []
state = []
cols = set()
diag1 = set()
diag2 = set()
backtrack(0)
return solutions
# Example usage:
# sol = Solution()
# print(sol.solveNQueens(4))
这段 Python 代码定义了一个Solution类，其中包含解决 n 皇后问题的solveNQueens方法。该方法使用回溯算法找出所有可能的解决方案，并返回一个列表，其中每个元素代表一个解决方案的棋盘布局。棋盘布局用字符串列表表示，其中'Q'代表皇后，'.'代表空位。create_board函数用于根据当前状态生成棋盘布局。backtrack函数是递归的核心，用于尝试在每一行放置皇后并检查是否有冲突。
Java 版本
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<List<String>> solveNQueens(int n) {
char[][] board = new char[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = '.';
}
}
List<List<String>> solutions = new ArrayList<>();
boolean[] cols = new boolean[n]; // columns |
boolean[] d1 = new boolean[2 * n]; // diagonals \
boolean[] d2 = new boolean[2 * n]; // diagonals /
backtrack(0, n, board, solutions, cols, d1, d2);
return solutions;
}
private void backtrack(int row, int n, char[][] board, List<List<String>> solutions, boolean[] cols, boolean[] d1, boolean[] d2) {
if (row == n) {
solutions.add(createBoard(board));
return;
}
for (int col = 0; col < n; col++) {
int id1 = col - row + n;
int id2 = col + row;
if (cols[col] || d1[id1] || d2[id2]) continue;
cols[col] = true; d1[id1] = true; d2[id2] = true;
board[row][col] = 'Q';
backtrack(row + 1, n, board, solutions, cols, d1, d2);
board[row][col] = '.';
cols[col] = false; d1[id1] = false; d2[id2] = false;
}
}
private List<String> createBoard(char[][] board) {
List<String> res = new ArrayList<>();
for (char[] row : board) {
res.add(new String(row));
}
return res;
}
public static void main(String[] args) {
Solution solution = new Solution();
List<List<String>> solutions = solution.solveNQueens(4);
for (List<String> sol : solutions) {
for (String row : sol) {
System.out.println(row);
}
System.out.println();
}
}
}
这段 Java 代码定义了一个Solution类，其中包含解决 n 皇后问题的solveNQueens方法。该方法使用回溯算法找出所有可能的解决方案，并返回一个列表，其中每个元素代表一个解决方案的棋盘布局。棋盘布局用字符串列表表示，其中'Q'代表皇后，'.'代表空位。createBoard方法用于从字符数组生成棋盘布局。backtrack方法是递归的核心，用于尝试在每一行放置皇后并检查是否有冲突。main方法用于演示如何调用solveNQueens方法并打印出所有解决方案。
Rust 版本
fn solve_n_queens(n: i32) -> Vec<Vec<String>> { let mut solutions = Vec::new(); let mut board = vec![vec!['.'; n as usize]; n as usize]; let mut cols = vec![false; n as usize]; let mut diag1 = vec![false; (2 * n) as usize]; let mut diag2 = vec![false; (2 * n) as usize]; backtrack(0, n, &mut board, &mut solutions, &mut cols, &mut diag1, &mut diag2); solutions } fn backtrack(row: i32, n: i32, board: &mut Vec<Vec<char>>, solutions: &mut Vec<Vec<String>>, cols: &mut Vec<bool>, diag1: &mut Vec<bool>, diag2: &mut Vec<bool>) { if row == n { solutions.push(board.iter().map(|r| r.iter().collect()).collect()); return; } for col in 0..n { let d1 = (col - row + n) as usize; let d2 = (col + row) as usize; if cols[col as usize] || diag1[d1] || diag2[d2] { continue; } cols[col as usize] = true; diag1[d1] = true; diag2[d2] = true; board[row as usize][col as usize] = 'Q'; backtrack(row + 1, n, board, solutions, cols, diag1, diag2); board[row as usize][col as usize] = '.'; cols[col as usize] = false; diag1[d1] = false; diag2[d2] = false; } } fn main() { let solutions = solve_n_queens(4); for solution in solutions { for row in solution { println!("{}", row); } println!(); } }
这段 Rust 代码定义了一个解决 n 皇后问题的函数solve_n_queens，它使用回溯算法找出所有可能的解决方案，并返回一个包含解决方案的向量。每个解决方案都是一个字符串向量，其中每个字符串代表棋盘的一行，'Q'代表皇后，'.'代表空位。backtrack函数是递归的核心，用于尝试在每一行放置皇后并检查是否有冲突。main函数用于演示如何调用solve_n_queens函数并打印出所有解决方案。
总结
上述 Rust 代码实现了经典的 N 皇后问题的解决方案。N 皇后问题要求在一个 N×N 的棋盘上放置 N 个皇后，使得它们互不攻击，即任意两个皇后都不在同一行、同一列或同一对角线上。解决方案采用了回溯算法，这是一种深度优先搜索算法，用于穷举所有可能的解决方案并回退到上一个状态，以尝试不同的解决路径。
具体步骤如下：
- 初始化一个空棋盘，棋盘的大小为 N×N，所有位置都用'.'表示空位。
- 使用三个布尔向量来跟踪哪些列以及两个方向的对角线上已经放置了皇后，以避免冲突。
- 从第一行开始，尝试在每一列放置一个皇后，并递归地在下一行中寻找合适的位置。
- 如果当前位置放置皇后会导致冲突（即同列或对角线上已有皇后），则跳过当前列，尝试下一列。
- 如果找到一个合法的位置，就在当前位置放置皇后（用'Q'表示），并更新列和对角线的占用状态。
- 递归调用回溯函数，尝试在下一行放置皇后。
- 如果所有行都成功放置了皇后，将当前棋盘的解决方案添加到解决方案集合中。
- 在回溯到上一行时，清除当前位置的皇后，并重置列和对角线的占用状态，以便尝试新的位置。
最终，solve_n_queens函数返回所有可能的棋盘配置，每个配置都是一个字符串向量，代表了一个有效的 N 皇后解决方案。main函数则用于演示如何调用这个函数并打印出所有的解决方案。