use crate::ExactCover;
use core::iter;
use std::collections::HashSet;
#[derive(Debug)]
pub struct NQueens {
pub possibilities: Vec<Possibility>,
pub constraints: Vec<Constraint>,
pub side_length: usize,
}
impl NQueens {
pub fn new(side_length: usize, filled_values: impl IntoIterator<Item = Possibility>) -> Self {
let filled_values: Vec<_> = filled_values.into_iter().collect();
let satisfied: HashSet<_> = filled_values
.iter()
.copied()
.flat_map(|poss| poss.satisfied_constraints(side_length))
.collect();
let filled_coordinates: HashSet<_> = filled_values
.iter()
.map(|poss| (poss.row, poss.column))
.collect();
let possibilities: Vec<_> = Possibility::all(side_length)
.filter(|poss| !filled_coordinates.contains(&(poss.row, poss.column)))
.collect();
let constraints = Constraint::all(side_length)
.filter(|cons| !satisfied.contains(cons))
.collect();
Self {
possibilities,
constraints,
side_length,
}
}
}
impl ExactCover for NQueens {
type Constraint = Constraint;
type Possibility = Possibility;
fn satisfies(&self, poss: &Self::Possibility, cons: &Self::Constraint) -> bool {
use Constraint::*;
match cons {
Row { index } => poss.row == *index,
Column { index } => poss.column == *index,
LeadingDiagonal { index } => poss.leading_diagonal(self.side_length) == *index,
TrailingDiagonal { index } => poss.trailing_diagonal() == *index,
}
}
fn is_optional(&self, cons: &Self::Constraint) -> bool {
matches!(cons, Constraint::LeadingDiagonal {..} | Constraint::TrailingDiagonal {..})
}
fn possibilities(&self) -> &[Self::Possibility] {
&self.possibilities
}
fn constraints(&self) -> &[Self::Constraint] {
&self.constraints
}
}
#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct Possibility {
row: usize,
column: usize,
}
impl Possibility {
pub fn all(side_length: usize) -> impl Iterator<Item = Self> {
crate::util::two_combination_iter([side_length, side_length], [0, 0])
.map(|[column, row]| Possibility { row, column })
}
pub fn leading_diagonal(self, side_length: usize) -> usize {
((self.column as i128 - self.row as i128) + (side_length - 1) as i128) as usize
}
pub fn trailing_diagonal(self) -> usize {
self.row + self.column
}
pub fn satisfied_constraints(self, side_length: usize) -> impl Iterator<Item = Constraint> {
iter::successors(
Some(Constraint::Row { index: self.row }),
move |cons| match cons {
Constraint::Row { .. } => Some(Constraint::Column { index: self.column }),
Constraint::Column { .. } => Some(Constraint::LeadingDiagonal {
index: self.leading_diagonal(side_length),
}),
Constraint::LeadingDiagonal { .. } => Some(Constraint::TrailingDiagonal {
index: self.trailing_diagonal(),
}),
Constraint::TrailingDiagonal { .. } => None,
},
)
}
}
#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub enum Constraint {
Row {
index: usize,
},
Column {
index: usize,
},
LeadingDiagonal {
index: usize,
},
TrailingDiagonal {
index: usize,
},
}
impl Constraint {
pub fn all(side_length: usize) -> impl Iterator<Item = Constraint> {
let row_it = (0..side_length).map(|index| Constraint::Row { index });
let column_it = (0..side_length).map(|index| Constraint::Column { index });
let leading_it =
(0..(2 * side_length - 1)).map(|index| Constraint::LeadingDiagonal { index });
let trailing_it =
(0..(2 * side_length - 1)).map(|index| Constraint::TrailingDiagonal { index });
row_it.chain(column_it).chain(leading_it).chain(trailing_it)
}
}
#[cfg(test)]
mod tests {
use super::*;
fn p(row: usize, column: usize) -> Possibility {
Possibility { row, column }
}
#[test]
fn check_diagonal_indices() {
let side_length = 8;
let leading_possibilities_it = (0..side_length)
.rev()
.map(|row| Possibility { row, column: 0 })
.chain((1..side_length).map(|column| Possibility { row: 0, column }));
let leading_diagonal_indices: Vec<_> = leading_possibilities_it
.map(|poss| poss.leading_diagonal(side_length))
.collect();
assert_eq!(leading_diagonal_indices, (0..15).collect::<Vec<_>>());
let trailing_possibilities_it = (0..side_length)
.map(|column| Possibility { column, row: 0 })
.chain((1..side_length).map(|row| Possibility {
row,
column: side_length - 1,
}));
let trailing_diagonal_indices: Vec<_> = trailing_possibilities_it
.map(|poss| poss.trailing_diagonal())
.collect();
assert_eq!(trailing_diagonal_indices, (0..15).collect::<Vec<_>>());
}
#[test]
fn check_tiny_boards() {
let size_one_board = NQueens::new(1, iter::empty());
let size_one_solutions = size_one_board.solver().all_solutions();
assert_eq!(size_one_solutions.len(), 1);
assert_eq!(size_one_solutions[0], vec![&p(0, 0)]);
let size_two_board = NQueens::new(2, iter::empty());
assert_eq!(size_two_board.solver().count(), 0);
let size_three_board = NQueens::new(3, iter::empty());
assert_eq!(size_three_board.solver().count(), 0);
}
#[test]
fn check_small_board() {
let queens = NQueens::new(4, iter::empty());
let mut solver = queens.solver();
let mut first_solution = solver.next().unwrap();
first_solution.sort();
assert_eq!(first_solution, vec![&p(0, 1), &p(1, 3), &p(2, 0), &p(3, 2)]);
let mut second_solution = solver.next().unwrap();
second_solution.sort();
assert_eq!(
second_solution,
vec![&p(0, 2), &p(1, 0), &p(2, 3), &p(3, 1)]
);
assert!(solver.next().is_none());
}
#[test]
#[cfg_attr(miri, ignore)] fn count_medium_board() {
let queens = NQueens::new(8, iter::empty());
assert_eq!(queens.solver().count(), 92);
}
}