#![deny(missing_docs)]
pub use quickbacktrack::*;
pub type Color = u64;
pub const EMPTY_EDGE: Color = 0;
pub const DISCONNECTED_EDGE: Color = 1;
#[derive(Clone, Debug)]
pub struct Graph {
pub nodes: Vec<Node>,
pub edges: Vec<Vec<Color>>,
pub pairs: Vec<(usize, usize)>,
pub no_triangles: bool,
pub meet_quad: bool,
pub connected: bool,
cache_has_triangles: std::cell::Cell<bool>,
cache_upper_triangle_disconnected: std::cell::Cell<bool>,
cache_node_satisfied: Vec<std::cell::Cell<bool>>,
}
impl Puzzle for Graph {
type Pos = (usize, usize);
type Val = Color;
fn set(&mut self, (i, j): (usize, usize), val: Color) {
if j <= i {self.edges[i][j] = val} else {self.edges[j][i] = val}
self.cache_has_triangles.set(false);
self.cache_upper_triangle_disconnected.set(false);
self.cache_node_satisfied[i].set(false);
self.cache_node_satisfied[j].set(false);
}
fn get(&self, (i, j): (usize, usize)) -> Color {
if j <= i {self.edges[i][j]} else {self.edges[j][i]}
}
fn print(&self) {
for i in 0..self.nodes.len() {
eprint!("{} ", self.nodes[i].color);
}
eprintln!("\n========================================");
for i in 0..self.nodes.len() {
for j in 0..self.nodes.len() {
eprint!("{} ", self.get((i, j)));
}
eprintln!("");
}
}
fn solve_simple<F: FnMut(&mut Self, Self::Pos, Self::Val)>(&mut self, mut f: F) {
let n = self.nodes.len();
for i in 0..n {
for j in i+1..n {
let colors = self.colors((i, j));
if colors.len() == 1 {
f(self, (i, j), colors[0]);
}
}
}
}
fn is_solved(&self) -> bool {
self.all_satisfied() &&
self.pairs_satisfied() &&
if self.no_triangles {!self.has_triangles()} else {true} &&
if self.meet_quad {self.meet_quad_satisfied()} else {true} &&
if self.connected {self.is_connected()} else {true}
}
fn remove(&mut self, other: &Graph) {
let n = self.nodes.len();
for i in 0..n {
for j in i..n {
if other.get((i, j)) != 0 {
self.set((i, j), 0);
}
}
}
}
}
impl Default for Graph {
fn default() -> Graph {Graph::new()}
}
impl Graph {
pub fn new() -> Graph {
Graph {
nodes: vec![],
edges: vec![],
pairs: vec![],
no_triangles: false,
meet_quad: false,
connected: false,
cache_has_triangles: std::cell::Cell::new(false),
cache_upper_triangle_disconnected: std::cell::Cell::new(false),
cache_node_satisfied: vec![],
}
}
pub fn graphviz(&self, layout: &str, node_colors: &[&str], edge_colors: &[&str]) -> String {
use std::fmt::Write;
let mut s = String::new();
writeln!(&mut s, "strict graph {{").unwrap();
writeln!(&mut s, " layout={}; edge[penwidth=4]", layout).unwrap();
for i in 0..self.nodes.len() {
writeln!(&mut s, " {}[regular=true,style=filled,fillcolor={}];", i,
node_colors[self.nodes[i].color as usize % node_colors.len()]).unwrap();
}
for i in 0..self.nodes.len() {
for (j, &ed) in self.edges[i].iter().enumerate() {
if ed < 2 {continue};
writeln!(&mut s, " {} -- {}[color={}];", i, j,
edge_colors[(ed - 2) as usize % edge_colors.len()]).unwrap();
}
}
writeln!(&mut s, "}}").unwrap();
s
}
pub fn fst_empty(&self) -> Option<(usize, usize)> {
let n = self.nodes.len();
for i in 0..n {
for j in i..n {
let s = self.colors((i, j)).len();
if s == 0 {continue};
if self.get((i, j)) == 0 {
return Some((i, j));
}
}
}
None
}
pub fn min_colors(&self) -> Option<(usize, usize)> {
let mut min: Option<(usize, usize, usize)> = None;
let n = self.nodes.len();
'outer: for i in 0..n {
for j in i..n {
let s = self.colors((i, j)).len();
if s == 0 {continue};
if min.is_none() || min.unwrap().2 > s {
min = Some((i, j, s));
if s == 1 {break 'outer}
}
}
}
min.map(|n| (n.0, n.1))
}
pub fn solve(self, solve_settings: SolveSettings) -> Option<Solution<Graph>> {
let solver = BackTrackSolver::new(self, solve_settings);
solver.solve(
Graph::min_colors,
Graph::colors
)
}
pub fn push(&mut self, node: Node) {
self.nodes.push(node);
self.edges.push(vec![0; self.nodes.len()]);
self.cache_node_satisfied.push(std::cell::Cell::new(false));
}
pub fn push_pair(&mut self, (i, j): (usize, usize)) {
self.pairs.push((i.min(j), i.max(j)));
}
pub fn node_satisfied(&self, i: usize) -> Vec<Constraint> {
if self.cache_node_satisfied[i].get() {return vec![]};
let mut res = vec![];
let mut m = vec![false; self.nodes[i].edges.len()];
for j in 0..self.nodes.len() {
let edge = self.get((i, j));
if edge == 0 {continue};
for k in 0..m.len() {
if m[k] {continue};
let con = &self.nodes[i].edges[k];
if con.edge == edge &&
con.node == self.nodes[j].color
{
m[k] = true;
break;
}
}
}
for k in 0..m.len() {
if !m[k] {
res.push(self.nodes[i].edges[k].clone());
}
}
if res.len() == 0 {
self.cache_node_satisfied[i].set(true);
}
res
}
pub fn all_satisfied(&self) -> bool {
for i in 0..self.nodes.len() {
if self.node_satisfied(i).len() != 0 {return false}
}
true
}
pub fn pairs_satisfied(&self) -> bool {
for &(i, j) in &self.pairs {
if self.edges[j][i] < 2 {return false}
}
true
}
pub fn has_triangles(&self) -> bool {
if self.cache_has_triangles.get() {return true};
let n = self.nodes.len();
for i in 0..n {
for j in i+1..n {
if self.get((i, j)) < 2 {continue};
for k in j+1..n {
if self.get((j, k)) >= 2 &&
self.get((i, k)) >= 2
{
self.cache_has_triangles.set(true);
return true
}
}
}
}
false
}
pub fn meet_quad_satisfied(&self) -> bool {
let n = self.nodes.len();
for i in 0..n {
let mut found = false;
'outer: for j in 0..n {
if i == j {continue};
if self.get((i, j)) < 2 {continue};
for k in j+1..n {
if k == i {continue};
if self.get((j, k)) < 2 &&
self.get((i, k)) < 2 {continue};
if self.get((j, k)) >= 2 &&
self.get((i, k)) >= 2 {
found = true;
break 'outer;
}
for k2 in 0..n {
if k2 == i || k2 == j || k2 == k {continue};
if self.get((k, k2)) >= 2 &&
(
self.get((j, k)) >= 2 &&
self.get((i, k2)) >= 2 ||
self.get((i, k)) >= 2 &&
self.get((j, k2)) >= 2
)
{
found = true;
break 'outer;
}
}
}
}
if !found {
return false
}
}
true
}
pub fn is_connected(&self) -> bool {
let n = self.nodes.len();
let mut reachable = vec![false; n];
for i in 0..n {
if self.get((0, i)) >= 2 {
reachable[i] = true;
}
}
loop {
let mut changed = false;
for i in 0..n {
if !reachable[i] {
for j in 0..n {
if reachable[j] && self.get((i, j)) >= 2 {
reachable[i] = true;
changed = true;
break;
}
}
}
}
if !changed {break}
}
reachable.iter().all(|&b| b)
}
pub fn is_upper_right_disconnected(&self) -> bool {
if self.cache_upper_triangle_disconnected.get() {return true};
let n = self.nodes.len();
if n % 2 != 0 {return false}
for i in 0..n/2 {
for j in n/2..n {
if i == j {continue}
if self.get((i, j)) != 1 {return false}
}
}
self.cache_upper_triangle_disconnected.set(true);
true
}
pub fn colors(&self, (i, j): (usize, usize)) -> Vec<Color> {
if self.get((i, j)) != 0 {return vec![]};
if !self.nodes[i].self_connected && i == j {return vec![]};
if self.no_triangles && self.has_triangles() {return vec![]};
if self.connected && self.is_upper_right_disconnected() {return vec![]};
let mut res = vec![];
let errors = self.node_satisfied(i);
let other_errors = self.node_satisfied(j);
for err in &errors {
if err.node != self.nodes[j].color {continue}
for other_err in &other_errors {
if err.edge == other_err.edge &&
other_err.node == self.nodes[i].color
{
res.push(err.edge);
break;
}
}
}
res.push(1);
res.sort();
res.dedup();
res
}
}
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub struct Constraint {
pub edge: Color,
pub node: Color,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Node {
pub color: Color,
pub self_connected: bool,
pub edges: Vec<Constraint>,
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn simple1() {
let mut g = Graph::new();
let a = Node {
color: 1,
self_connected: false,
edges: vec![Constraint {edge: 2, node: 1}],
};
assert_eq!(g.nodes.len(), 0);
g.push(a.clone());
assert_eq!(g.node_satisfied(0), vec![
Constraint {edge: 2, node: 1}
]);
g.push(a.clone());
assert_eq!(g.node_satisfied(0), vec![
Constraint {edge: 2, node: 1}
]);
assert_eq!(g.node_satisfied(1), vec![
Constraint {edge: 2, node: 1}
]);
assert_eq!(g.colors((0, 1)), vec![1, 2]);
g.set((0, 1), 2);
assert_eq!(g.node_satisfied(0), vec![]);
g.set((0, 1), 2);
assert!(g.all_satisfied());
}
}