use std::env;
use hashbrown::hash_map::DefaultHashBuilder;
use log::{debug, info};
use ordered_float::OrderedFloat;
use priority_queue::PriorityQueue as PQ;
use crate::{
block::{Block, Color},
board::{Board, Point},
solver::{
line::{LineSolver, UnsolvableLine},
propagation,
},
utils::{
iter::PartialEntry,
rc::{MutRc, ReadRef},
},
};
#[derive(Debug)]
pub struct ProbeImpact<C: Color> {
point: Point,
color: C,
cells_solved: Vec<(Point, C)>,
probe_priority: Priority,
}
impl<C: Color> ProbeImpact<C> {
pub fn into_tuple(self) -> (Point, C, Vec<(Point, C)>, Priority) {
(
self.point,
self.color,
self.cells_solved,
self.probe_priority,
)
}
}
#[derive(Debug, Ord, PartialOrd, Eq, PartialEq, Copy, Clone)]
pub struct Priority(pub OrderedFloat<f64>);
impl Priority {
const NEIGHBOUR_OF_NEWLY_SOLVED: Self = Self(OrderedFloat(10.0));
const NEIGHBOUR_OF_CONTRADICTION: Self = Self(OrderedFloat(20.0));
}
impl From<f64> for Priority {
fn from(val: f64) -> Self {
Self(OrderedFloat(val))
}
}
type PointImpact<C> = Vec<(C, ProbeResult<Vec<(Point, C)>>)>;
pub type Impact<B> = Vec<ProbeImpact<<B as Block>::Color>>;
type OrderedPoints = PQ<Point, Priority, DefaultHashBuilder>;
pub trait ProbeSolver {
type BlockType: Block;
fn with_board(board: MutRc<Board<Self::BlockType>>) -> Self;
fn unsolved_cells(&self) -> OrderedPoints;
fn propagate_point<S>(
&mut self,
point: &Point,
) -> Result<Vec<(Point, Priority)>, UnsolvableLine>
where
S: LineSolver<BlockType = Self::BlockType>;
fn run_unsolved<S>(&mut self) -> Result<Impact<Self::BlockType>, String>
where
S: LineSolver<BlockType = Self::BlockType>,
{
self.run::<S>(&mut self.unsolved_cells())
}
fn run<S>(&mut self, probes: &mut OrderedPoints) -> Result<Impact<Self::BlockType>, String>
where
S: LineSolver<BlockType = Self::BlockType>;
}
#[derive(Debug)]
pub struct FullProbe1<B>
where
B: Block,
{
board: MutRc<Board<B>>,
low_threshold: Priority,
propagation_solver: propagation::Solver<B>,
}
fn low_priority_threshold() -> Priority {
env::var("LOW_PRIORITY")
.ok()
.and_then(|val| val.parse().ok())
.unwrap_or(0.0)
.into()
}
impl<B> ProbeSolver for FullProbe1<B>
where
B: Block,
{
type BlockType = B;
fn with_board(board: MutRc<Board<B>>) -> Self {
let propagation_solver = propagation::Solver::with_cache(MutRc::clone(&board));
Self {
board,
low_threshold: low_priority_threshold(),
propagation_solver,
}
}
fn unsolved_cells(&self) -> OrderedPoints {
let board = self.board();
let unsolved = board.unsolved_cells();
let mut row_rate_cache = Vec::with_none(board.height());
let mut column_rate_cache = Vec::with_none(board.width());
let mut queue = OrderedPoints::with_default_hasher();
queue.extend(unsolved.map(|point| {
let no_solved = 4 - board.unsolved_neighbours(&point).count();
let row_rate =
row_rate_cache.unwrap_or_insert_with(point.y, || board.row_solution_rate(point.y));
let column_rate = column_rate_cache
.unwrap_or_insert_with(point.x, || board.column_solution_rate(point.x));
#[allow(clippy::cast_precision_loss)]
let priority = no_solved as f64 + row_rate + column_rate;
(point, priority.into())
}));
queue
}
fn propagate_point<S>(
&mut self,
point: &Point,
) -> Result<Vec<(Point, Priority)>, UnsolvableLine>
where
S: LineSolver<BlockType = B>,
{
let fixed_points = self.run_propagation::<S>(point)?;
let board = self.board();
debug!("Solution rate: {:.2}", self.board().solution_rate());
Ok(fixed_points
.into_iter()
.flat_map(|new_point| {
board
.unsolved_neighbours(&new_point)
.map(|neighbour| (neighbour, Priority::NEIGHBOUR_OF_NEWLY_SOLVED))
})
.chain(
self.board()
.unsolved_neighbours(point)
.map(|neighbour| (neighbour, Priority::NEIGHBOUR_OF_CONTRADICTION)),
)
.collect())
}
fn run<S>(&mut self, probes: &mut OrderedPoints) -> Result<Impact<Self::BlockType>, String>
where
S: LineSolver<BlockType = B>,
{
let mut contradictions_number = 0;
let impact =
loop {
let mut impact = Vec::new();
if self.is_solved() {
break impact;
}
let mut false_probes = None;
let mut probe_counter = 0_u32;
while let Some((point, priority)) = probes.pop() {
probe_counter += 1;
debug!(
"Trying probe #{} {:?} with priority {:?}",
probe_counter, point, priority
);
if priority < self.low_threshold {
impact.extend(self.board().cell(&point).variants().into_iter().map(
|color| ProbeImpact {
point,
color,
probe_priority: priority,
cells_solved: Vec::new(),
},
));
continue;
}
let probe_results = self.probe::<S>(point);
let (contradictions, non_contradictions): (Vec<_>, Vec<_>) = probe_results
.into_iter()
.partition(|(_color, res)| res.is_contradiction());
if !contradictions.is_empty() {
let bad_colors = contradictions
.into_iter()
.map(|(color, _should_be_none)| color);
false_probes = Some((point, bad_colors));
break;
}
impact.extend(non_contradictions.into_iter().map(|(color, updated)| {
ProbeImpact {
point,
color,
probe_priority: priority,
cells_solved: updated.unwrap(),
}
}));
}
if let Some((contradiction, colors)) = false_probes {
contradictions_number += 1;
for color in colors {
Board::unset_color_with_callback(&self.board, &contradiction, &color)?;
}
let new_probes = self.propagate_point::<S>(&contradiction).map_err(|err| {
format!(
"Error while propagating contradicted values in {:?}: {:?}",
contradiction, err
)
})?;
probes.extend(new_probes);
} else {
break impact;
}
};
if contradictions_number > 0 {
info!("Contradictions found: {}", contradictions_number);
}
Ok(impact)
}
}
enum ProbeResult<PropagationResult> {
Contradiction,
NewInfo(PropagationResult),
}
impl<PropagationResult> ProbeResult<PropagationResult> {
#[allow(clippy::missing_const_for_fn)]
#[allow(clippy::match_like_matches_macro)]
fn is_contradiction(&self) -> bool {
if let Self::Contradiction = self {
true
} else {
false
}
}
#[allow(clippy::missing_const_for_fn)]
fn unwrap(self) -> PropagationResult {
if let Self::NewInfo(res) = self {
return res;
}
panic!("The result is contradiction")
}
}
impl<B> FullProbe1<B>
where
B: Block,
B::Color: std::fmt::Debug,
{
fn board(&self) -> ReadRef<'_, Board<B>> {
self.board.read()
}
fn run_propagation<S>(&mut self, point: &Point) -> Result<Vec<Point>, UnsolvableLine>
where
S: LineSolver<BlockType = B>,
{
self.propagation_solver.run::<S>(Some(*point))
}
fn is_solved(&self) -> bool {
self.board().is_solved_full()
}
fn probe<S>(&mut self, point: Point) -> PointImpact<B::Color>
where
S: LineSolver<BlockType = B>,
{
if self.board().cell(&point).is_solved() {
info!("Probing expired! {:?}", point);
}
let vars = self.board().cell(&point).variants();
debug!("Probing {:?} for variants: {:?}", point, vars);
vars.into_iter()
.map(|assumption| {
let save = self.board().make_snapshot();
Board::set_color_with_callback(&self.board, &point, &assumption);
let solved = self.run_propagation::<S>(&point);
let impact = solved.ok().map_or_else(
|| {
debug!("Contradiction found! {:?}: {:?}", point, assumption);
ProbeResult::Contradiction
},
|new_cells| {
let new_cells: Vec<_> = new_cells
.into_iter()
.map(|point| (point, self.board().cell(&point)))
.collect();
if !new_cells.is_empty() {
debug!(
"Probing {:?}: {:?} brings some new info: {:?}",
point, assumption, new_cells
);
}
ProbeResult::NewInfo(new_cells)
},
);
Board::restore_with_callback(&self.board, save);
(assumption, impact)
})
.collect()
}
}