deus-nqueens 0.4.1

fractal curves generation
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

use std::collections::{BTreeMap, BTreeSet};
use std::iter::from_generator;
use std::fmt::Display;
use rand::Rng;

mod display;

#[derive(Clone, Debug)]
pub struct NQueensState {
    size: isize,
    filled: Vec<isize>,
    unfilled: BTreeSet<isize>,
}


impl NQueensState {
    pub fn new(size: usize) -> Self {
        Self {
            size: size as isize,
            filled: Vec::with_capacity(size),
            unfilled: (0..size as isize).collect(),
        }
    }
    pub fn full_filled(&self) -> bool {
        self.unfilled.is_empty()
    }
    // Rotational symmetry and mirror symmetry points
    pub fn symmetrical(&self, x: isize, y: isize) -> Vec<(isize, isize)> {
        let mut symmetry = Vec::with_capacity(8);
        let s = self.size;
        let x = x % s;
        let y = y % s;
        symmetry.push((x, y));
        symmetry.push((s - x - 1, y));
        symmetry.push((x, s - y - 1));
        symmetry.push((s - x - 1, s - y - 1));
        symmetry.push((y, x));
        symmetry.push((s - y - 1, x));
        symmetry.push((y, s - x - 1));
        symmetry.push((s - y - 1, s - x - 1));
        symmetry
    }
    pub fn is_solution(&self) -> bool {
        for i in 0..self.size {
            if !self.filled.contains(&i) {
                return false;
            }
        }
        true
    }
    pub fn valid_at(&self, column: isize) -> bool {
        let row = self.filled.len() as isize;
        self.filled
            .iter()
            .enumerate()
            .all(|(solution_row, &solution_column)| {
                // Test for same column
                column != solution_column &&
                    // Test for same NE-SW diagonal
                    column + row != solution_column + solution_row as isize &&
                    // Test for same NW-SE diagonal
                    column - row != solution_column - solution_row as isize
            })
    }
    pub fn go_walk(&mut self, column: isize) {
        self.filled.push(column);
        self.unfilled.remove(&column);
    }
    pub fn go_back(&mut self) {
        match self.filled.pop() {
            Some(s) => {
                self.unfilled.insert(s);
            }
            None => {}
        }
    }
}

pub fn n_queens_backtracking(size: usize) -> impl Iterator<Item=NQueensState> {
    let mut stack = vec![NQueensState::new(size)];
    from_generator(move || {
        while let Some(mut state) = stack.pop() {
            if state.full_filled() {
                yield state;
                continue;
            };
            for row in state.unfilled.clone() {
                if state.valid_at(row) {
                    state.go_walk(row);
                    stack.push(state.clone());
                    state.go_back();
                }
            }
        }
    })
}

// pub fn n_queens_greedy(size: usize) -> Vec<NQueensState> {
//     let mut stack = vec![NQueensState::new(size)];
//     todo!()
// }

#[test]
fn test_n_queens_backtracking() {
    let mut count = 0;
    for solution in n_queens_backtracking(4) {
        println!("{}", solution);
        count += 1;
    }
    println!("{} solutions found", count);
}