An implementation of backtracking algorithm with Rust.

backtrack.rs

use std::collections::HashSet;

/// Monoid must satisfy:
/// ```rs
/// fn test<M: Monoid>(m: M, n: M, l: M) {
///   assert_eq!(m.op(M::ID), m);
///   assert_eq!(M::ID.op(m), m);
///   assert_eq!(m.op(n.op(l)), m.op(n).op(l));
/// }
/// ```
pub trait Monoid: Copy + Eq {
    const ID: Self;
    fn op(self, other: Self) -> Self;
}

/// A structure to seek state space by going and leaving a step. It is efficient for memory because no allocation is required.
pub trait BacktrackingState {
    /// A command generated by `next_steps`.
    type Step: Copy + Eq + std::hash::Hash;
    type Steps: IntoIterator<Item = Self::Step>;
    /// Generates next commands from the state to seek other states.
    fn next_steps(&self, track: &[Self::Step]) -> Self::Steps;
    /// Applies the command to the state.
    fn forward(&mut self, going: Self::Step);
    /// Undos the command from the state. This will be always called after `forward` unless panicking.
    fn back(&mut self, leaving: Self::Step);
    /// Determines whether the state is a solution you're finding.
    fn is_goal(&self, track: &[Self::Step], next: Self::Step) -> bool;

    /// A metric how the solution is good. Two results of solution will be combined by the `Monoid::op`.
    type Score: Monoid;
    /// Evaluates how the backtrack history is good by returning a `Score`.
    fn score(&self, track: &[Self::Step]) -> Self::Score;
}

/// Backtracks the state space with methods of `BacktrackingState` trait.
/// It preserves `state` data unless panicking implement of `BacktrackingState` for `S`.
pub fn backtracking<S: BacktrackingState>(state: &mut S, start: S::Step) -> S::Score {
    fn recursion<S: BacktrackingState>(
        track: &mut Vec<S::Step>,
        visited: &mut HashSet<S::Step>,
        state: &mut S,
    ) -> S::Score {
        let mut score = <S::Score as Monoid>::ID;
        for next in state.next_steps(track) {
            if state.is_goal(track, next) {
                score = score.op(state.score(track));
                continue;
            }
            if visited.contains(&next) {
                continue;
            }
            state.forward(next);
            visited.insert(next);
            track.push(next);
            score = score.op(recursion(track, visited, state));
            track.pop();
            visited.remove(&next);
            state.back(next);
        }
        score
    }
    let mut set = HashSet::new();
    set.insert(start);
    recursion(&mut vec![start], &mut set, state)
}