dlx_rs/
queens.rs

1use crate::Solver;
2
3/// Implements solution to the N queens problem
4///
5/// ```
6///# use dlx_rs::queens::Queens;
7/// let n_queens_solutions = vec![0,1,0,0,2,10,4,40,92,352,724];
8/// for i in 1..=10 {
9///     let qi = Queens::new(i);
10///     assert_eq!(qi.count(), n_queens_solutions[i]);
11/// }
12/// ```
13pub struct Queens {
14    n: usize,
15    solver: Solver<String>,
16}
17
18impl Queens {
19    /// Creates new `Queens` set up with constraints for the `n` queens problem
20    pub fn new(n: usize) -> Queens {
21        // Create blank solver
22
23        // Add constraints
24
25        // What are the constraints?
26        // We are putting N queens on an NxN chess board
27
28        // 1. Each of the N columns must have exactly 1 queen on it
29        // 2. Each of the N rows must have exactly 1 queen on it
30        // 3. Each of the 2*N-1 right diagonals may have at most one queen
31        // 4. Each of the 2*N-1 left diagonals may have at most one queen
32        // 5. Each of the N^2 squares may have at most one queen
33
34        // So this gives us 2*N mandatory items, and N^2 + 6*N -2 optional ones
35
36        let mut solver = Solver::new_optional(2 * n, n * n + 6 * n - 2);
37
38        // Now add options: each option corresponds to a queen in a particular
39
40        for r in 1..=n {
41            for c in 1..=n {
42                let con_name = format!("R{}C{}", r, c);
43                // 1 -> N
44                let col_con = c;
45                // N+1 -> 2*N
46                let row_con = n + r;
47                // 2*N+1 -> 4*N - 1
48                let rd_con = 2 * n + c - r + n;
49                // 4*N ->  6*N - 2
50                let ld_con = 4 * n - 1 + r + c - 1;
51                // 6*N-1 -> N**2 + 6*N - 2
52                let is_queen = 6 * n - 2 + r + n * (c - 1);
53
54                solver.add_option(con_name, &[col_con, row_con, rd_con, ld_con, is_queen]);
55            }
56        }
57
58        Queens { solver, n }
59    }
60}
61
62impl Iterator for Queens {
63    type Item = Vec<(usize, usize)>;
64    /// Returns the next solution, which is a vector of tuples denoting the Row and Column of the N queens in the solution
65    fn next(&mut self) -> Option<Self::Item> {
66        if let Some(sol) = self.solver.next() {
67            let mut n_queens_solved = Vec::with_capacity(self.n);
68            for i in sol {
69                let i = i.as_str();
70                let s: Vec<&str> = i.split(&['R', 'C']).collect(); //.split('C').split('#');
71                let r: usize = s[1].parse().unwrap();
72                let c: usize = s[2].parse().unwrap();
73                n_queens_solved.push((r, c));
74            }
75            Some(n_queens_solved)
76        } else {
77            None
78        }
79    }
80}
dlx_rs/queens.rs

dlx_rs/
queens.rs
