deus-nqueens 0.3.0

use super::*;

impl Default for NQueensBoard {
    // The only symmetrical solution to the eight queens puzzle
    fn default() -> Self {
        Self { arrange: vec![6, 4, 7, 1, 8, 2, 5, 3] }
    }
}

impl Iterator for NQueensBoard {
    type Item = bool;

    fn next(&mut self) -> Option<Self::Item> {
        match next_permutation(&mut self.arrange) {
            true => Some(self.is_solution()),
            false => None,
        }
    }
}

impl NQueensBoard {
    /// Create a initialized board state
    ///
    /// Notice that it is not a valid state.
    pub fn empty(rank: usize) -> Self {
        Self { arrange: (1..=rank).collect() }
    }
    /// Check if current state is a valid solution
    pub fn is_solution(&self) -> bool {
        // TODO: optimize by Statement 1.2
        let iter = self.arrange.iter().enumerate();
        iter.clone().all(|(col, &row)| {
            iter.clone().filter(|&(c, _)| c != col).all(|(o_col, &o_row)| {
                col as isize - row as isize != o_col as isize - o_row as isize && col as usize + row != o_col as usize + o_row
            })
        })
    }
    /// Get next solution form current state
    ///
    /// Return `true` if successfully find one solution
    /// Return `false` if reach the end state
    pub fn next_solution(&mut self) -> bool {
        loop {
            match self.next() {
                None => return false,
                Some(true) => return true,
                Some(false) => continue,
            }
        }
    }
}

pub fn next_permutation(arrange: &mut [usize]) -> bool {
    // TODO: use feature(array_windows)
    let last_ascending = match arrange.windows(2).rposition(|w| w[0] < w[1]) {
        Some(i) => i,
        None => {
            arrange.reverse();
            return false;
        }
    };

    let swap_with = arrange[last_ascending + 1..]
        .binary_search_by(|n| usize::cmp(&arrange[last_ascending], n).then(Ordering::Less))
        // can't fail because the binary search will never succeed
        .unwrap_err();
    arrange.swap(last_ascending, last_ascending + swap_with);
    arrange[last_ascending + 1..].reverse();
    true
}