n_queens/
n_queens.rs

1use std::fmt::{self, Display, Formatter};
2
3use backtracking::{Problem, Solutions};
4
5fn main() {
6    let board = NQueens::new(8);
7    for solution in Solutions::new(board) {
8        println!("{solution}")
9    }
10}
11
12#[derive(Clone)]
13struct NQueens {
14    n: u32,
15}
16
17impl NQueens {
18    fn new(n: u32) -> Self {
19        Self { n }
20    }
21}
22
23/// Possition of an individual queen on the board
24#[derive(Clone, Copy)]
25struct QueenAt {
26    row: u32,
27    column: u32,
28}
29
30impl QueenAt {
31    /// True if the two queens are not allowed at the board at the same time.
32    fn conflicts(self, other: QueenAt) -> bool {
33        self.row == other.row
34            || self.column == other.column
35            || self.row.abs_diff(other.row) == self.column.abs_diff(other.column)
36    }
37}
38
39impl Problem for NQueens {
40    type Posibility = QueenAt;
41    type Solution = NQueensSolution;
42
43    fn extend_possibilities(&self, possible_moves: &mut Vec<QueenAt>, history: &[QueenAt]) {
44        if history.len() == self.n as usize {
45            return;
46        }
47        // Give all possible position for the top empty row
48        let possibilities = (0..self.n)
49            .map(|col| QueenAt {
50                row: history.len() as u32,
51                column: col,
52            })
53            .filter(|candidate| history.iter().all(|q| !q.conflicts(*candidate)));
54        possible_moves.extend(possibilities);
55    }
56
57    fn undo(&mut self, _last: &Self::Posibility, _history: &[Self::Posibility]) {}
58
59    fn what_if(&mut self, _next: QueenAt) {}
60
61    fn is_solution(&self, history: &[QueenAt]) -> Option<NQueensSolution> {
62        if history.len() == self.n as usize {
63            let mut solution = vec![0; self.n as usize];
64            for queen in history {
65                solution[queen.row as usize] = queen.column;
66            }
67            Some(NQueensSolution(solution))
68        } else {
69            None
70        }
71    }
72}
73
74/// Solution to the n queens problem. Nth index of vec contains column index of queen in n-th row.
75struct NQueensSolution(Vec<u32>);
76
77impl Display for NQueensSolution {
78    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
79        let repeat_point = |f: &mut Formatter, n| {
80            for _ in 0..n {
81                write!(f, ".")?;
82            }
83            Ok(())
84        };
85
86        for &pos in &self.0 {
87            repeat_point(f, pos)?;
88            write!(f, "Q")?;
89            repeat_point(f, self.0.len() as u32 - pos - 1)?;
90            writeln!(f)?;
91        }
92        Ok(())
93    }
94}
n_queens/n_queens.rs

n_queens/
n_queens.rs
