backtracking/
lib.rs

1//! Find solutions with backtracking.
2
3/// A problem to be tackled with backtracking. Used by the [`Solutions`] iterator which can find
4/// solutions for ypes implementing [`Problem`].
5///
6/// Technically any problem solvable with backtracking would not need to keep any state, apart from
7/// the initial state, since all the essential input is part of the history. An empty implementation
8/// for [`Problem::what_if`] and [`Problem::undo`] would always be sufficient. Given the large
9/// search space for many of these problems, though, real world implementation are likely to keep
10/// some cached state, which is updated in these methods.
11pub trait Problem {
12    /// Describes a decision made in a problem state leading to a new candidate for a solution. E.g.
13    /// which field to jump to in a knights journey problem or which digit to write into a cell for
14    /// a sudoku puzzle.
15    type Posibility: Copy;
16    /// Final state we are interested in. E.g. The history of moves made for a knights journey, or
17    /// the final distribution of digits in the cells of a sudoku puzzle.
18    type Solution;
19
20    /// Extends `possibilities` with a set of decisions to be considered next. Implementations may
21    /// assume that the `possibilities` is empty if invoked through the `Solutions` iterator.
22    fn extend_possibilities(
23        &self,
24        possibilities: &mut Vec<Self::Posibility>,
25        history: &[Self::Posibility],
26    );
27
28    /// Undo the last decision made. If invoked by the [`Solutions`] iterator `last` is to be
29    /// guaranteed, to be the last decision made with [`do`]
30    fn undo(&mut self, last: &Self::Posibility, history: &[Self::Posibility]);
31
32    /// Update internal caches to reflect a scenario in which we would decide to execute the given
33    /// possibility.
34    fn what_if(&mut self, decision: Self::Posibility);
35
36    /// Check if the candidate state we are looking at is a solution to our probelm. If so extract
37    /// the information we are interessted in.
38    fn is_solution(&self, history: &[Self::Posibility]) -> Option<Self::Solution>;
39}
40
41/// An iterator performing backtracking to find solutions to a problem.
42pub struct Solutions<P: Problem> {
43    decisions: Vec<P::Posibility>,
44    open: Vec<Candidate<P::Posibility>>,
45    /// Keeps track of the decisions, which yielded the current problem state, starting from the
46    /// initial state.
47    history: Vec<P::Posibility>,
48    current: P,
49}
50
51impl<G: Problem> Solutions<G> {
52    pub fn new(init: G) -> Self {
53        let mut possible_moves = Vec::new();
54        init.extend_possibilities(&mut possible_moves, &[]);
55        let open = possible_moves
56            .iter()
57            .map(|pos| Candidate {
58                count: 1,
59                possibility: *pos,
60            })
61            .collect();
62        Self {
63            decisions: possible_moves,
64            open,
65            history: Vec::new(),
66            current: init,
67        }
68    }
69}
70
71impl<G: Problem> Iterator for Solutions<G> {
72    type Item = G::Solution;
73
74    fn next(&mut self) -> Option<Self::Item> {
75        while let Some(Candidate {
76            count,
77            possibility: mov,
78        }) = self.open.pop()
79        {
80            // Unroll all the moves until our current state is identical with the one which we
81            // had once we put that mov into the open list. We want to be one move behind so
82            // we need to play the move in order to get the desired state
83            for _ in 0..self.history.len() as i32 - count + 1 {
84                let last = self.history.pop().unwrap();
85                self.current.undo(&last, &self.history);
86            }
87
88            // We advance one move deeper into the search tree
89            self.current.what_if(mov);
90            self.history.push(mov);
91
92            // Emit solution
93            if let Some(solution) = self.current.is_solution(&self.history) {
94                return Some(solution);
95            }
96
97            // Extend search tree
98            self.decisions.clear();
99            self.current
100                .extend_possibilities(&mut self.decisions, &self.history);
101            self.open
102                .extend(self.decisions.iter().map(|&position| Candidate {
103                    count: count + 1,
104                    possibility: position,
105                }))
106        }
107        None
108    }
109}
110
111struct Candidate<P> {
112    /// Counts the number of turns made to get to this candidate. We keep track of this so we can
113    /// call undo the appropriate number of types, if we roll back to an earlier state.
114    count: i32,
115    /// Possibility which will lead to this candidate
116    possibility: P,
117}
backtracking/lib.rs

backtracking/
lib.rs
