Rust求解八皇后问题

八皇后问题是一个经典的回溯算法问题，目的是在 8x8 的棋盘上放置 8 个皇后，使得它们不能相互攻击。也就是说，任意两个皇后不能在同一行、同一列或同一对角线上。

这是一个使用 Rust 解决八皇后问题的完整代码，并附有详细的注解。Rust 和 Haskell 等函数式语言不同，在处理递归或高阶函数时，语法略有不同。我们可以使用回溯算法来解决这个问题。

Rust 解决八皇后问题的源代码：

fn main() {
    let n = 8;
    let mut board = vec![];  // 用于保存棋盘的状态，board[i] 代表第 i 列的皇后位置（即行号）
    solve_n_queens(n, &mut board);
}

fn solve_n_queens(n: usize, board: &mut Vec<usize>) {
    if board.len() == n {
        print_board(board, n);  // 如果所有皇后都放置完毕，打印当前解
    } else {
        for row in 0..n {
            if is_safe(board, row) {
                board.push(row);  // 将皇后放在当前列的 row 行
                solve_n_queens(n, board);  // 递归地放置下一列的皇后
                board.pop();  // 回溯，移除当前列的皇后，尝试下一个可能的行
            }
        }
    }
}

// 判断是否可以安全地在当前列的某一行放置皇后
fn is_safe(board: &Vec<usize>, row: usize) -> bool {
    let current_col = board.len();  // 当前要放置的列号
    
    for (col, &placed_row) in board.iter().enumerate() {
        // 检查：
        // 1. 同一行（不能在同一行放置皇后）
        // 2. 对角线（不能在对角线上放置皇后）
        if placed_row == row || (placed_row as isize - row as isize).abs() == (current_col as isize - col as isize) {
            return false;  // 如果同一行或对角线冲突，返回 false
        }
    }
    
    true  // 如果没有冲突，返回 true
}

// 打印棋盘的状态
fn print_board(board: &Vec<usize>, n: usize) {
    for &row in board.iter() {
        let mut line = vec!['.'; n];  // 初始化每一行，所有位置默认都是 "."
        line[row] = 'Q';  // 在当前行的正确位置放置皇后 "Q"
        println!("{}", line.iter().collect::<String>());  // 打印该行
    }
    println!();  // 每个解之间空一行
}

代码的详细解释：

1. 主函数 main:

   fn main() {
       let n = 8;
       let mut board = vec![];  // 用于保存棋盘的状态，board[i] 代表第 i 列的皇后位置（即行号）
       solve_n_queens(n, &mut board);
   }
   

   • 这里的 n 是皇后数量（问题的大小），即 8 皇后问题。
   • board 是一个 Vec<usize>，用于保存每一列的皇后位置。board[i] 表示第 i 列的皇后所处的行号。我们一开始用空的棋盘开始。
   • 调用 solve_n_queens 函数，它负责递归地解决问题并找到所有解。

2. 递归求解函数 solve_n_queens:

   fn solve_n_queens(n: usize, board: &mut Vec<usize>) {
       if board.len() == n {
           print_board(board, n);  // 如果所有皇后都放置完毕，打印当前解
       } else {
           for row in 0..n {
               if is_safe(board, row) {
                   board.push(row);  // 将皇后放在当前列的 row 行
                   solve_n_queens(n, board);  // 递归地放置下一列的皇后
                   board.pop();  // 回溯，移除当前列的皇后，尝试下一个可能的行
               }
           }
       }
   }
   

   • solve_n_queens 是递归求解八皇后问题的核心函数。
   • 它首先检查当前列是否已经放置了所有皇后，如果是，就调用 print_board 函数输出棋盘。
   • 如果还没放满皇后，程序会逐行尝试在当前列放置皇后，并通过 is_safe 检查当前行是否安全。如果安全，将该行号加入棋盘（board.push(row)），然后递归地解决下一列（调用 solve_n_queens）。
   • 在尝试所有可能行之后，通过 board.pop() 回溯，移除之前放置的皇后，继续尝试下一行。

3. 安全检查函数 is_safe:

   fn is_safe(board: &Vec<usize>, row: usize) -> bool {
       let current_col = board.len();  // 当前要放置的列号
       
       for (col, &placed_row) in board.iter().enumerate() {
           // 检查：
           // 1. 同一行（不能在同一行放置皇后）
           // 2. 对角线（不能在对角线上放置皇后）
           if placed_row == row || (placed_row as isize - row as isize).abs() == (current_col as isize - col as isize) {
               return false;  // 如果同一行或对角线冲突，返回 false
           }
       }
       
       true  // 如果没有冲突，返回 true
   }
   

   • is_safe 函数检查在当前列的某一行放置皇后是否安全。
   • 它遍历 board 中已经放置的所有皇后，确保不会与当前尝试放置的皇后冲突。冲突的条件是：
     1. 在同一行（placed_row == row）。
     2. 在同一对角线（两个皇后的行差和列差的绝对值相等，即 (placed_row - row).abs() == (current_col - col)）。
   • 如果有任何冲突，返回 false；否则，返回 true。

4. 打印棋盘函数 print_board:

   fn print_board(board: &Vec<usize>, n: usize)