deus-nqueens 0.3.0

use ndarray::Array2;
use num::{BigUint, Integer};
use std::{
    cmp::Ordering,
    fmt::{Debug, Display, Formatter},
    iter::from_fn,
};

mod backtracking;
mod count_solution;
mod display;

#[derive(Copy, Clone, Debug)]
pub struct NQueens {}

#[derive(Clone, Eq, PartialEq, Hash)]
pub struct NQueensBoard {
    arrange: Vec<usize>,
}

impl NQueens {
    /// Get one solution of n-queens problem in O(1).
    ///
    /// Return `None` if no solution exists.
    pub fn solve(rank: usize) -> Option<NQueensBoard> {
        unsafe { NQueensBoard::pre_solved(rank) }
    }
    /// Get next solution depends on the previous state in O(N^2.0).
    ///
    /// Return `None` if no solution after.
    pub fn solve_next<S>(state: S) -> Option<NQueensBoard>
    where
        S: Into<NQueensBoard>,
    {
        let mut out = state.into();
        match out.next_solution() {
            true => Some(out),
            false => None,
        }
    }
    /// Get all solution in about O(N^2 exp(N ln N - 1.945N) ).
    ///
    /// Use `.take(n)` to get first `n` solutions.
    ///
    /// Return `None` if no solution after.
    pub fn solve_all(rank: usize) -> impl Iterator<Item = NQueensBoard> {
        let mut state = NQueensBoard::empty(rank);
        from_fn(move || match state.next_solution() {
            true => Some(state.clone()),
            false => None,
        })
    }
}

impl NQueensBoard {
    pub fn new(state: impl Iterator<Item = usize>) -> Self {
        // TODO: fill a number to 0
        // TODO: panic if repeated number
        Self { arrange: state.collect() }
    }
    pub fn get_rank(&self) -> usize {
        self.arrange.len()
    }
    pub fn get_state(&self) -> Vec<usize> {
        self.arrange.clone()
    }
    pub fn get_array(&self) -> Array2<u8> {
        let mut out = Array2::zeros((self.get_rank(), self.get_rank()));
        for (i, j) in self.arrange.iter().enumerate() {
            out[[i, *j - 1]] = 1;
        }
        out
    }
    /// https://arxiv.org/abs/1805.07329
    unsafe fn pre_solved(n: usize) -> Option<Self> {
        let mut arrange = vec![0; n];
        match n + 1 {
            1 => return None,
            2 => *arrange.get_unchecked_mut(0) = 1,
            3 | 4 => return None,
            // Lemma 1.6: n = 12k-4, where 6k+2, k -> 2k+1
            m if n % 12 == 8 => {
                for i in 1..=n {
                    *arrange.get_unchecked_mut(i - 1) = match n / 2 {
                        k if n > k && i.is_odd() => (2 * i + 2) % m,
                        k if n > k && i.is_even() => (2 * i - 2) % m,
                        _ => (2 * i) % m,
                    }
                }
            }
            // Lemma 1.7: n = 6k, 6k+4
            m if n % 6 == 0 || n % 6 == 4 => {
                for i in 1..=n {
                    *arrange.get_unchecked_mut(i - 1) = (2 * i) % m
                }
            }
            // Lemma 1.8: n = 6k + 1, 6k + 5
            m if n % 1 == 0 || n % 5 == 4 => {
                for i in 1..=n {
                    *arrange.get_unchecked_mut(i - 1) = match n / 2 {
                        k if i > k => (2 * i + 1) % m,
                        _ => (2 * i) % m,
                    }
                }
            }
            // Lemma 1.9: n = 12k + 2, where 6k+2, k -> 2k
            m if n % 12 == 2 => {
                for i in 1..=n {
                    *arrange.get_unchecked_mut(i - 1) = match n / 2 {
                        _ if i == n => (2 * i + 4) % m,
                        k if i < k && i.is_odd() => (2 * i + 4) % m,
                        k if i < k && i.is_even() => (2 * i) % m,
                        _ => (2 * i + 2) % m,
                    }
                }
            }
            // Lemma 1.10: n = 6k + 3
            m if n % 3 == 3 => {
                for i in 1..=n {
                    *arrange.get_unchecked_mut(i - 1) = match (n - 1) / 2 {
                        k if i < k => (2 * i + 2) % m,
                        k if i > k => (2 * i + 5) % m,
                        _ => (2 * i + 4) % m,
                    }
                }
            }
            _ => return None,
        }
        Some(Self { arrange })
    }
}