N皇后算法

  1. #[allow(unused_imports)]
  2. use std::env::args;
  4. #[allow(dead_code)]
  5. fn main() {
  6.     let mut board_width = 0;
  8.     for arg in args() {
  9.         board_width = match arg.parse() {
  10.             Ok(x) => x,
  11.             _ => 0,
  12.         };
  14.         if board_width != 0 {
  15.             break;
  16.         }
  17.     }
  19.     if board_width < 4 {
  20.         println!(
  21.             "Running algorithm with 8 as a default. Specify an alternative Chess board size for \
  22.              N-Queens as a command line argument.\n"
  23.         );
  24.         board_width = 8;
  25.     }
  27.     let board = match nqueens(board_width) {
  28.         Ok(success) => success,
  29.         Err(err) => panic!("{}", err),
  30.     };
  32.     println!("N-Queens {} by {} board result:", board_width, board_width);
  33.     print_board(&board);
  34. }
  36. /*
  37. The n-Queens search is a backtracking algorithm. Each row of the Chess board where a Queen is
  38. placed is dependent on all earlier rows. As only one Queen can fit per row, a one-dimensional
  39. integer array is used to represent the Queen's offset on each row.
  40. */
  41. pub fn nqueens(board_width: i64) -> Result<Vec<i64>, &'static str> {
  42.     let mut board_rows = vec![0; board_width as usize];
  43.     let mut conflict;
  44.     let mut current_row = 0;
  46.     //Process by row up to the current active row
  47.     loop {
  48.         conflict = false;
  50.         //Column review of previous rows
  51.         for review_index in 0..current_row {
  52.             //Calculate the diagonals of earlier rows where a Queen would be a conflict
  53.             let left = board_rows[review_index] - (current_row as i64 - review_index as i64);
  54.             let right = board_rows[review_index] + (current_row as i64 - review_index as i64);
  56.             if board_rows[current_row] == board_rows[review_index]
  57.                 || (left >= 0 && left == board_rows[current_row])
  58.                 || (right < board_width as i64 && right == board_rows[current_row])
  59.             {
  60.                 conflict = true;
  61.                 break;
  62.             }
  63.         }
  65.         match conflict {
  66.             true => {
  67.                 board_rows[current_row] += 1;
  69.                 if current_row == 0 && board_rows[current_row] == board_width {
  70.                     return Err("No solution exists for specificed board size.");
  71.                 }
  73.                 while board_rows[current_row] == board_width {
  74.                     board_rows[current_row] = 0;
  76.                     if current_row == 0 {
  77.                         return Err("No solution exists for specificed board size.");
  78.                     }
  80.                     current_row -= 1;
  81.                     board_rows[current_row] += 1;
  82.                 }
  83.             }
  84.             _ => {
  85.                 current_row += 1;
  87.                 if current_row as i64 == board_width {
  88.                     break;
  89.                 }
  90.             }
  91.         }
  92.     }
  94.     Ok(board_rows)
  95. }
  97. fn print_board(board: &[i64]) {
  98.     for row in 0..board.len() {
  99.         print!("{}\t", board[row as usize]);
  101.         for column in 0..board.len() as i64 {
  102.             if board[row as usize] == column {
  103.                 print!("Q");
  104.             } else {
  105.                 print!(".");
  106.             }
  107.         }
  108.         println!();
  109.     }
  110. }
  112. #[cfg(test)]
  113. mod test {
  114.     use super::*;
  116.     fn check_board(board: &Vec<i64>) -> bool {
  117.         for current_row in 0..board.len() {
  118.             //Column review
  119.             for review_index in 0..current_row {
  120.                 //Look for any conflict.
  121.                 let left = board[review_index] - (current_row as i64 - review_index as i64);
  122.                 let right = board[review_index] + (current_row as i64 - review_index as i64);
  124.                 if board[current_row] == board[review_index]
  125.                     || (left >= 0 && left == board[current_row])
  126.                     || (right < board.len() as i64 && right == board[current_row])
  127.                 {
  128.                     return false;
  129.                 }
  130.             }
  131.         }
  132.         true
  133.     }
  135.     #[test]
  136.     fn test_board_size_4() {
  137.         let board = nqueens(4).expect("Error propagated.");
  138.         assert_eq!(board, vec![1, 3, 0, 2]);
  139.         assert!(check_board(&board));
  140.     }
  142.     #[test]
  143.     fn test_board_size_7() {
  144.         let board = nqueens(7).expect("Error propagated.");
  145.         assert_eq!(board, vec![0, 2, 4, 6, 1, 3, 5]);
  146.         assert!(check_board(&board));
  147.     }
  148. }