qsolve 1.1.0

A library and command-line tool for solving Queens puzzles
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

use crate::{
    heuristic::{Heuristic, next_heuristic},
    solvestate::{SolveState, SolveStrategy},
};

/// This represents a stage in the process of solving a Queens board.
/// It contains both the current state of solving (solve_state), and
/// the next heuristic that will be used to advance the solving process
/// (next_heuristic). If no heuristic could be found (meaning either
/// the heuristic set is incomplete, or the board is solved), then
/// next_heuristic will be None.
pub struct SolveIterItem<'h, 'ss> {
    /// The current [SolveState] during the solving process.
    pub solve_state: SolveState<'ss>,

    /// The next [Heuristic] that we will apply to the given [SolveState],
    /// or None if no heuristic could be found.
    pub next_heuristic: Option<&'h dyn Heuristic>,
}

/// An Iterator that returns a series of StateIterItem's representing
/// the solving process for a given board.
pub struct SolveIter<'h, 'ss> {
    solve_state: SolveState<'ss>,
    solve_strategy: SolveStrategy,
    heuristics: &'h [Box<dyn Heuristic>],
    done: bool,
}
impl<'h, 'ss> Iterator for SolveIter<'h, 'ss> {
    type Item = SolveIterItem<'h, 'ss>;

    fn next(&mut self) -> Option<Self::Item> {
        if self.done {
            return None;
        }
        if self.solve_state.complete() {
            self.done = true;
            return Some(SolveIterItem {
                solve_state: self.solve_state.clone(),
                next_heuristic: None,
            });
        }
        let h = next_heuristic(&self.solve_state, self.solve_strategy, self.heuristics)?;
        let changes = h.changes(&self.solve_state)?;
        let old_solve_state = self.solve_state.clone();
        self.solve_state.apply_changes(&changes);
        Some(SolveIterItem {
            solve_state: old_solve_state,
            next_heuristic: Some(h),
        })
    }
}

/// Returns an Iterator that represents the solving of the provided
/// Queens solve state, using the given strategy and set of heuristics.
pub fn solve_iter<'h, 'b>(
    solve_state: SolveState<'b>,
    solve_strategy: SolveStrategy,
    heuristics: &'h [Box<dyn Heuristic>],
) -> SolveIter<'h, 'b> {
    SolveIter {
        solve_state,
        solve_strategy,
        heuristics,
        done: false,
    }
}

#[cfg(test)]
mod tests {
    use std::str::FromStr;

    use anyhow::Result;

    use crate::{board::Board, heuristic::all_heuristics};

    use super::*;

    #[test]
    fn solve_iter_succeeds() -> Result<()> {
        let board_str = "wwww\nwkkk\nrrrr\nbbbb";
        let board = Board::from_str(board_str)?;
        let solve_state = SolveState::from(&board);
        let heuristics = all_heuristics(&board);
        let mut solve_iter = solve_iter(solve_state, SolveStrategy::Fast, &heuristics);
        assert!(solve_iter.next().is_some());

        Ok(())
    }

    #[test]
    fn solve_iter_does_not_complete_ambiguous_board() -> Result<()> {
        let board_str = "wwww\nkkkk\nrrrr\nbbbb"; // This board is ambiguous: it has two solutions.
        let board = Board::from_str(board_str)?;
        let solve_state = SolveState::from(&board);
        let heuristics = all_heuristics(&board);
        let state_iter_items =
            solve_iter(solve_state, SolveStrategy::Fast, &heuristics).collect::<Vec<_>>();
        assert!(
            state_iter_items
                .iter()
                .all(|item| !item.solve_state.complete())
        );

        Ok(())
    }
}