Flow Free solver in Rust

main.rs

use std::{
    collections::{HashMap, LinkedList},
    vec,
};

pub const E: &str = "-";
pub const X: &str = "X";

pub fn solve(panel: &Panel) -> Panel {
    let all_pairs = panel.source_target_pairs();
    let mut states: Vec<SearchState> = vec![SearchState::new(all_pairs, panel.clone())];

    while !states.is_empty() {
        let mut state = states.pop().unwrap();

        //println!("candidates={} >>>>>>>>>>>>>>>>>>>", states.len() + 1);
        //state.panel.print();

        // validate state
        if !is_valid_state(&state) {
            continue;
        }

        //let mut stdin = std::io::stdin();
        //let _ = std::io::Read::read(&mut stdin, &mut [0u8]).unwrap();

        // apply rules for creating next states
        let mut state_new = (state.clone(), proceed_by_following_rules(&mut state));
        while state_new.1.is_some() {
            state_new.0 = state_new.1.clone().unwrap();
            state_new.1 = proceed_by_following_rules(&mut state_new.1.unwrap());
        }
        let mut state = state_new.0;

        // check if the problem is already solved
        if state.active_pairs.is_empty() {
            return state.panel;
        }

        // expand states
        let p = next_target(&state);
        for n in p.around(state.panel.height, state.panel.width) {
            if state.panel.value(&n) != E {
                continue;
            }
            let state_new = state.proceed(n, p);
            states.push(state_new);
        }
    }
    todo!("something wrong");
}

// returns a point that have the least options to proceed.
fn next_target(state: &SearchState) -> P {
    let mut count: i64 = std::i64::MAX;
    let mut point: Option<P> = None;
    for p in state.active_points() {
        let mut c = 0;
        for n in p.around(state.panel.height, state.panel.width) {
            if state.panel.value(&n) == E {
                c += 1;
            }
        }
        if c < count {
            count = c;
            point = Some(p);
        }
    }
    return point.unwrap();
}

fn proceed_by_following_rules(state: &mut SearchState) -> Option<SearchState> {
    let s = apply_proceed_rule1(state);
    if s.is_some() {
        return s;
    }
    let s = apply_proceed_rule2(state);
    if s.is_some() {
        return s;
    }
    let s = apply_proceed_rule3(state);
    if s.is_some() {
        return s;
    }

    // 1/4 rotation
    let mut state = state.rotate();
    let s = apply_proceed_rule1(&mut state);
    if s.is_some() {
        return Some(s.unwrap().rotate().rotate().rotate());
    }
    let s = apply_proceed_rule2(&mut state);
    if s.is_some() {
        return Some(s.unwrap().rotate().rotate().rotate());
    }

    // 2/4 rotation
    let mut state = state.rotate();
    let s = apply_proceed_rule1(&mut state);
    if s.is_some() {
        return Some(s.unwrap().rotate().rotate());
    }
    let s = apply_proceed_rule2(&mut state);
    if s.is_some() {
        return Some(s.unwrap().rotate().rotate());
    }

    // 3/4 rotattion
    let mut state = state.rotate();
    let s = apply_proceed_rule1(&mut state);
    if s.is_some() {
        return Some(s.unwrap().rotate());
    }
    let s = apply_proceed_rule2(&mut state);
    if s.is_some() {
        return Some(s.unwrap().rotate());
    }

    None
}

///   B'        B'
/// A _ C' => A A C'
fn apply_proceed_rule1(state: &mut SearchState) -> Option<SearchState> {
    for x in 0..state.panel.height {
        for y in 0..state.panel.width {
            if state.panel.values[x][y] != E {
                continue;
            }
            let c = P::new(x, y);
            let l = c.left();
            let u = c.up();
            let r = c.right(state.panel.width);

            if state.is_active_cell(l) && state.is_fixed_cell(u) && state.is_fixed_cell(r) {
                return Some(state.proceed(c, l.unwrap()));
            }
            if state.is_fixed_cell(l) && state.is_active_cell(u) && state.is_fixed_cell(r) {
                return Some(state.proceed(c, u.unwrap()));
            }
            if state.is_fixed_cell(l) && state.is_fixed_cell(u) && state.is_active_cell(r) {
                return Some(state.proceed(c, r.unwrap()));
            }
        }
    }
    return None;
}

///   B' C'         B' C'
/// A _  _  D' => A A  A  D'
fn apply_proceed_rule2(state: &mut SearchState) -> Option<SearchState> {
    for x in 0..state.panel.height {
        for y in 0..state.panel.width - 1 {
            if state.panel.values[x][y] != E || state.panel.values[x][y + 1] != E {
                continue;
            }
            let c1 = P::new(x, y);
            let c2 = P::new(x, y + 1);
            let l = c1.left();
            let u1 = c1.up();
            let u2 = c2.up();
            let r = c2.right(state.panel.width);

            if state.is_active_cell(l)
                && state.is_fixed_cell(u1)
                && state.is_fixed_cell(u2)
                && state.is_fixed_cell(r)
            {
                return Some(state.proceed(c1, l.unwrap()).proceed(c2, c1));
            }
            if state.is_fixed_cell(l)
                && state.is_active_cell(u1)
                && state.is_fixed_cell(u2)
                && state.is_fixed_cell(r)
            {
                return Some(state.proceed(c1, u1.unwrap()).proceed(c2, c1));
            }
            if state.is_fixed_cell(l)
                && state.is_fixed_cell(u1)
                && state.is_active_cell(u2)
                && state.is_fixed_cell(r)
            {
                return Some(state.proceed(c2, u2.unwrap()).proceed(c1, c2));
            }
            if state.is_fixed_cell(l)
                && state.is_fixed_cell(u1)
                && state.is_fixed_cell(u2)
                && state.is_active_cell(r)
            {
                return Some(state.proceed(c2, r.unwrap()).proceed(c1, c2));
            }
        }
    }
    return None;
}

/// if a cell is useful only for one path, then proceed deterministically
fn apply_proceed_rule3(state: &mut SearchState) -> Option<SearchState> {
    for p in state.active_points() {
        let mut e_around = (0, None);
        for n in p.around(state.panel.height, state.panel.width) {
            if state.panel.value(&n) == E {
                e_around.0 += 1;
                e_around.1 = Some(n);
            }
        }
        if e_around.0 == 1 {
            let n = e_around.1.unwrap();
            state.panel.values[n.x][n.y] = X; // put an obstacle temporally
            match state.unreachable_path() {
                // if unreachable path exists
                Some((s, t)) => {
                    state.panel.values[n.x][n.y] = E; // remove the obstacle
                    if p == s || p == t {
                        return Some(state.proceed(n, p));
                    }
                }
                None => {
                    state.panel.values[n.x][n.y] = E;
                }
            }
        }
    }
    return None;
}

fn is_valid_state(state: &SearchState) -> bool {
    if !ok_validation_rule1(state) {
        return false;
    }

    // 0/4 rotation
    if !(ok_validation_rule2(state) && ok_validation_rule3(&state)) {
        return false;
    }

    // 1/4 rotation
    let mut state = state.rotate();
    if !(ok_validation_rule2(&mut state) && ok_validation_rule3(&state)) {
        return false;
    }

    // 2/4 rotation
    let mut state = state.rotate();
    if !(ok_validation_rule2(&mut state) && ok_validation_rule3(&state)) {
        return false;
    }

    // 3/4 rotattion
    let mut state = state.rotate();
    if !(ok_validation_rule2(&mut state) && ok_validation_rule3(&state)) {
        return false;
    }

    // other checking
    if state.unreachable_path().is_some() {
        return false;
    }
    return true;
}

/// A A
/// A A
fn ok_validation_rule1(state: &SearchState) -> bool {
    for x in 0..state.panel.height - 1 {
        for y in 0..state.panel.width - 1 {
            let c = P::new(x, y);
            if state.panel.value(&c) == E {
                continue;
            }

            let r = c.right(state.panel.width).unwrap();
            let d = c.down(state.panel.height).unwrap();
            let rd = r.down(state.panel.height).unwrap();

            let v_c = state.panel.value(&c);
            let v_r = state.panel.value(&r);
            let v_d = state.panel.value(&d);
            let v_rd = state.panel.value(&rd);

            if v_c == v_r && v_c == v_d && v_c == v_rd {
                return false;
            }
        }
    }
    return true;
}

///   B
/// A X C
fn ok_validation_rule2(state: &SearchState) -> bool {
    for x in 0..state.panel.height {
        for y in 0..state.panel.width {
            let c = P::new(x, y);
            if state.panel.value(&c) != E {
                continue;
            }
            if state.is_fixed_cell(c.left())
                && state.is_fixed_cell(c.up())
                && state.is_fixed_cell(c.right(state.panel.width))
            {
                return false;
            }
        }
    }
    return true;
}

///   B C
/// A X X D
fn ok_validation_rule3(state: &SearchState) -> bool {
    for x in 0..state.panel.height - 1 {
        for y in 0..state.panel.width - 1 {
            if state.panel.values[x][y] != E || state.panel.values[x][y + 1] != E {
                continue;
            }
            let c1 = P::new(x, y);
            let c2 = P::new(x, y + 1);
            let l = c1.left();
            let u1 = c1.up();
            let u2 = c2.up();
            let r = c2.right(state.panel.width);

            if state.is_fixed_cell(l)
                && state.is_fixed_cell(u1)
                && state.is_fixed_cell(u2)
                && state.is_fixed_cell(r)
            {
                return false;
            }
        }
    }
    return true;
}

#[derive(Eq, PartialEq, Clone)]
pub struct SearchState {
    active_pairs: Vec<(P, P)>,
    panel: Panel,
}

impl SearchState {
    fn new(active_pairs: Vec<(P, P)>, panel: Panel) -> SearchState {
        SearchState {
            active_pairs: active_pairs,
            panel: panel,
        }
    }

    fn active_points(&self) -> Vec<P> {
        let mut ps: Vec<P> = vec![];
        for (s, t) in &self.active_pairs {
            ps.push(*s);
            ps.push(*t);
        }
        return ps;
    }

    fn proceed(&mut self, to: P, from: P) -> SearchState {
        let mut pairs_updated: Vec<(P, P)> = vec![];
        for (s, t) in &self.active_pairs {
            if *s == from {
                // when connected, ignore the path.
                if !to.around(self.panel.height, self.panel.width).contains(t) {
                    pairs_updated.push((to, *t));
                }
            } else if *t == from {
                if !to.around(self.panel.height, self.panel.width).contains(s) {
                    pairs_updated.push((*s, to));
                }
            } else {
                pairs_updated.push((*s, *t));
            }
        }
        let mut panel_updated = self.panel.clone();
        panel_updated.copy_value(&from, &to);
        SearchState::new(pairs_updated, panel_updated)
    }

    fn rotate(&self) -> SearchState {
        let mut pairs_rotated: Vec<(P, P)> = vec![];
        for (p1, p2) in &self.active_pairs {
            pairs_rotated.push((
                P::new(self.panel.width - 1 - p1.y, p1.x),
                P::new(self.panel.width - 1 - p2.y, p2.x),
            ));
        }
        let panel_rotated = self.panel.rotate();
        SearchState::new(pairs_rotated, panel_rotated)
    }

    pub fn unreachable_path(&self) -> Option<(P, P)> {
        for (s, t) in &self.active_pairs {
            if !&self.panel.is_reachable(*s, *t) {
                return Some((*s, *t));
            }
        }
        return None;
    }

    fn is_fixed_cell(&self, p: Option<P>) -> bool {
        match p {
            None => true,
            Some(p) => {
                if self.panel.value(&p) == E {
                    return false;
                }
                for a in &self.active_points() {
                    if p == *a {
                        return false;
                    }
                }
                true
            }
        }
    }

    fn is_active_cell(&self, p: Option<P>) -> bool {
        match p {
            None => false,
            Some(p) => {
                for a in &self.active_points() {
                    if p == *a {
                        return true;
                    }
                }
                false
            }
        }
    }
}

#[derive(Clone, PartialEq, Eq)]
pub struct Panel {
    width: usize,
    height: usize,
    values: Vec<Vec<&'static str>>,
}

impl Panel {
    pub fn value(&self, p: &P) -> &'static str {
        self.values[p.x][p.y]
    }

    pub fn neighbors(&self, p: P) -> Vec<P> {
        p.around(self.height, self.width).into_iter().collect()
    }

    pub fn copy_value(&mut self, from: &P, to: &P) {
        self.values[to.x][to.y] = self.value(&from);
    }

    pub fn rotate(&self) -> Panel {
        let mut vs = vec![];
        for y in (0..self.width).rev() {
            let mut v = vec![];
            for x in 0..self.height {
                v.push(self.value(&P::new(x, y)));
            }
            vs.push(v);
        }
        Panel {
            width: self.height,
            height: self.width,
            values: vs,
        }
    }

    fn source_target_pairs(&self) -> Vec<(P, P)> {
        let mut map: HashMap<&str, Vec<P>> = HashMap::new();
        for x in 0..self.height {
            for y in 0..self.width {
                let v = self.values[x][y];
                if v == E {
                    continue;
                }
                map.entry(v).or_insert(vec![]).push(P::new(x, y));
            }
        }
        let mut pairs: Vec<(P, P)> = vec![];
        for (_, points) in map.into_iter() {
            assert!(points.len() == 2, "illgal panel!");
            pairs.push((points[0], points[1]));
        }
        // just for making the resulting order stable
        pairs.sort_by_key(|(s, t)| s.x.abs_diff(t.x) + s.y.abs_diff(t.y));
        return pairs;
    }

    pub fn is_reachable(&self, source: P, target: P) -> bool {
        self.shortest_dist(source, target).is_some()
    }

    // dijkstra's algorithm
    pub fn shortest_dist(&self, source: P, target: P) -> Option<usize> {
        let mut costs: HashMap<P, i64> = HashMap::new();
        costs.insert(source, 0);
        let mut queue: LinkedList<P> = LinkedList::new();
        queue.push_back(source);

        while !queue.is_empty() {
            let p = queue.pop_front().unwrap();
            if p == target {
                return Some(costs[&p] as usize);
            }
            for n in self.neighbors(p) {
                // ignore illegal paths
                if self.value(&n) != E && n != target {
                    continue;
                }
                // update the cost of newly found points
                let current_cost = costs[&p] + 1;
                match costs.get(&n) {
                    None => {
                        costs.insert(n, current_cost);
                        queue.push_back(n);
                    }
                    Some(&cost_n) => {
                        if current_cost < cost_n {
                            costs.insert(n, current_cost);
                            queue.push_back(n);
                        }
                    }
                }
            }
        }
        return None;
    }

    pub fn print(&self) {
        for x in 0..self.height {
            for y in 0..self.width {
                let v = self.values[x][y];
                print!("{:02}", v);
            }
            println!()
        }
    }
}

/// Point class
#[derive(PartialEq, Eq, Hash, Clone, Copy)]
pub struct P {
    x: usize,
    y: usize,
}

impl std::fmt::Debug for P {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "({}, {})", self.x, self.y)
    }
}

impl P {
    fn new(x: usize, y: usize) -> P {
        P { x: x, y: y }
    }

    fn around(&self, height: usize, width: usize) -> Vec<P> {
        vec![self.up(), self.down(height), self.left(), self.right(width)]
            .into_iter()
            .flatten()
            .collect()
    }

    fn up(&self) -> Option<P> {
        if self.x >= 1 {
            Some(P::new(self.x - 1, self.y))
        } else {
            None
        }
    }

    fn down(&self, height: usize) -> Option<P> {
        if self.x + 1 < height {
            Some(P::new(self.x + 1, self.y))
        } else {
            None
        }
    }

    fn left(&self) -> Option<P> {
        if self.y >= 1 {
            Some(P::new(self.x, self.y - 1))
        } else {
            None
        }
    }

    fn right(&self, width: usize) -> Option<P> {
        if self.y + 1 < width {
            Some(P::new(self.x, self.y + 1))
        } else {
            None
        }
    }
}

fn main() {
    let panel = panel7();
    panel.print();
    let solution = solve(&panel);
    println!("-----------------------");
    solution.print();
}

#[allow(dead_code)]
fn panel1() -> Panel {
    Panel {
        width: 5,
        height: 5,
        values: vec![
            vec!["1", "2", "3", E, E],
            vec![E, E, E, E, E],
            vec![E, "1", "4", E, E],
            vec![E, E, E, E, E],
            vec!["4", "2", E, E, "3"],
        ],
    }
}

#[allow(dead_code)]
fn panel2() -> Panel {
    Panel {
        width: 10,
        height: 10,
        values: vec![
            vec!["1", E, E, E, E, E, E, E, E, E],
            vec![E, E, E, E, E, "2", E, E, "2", E],
            vec![E, E, E, E, "3", E, E, E, E, E],
            vec![E, "1", "4", E, E, E, E, E, E, E],
            vec![E, E, E, E, E, E, E, "5", E, E],
            vec![E, E, E, E, E, E, E, E, E, "6"],
            vec![E, E, E, E, E, "7", "5", E, E, E],
            vec![E, E, E, "8", E, E, E, E, "8", E],
            vec![E, E, "6", "7", E, "4", E, E, E, E],
            vec!["3", E, E, E, E, E, "9", E, E, "9"],
        ],
    }
}

#[allow(dead_code)]
fn panel3() -> Panel {
    Panel {
        width: 14,
        height: 14,
        values: vec![
            vec![E, E, E, E, "A", E, E, E, E, E, E, E, E, E],
            vec![E, E, E, E, E, E, E, E, E, E, E, E, E, E],
            vec![E, E, E, E, E, E, E, "B", E, E, E, E, E, E],
            vec![E, E, "C", E, E, "D", "E", "F", E, E, "G", E, E, E],
            vec![E, E, E, "D", "E", E, E, E, E, E, E, E, E, E],
            vec![E, E, E, E, E, E, E, E, "B", E, E, E, E, E],
            vec!["H", E, "I", E, E, E, E, E, "I", E, E, E, E, E],
            vec![E, E, E, "J", E, E, E, E, "J", E, E, E, E, E],
            vec![E, E, E, E, E, E, E, "A", E, E, E, E, E, E],
            vec!["K", E, E, E, E, E, E, E, E, E, E, E, E, E],
            vec![E, E, E, "L", E, E, "K", E, "G", E, "M", E, E, E],
            vec![E, E, E, E, "N", E, "M", E, "F", E, "C", E, E, E],
            vec![E, E, "H", E, E, E, E, E, "L", E, E, E, E, E],
            vec![E, E, E, E, E, E, E, E, "N", "O", E, E, E, "O"],
        ],
    }
}

#[allow(dead_code)]
fn panel4() -> Panel {
    Panel {
        width: 10,
        height: 10,
        values: vec![
            vec![E, E, E, E, E, E, E, E, E, E],
            vec![E, E, "A", E, E, E, E, E, "B", E],
            vec![E, E, E, E, E, E, E, E, E, E],
            vec![E, E, E, E, E, E, E, E, E, "C"],
            vec![E, E, E, E, E, E, E, E, E, "D"],
            vec!["E", E, E, E, E, E, E, E, E, "F"],
            vec!["D", E, E, E, E, E, "C", E, E, E],
            vec![E, E, E, E, E, E, E, E, E, E],
            vec![E, "A", "E", E, E, E, E, E, "B", E],
            vec![E, E, E, E, "F", E, E, E, E, E],
        ],
    }
}

#[allow(dead_code)]
fn panel5() -> Panel {
    Panel {
        width: 12,
        height: 12,
        values: vec![
            vec![E, E, E, E, "A", E, E, E, E, E, E, E],
            vec![E, "B", E, E, E, E, E, E, E, E, E, E],
            vec![E, E, E, E, E, "C", "D", "E", E, E, E, E],
            vec!["F", E, "G", E, E, E, E, E, E, E, E, E],
            vec!["H", E, E, E, E, "A", E, "I", E, E, E, E],
            vec![E, "F", E, E, E, E, E, "J", E, "E", E, E],
            vec![E, E, E, E, "J", E, E, E, E, E, E, E],
            vec![E, "G", "K", E, "I", "L", E, "K", E, E, E, E],
            vec![E, "H", E, E, E, E, E, "L", E, E, E, E],
            vec![E, E, E, E, "M", E, E, E, E, E, E, E],
            vec!["M", E, E, E, E, E, E, E, E, E, "D", E],
            vec!["B", E, "C", E, E, E, E, E, E, E, E, E],
        ],
    }
}

#[allow(dead_code)]
fn panel6() -> Panel {
    Panel {
        width: 13,
        height: 13,
        values: vec![
            vec!["A", E, "A", "B", "C", E, E, E, E, E, E, E, "D"],
            vec![E, "E", E, E, E, E, "F", E, E, E, "G", E, E],
            vec![E, E, E, E, E, E, E, E, "H", E, E, E, E],
            vec![E, E, E, E, E, E, E, "I", E, E, "G", "J", E],
            vec![E, E, E, E, E, "K", E, E, E, "D", E, E, E],
            vec![E, E, E, E, E, E, E, E, E, "F", E, E, E],
            vec![E, E, E, E, E, E, E, E, "L", E, E, "M", E],
            vec![E, E, E, "J", E, E, "N", E, E, E, E, E, E],
            vec![E, E, E, "C", E, E, E, "E", "I", "L", E, E, E],
            vec![E, E, E, E, E, E, E, E, E, E, E, E, E],
            vec![E, E, "K", E, "B", E, E, "M", E, E, E, E, E],
            vec![E, E, E, E, "H", E, E, E, E, E, E, "N", E],
            vec![E, E, E, E, E, E, E, E, E, E, E, E, E],
        ],
    }
}

#[allow(dead_code)]
fn panel7() -> Panel {
    Panel {
        width: 13,
        height: 13,
        values: vec![
            vec![E, E, E, E, E, E, E, E, E, E, E, E, E],
            vec![E, E, E, E, E, E, E, E, E, E, E, E, E],
            vec![E, E, E, E, E, E, E, "A", E, E, E, E, E],
            vec![E, "B", E, E, E, E, E, E, E, "C", E, E, E],
            vec!["D", E, E, E, "E", E, E, E, E, E, E, E, E],
            vec!["F", E, E, E, E, E, E, E, E, E, E, E, E],
            vec![E, E, "G", E, E, "G", E, E, E, E, E, E, E],
            vec![E, E, "A", E, "B", E, E, E, E, E, E, E, E],
            vec![E, "C", E, E, "H", E, E, E, "E", E, E, E, E],
            vec![E, E, E, E, E, E, E, E, E, E, E, E, E],
            vec![E, E, "I", E, "I", E, E, E, E, E, E, E, E],
            vec![E, E, E, E, "H", E, E, E, E, E, E, E, E],
            vec![E, E, E, E, E, "F", "D", E, E, E, E, E, E],
        ],
    }
}

#[cfg(test)]
mod tests {
    use crate::{ok_validation_rule1, panel1, panel3, solve, Panel, SearchState, P};

    #[test]
    pub fn test_astar_is_reachable() {
        let panel = panel1();
        panel.print();
        let result = panel.is_reachable(P::new(0, 1), P::new(4, 1));
        assert_eq!(result, true);
    }

    #[test]
    pub fn test_unreachble_path() {
        let panel = panel3();
        panel.print();
        let state = SearchState::new(panel.source_target_pairs(), panel);
        assert_eq!(state.unreachable_path().is_none(), true);
    }

    #[test]
    pub fn test_rotate1() {
        let panel = Panel {
            width: 4,
            height: 2,
            values: vec![
                vec!["-", "1", "2", "3"], //
                vec!["1", "2", "-", "3"],
            ],
        };
        panel.print();
        let p = panel.rotate();
        p.print();
        println!("{:?}", p.source_target_pairs());
    }

    #[test]
    pub fn test_rotate2() {
        let panel = Panel {
            width: 4,
            height: 4,
            values: vec![
                vec!["-", "-", "-", "1"], //
                vec!["-", "2", "3", "4"], //
                vec!["1", "-", "-", "4"], //
                vec!["2", "-", "-", "3"], //
            ],
        };
        panel.print();
        let p = panel.rotate();
        p.print();
        println!("{:?}", p.source_target_pairs());
    }

    #[test]
    pub fn test_proceed() {
        let panel = Panel {
            width: 3,
            height: 3,
            values: vec![
                vec!["-", "1", "3"],
                vec!["1", "2", "-"],
                vec!["2", "-", "3"],
            ],
        };
        let state = SearchState::new(panel.source_target_pairs(), panel);
        state.panel.print();
        println!("--------");
        let mut state = state.rotate();
        let state = state.proceed(P::new(2, 0), P::new(1, 0));
        state.panel.print();
        println!("{:?}", state.active_pairs);
    }

    #[test]
    pub fn test_rule1() {
        let panel = Panel {
            width: 3,
            height: 3,
            values: vec![
                vec!["-", "1", "3"],
                vec!["1", "2", "-"],
                vec!["2", "-", "3"],
            ],
        };
        solve(&panel);
    }

    #[test]
    pub fn test_validate1() {
        let state = SearchState::new(
            vec![],
            Panel {
                width: 4,
                height: 4,
                values: vec![
                    vec!["1", "-", "-", "1"],
                    vec!["1", "1", "3", "4"],
                    vec!["3", "-", "4", "4"],
                    vec!["4", "-", "4", "4"],
                ],
            },
        );
        assert_eq!(ok_validation_rule1(&state), false);
    }
}