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
use std::{
fmt::{Display, Formatter},
iter::from_generator,
};
mod display;
#[derive(Clone, Debug)]
pub struct NBishopsState {
size: isize,
filled: Vec<isize>,
}
impl NBishopsState {
pub fn new(size: usize) -> Self {
Self { size: size as isize, filled: Vec::with_capacity(size) }
}
pub fn full_filled(&self) -> bool {
self.filled.len() == self.size as usize
}
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)| {
column + row != solution_column + solution_row as isize &&
column - row != solution_column - solution_row as isize
})
}
pub fn go_walk(&mut self, column: isize) {
self.filled.push(column);
}
pub fn go_back(&mut self) {
self.filled.pop();
}
}
pub fn n_bishops_backtrack(size: usize) -> impl Iterator<Item = NBishopsState> {
let mut stack = vec![NBishopsState::new(size)];
from_generator(move || {
while let Some(mut state) = stack.pop() {
if state.full_filled() {
yield state;
continue;
};
for row in 0..state.size {
if state.valid_at(row) {
state.go_walk(row);
stack.push(state.clone());
state.go_back();
}
}
}
})
}