extern crate itertools;
use itertools::Itertools;

#[derive(Debug)]
struct Problem {
    cells: Vec<(usize, usize, char)>,
}

impl Problem {
    fn new(cells: &[(usize, usize, char)]) -> Problem {
        Problem {
            cells: cells.to_vec(),
        }
    }
}

#[derive(Debug)]
struct PartialSolution {
    cell_values: Vec<(usize, usize, char)>,
    empty_cells: Vec<(usize, usize)>,
}

fn root(problem: &Problem) -> PartialSolution {
    let fixed_cells = problem
        .cells
        .iter()
        .map(|&(i, j, _)| (i, j))
        .collect::<Vec<_>>();
    PartialSolution {
        cell_values: Vec::new(),
        empty_cells: (0..9)
            .cartesian_product(0..9)
            .filter(|x| !fixed_cells.contains(x))
            .collect::<Vec<_>>(),
    }
}

mod rule {
    pub enum RuleType {
        Row(usize),
        Column(usize),
        Square(usize, usize),
    }

    pub fn create_rule(rule: RuleType) -> Vec<(usize, usize)> {
        use itertools::Itertools;
        match rule {
            RuleType::Row(i) => (0..9).map(|j| (i, j)).collect::<Vec<(usize, usize)>>(),
            RuleType::Column(j) => (0..9).map(|i| (i, j)).collect::<Vec<(usize, usize)>>(),
            RuleType::Square(x, y) => (3 * x..3 * (x + 1))
                .cartesian_product(3 * y..3 * (y + 1))
                .collect::<Vec<(usize, usize)>>(),
        }
    }

    pub fn mask(cells: &[(usize, usize, char)], rule: &[(usize, usize)]) -> Vec<char> {
        use std::collections::HashMap;
        let cell_hash = cells
            .iter()
            .map(|&(x, y, z)| ((x, y), z))
            .collect::<HashMap<(usize, usize), char>>();
        rule.iter()
            .filter_map(|x| cell_hash.get(x))
            .map(|x| *x)
            .collect::<Vec<char>>()
    }

    pub fn contains_duplicates<T>(xs: &[T]) -> bool
    where
        T: PartialEq,
    {
        match xs.split_first() {
            Some((y, ys)) => ys.contains(y) || contains_duplicates(ys),
            None => false,
        }
    }

    pub fn check(cells: &[(usize, usize, char)], rule: &[(usize, usize)]) -> bool {
        //true if it passes, false otherwise
        !contains_duplicates(&mask(cells, rule))
    }
}

fn reject(problem: &Problem, candidate: PartialSolution) -> bool {
    let all_rules = (0..9)
        .map(|x| rule::RuleType::Row(x))
        .chain((0..9).map(|x| rule::RuleType::Column(x)))
        .chain(
            (0..3)
                .cartesian_product(0..3)
                .map(|(x, y)| rule::RuleType::Square(x, y)),
        )
        .map(|x| rule::create_rule(x))
        .collect::<Vec<_>>();
    let all_cells = problem
        .cells
        .iter()
        .chain(candidate.cell_values.iter())
        .map(|x| *x)
        .collect::<Vec<(usize, usize, char)>>();
    !all_rules
        .iter()
        .all(|x| rule::check(all_cells.as_slice(), x))
}

fn accept(problem: &Problem, candidate: PartialSolution) -> bool {
    let fixed_cells = problem
        .cells
        .iter()
        .chain(candidate.cell_values.iter())
        .map(|&(i, j, _)| (i, j))
        .collect::<Vec<_>>();
    let empty_cells = (0..9)
        .cartesian_product(0..9)
        .filter(|x| !fixed_cells.contains(x))
        .collect::<Vec<_>>();
    empty_cells.is_empty()
}

fn output(problem: &Problem, candidate: PartialSolution) -> Vec<(usize, usize, char)> {
    problem
        .cells
        .iter()
        .chain(candidate.cell_values.iter())
        .map(|x| *x)
        .collect::<Vec<(usize, usize, char)>>()
}

fn first(_problem: &Problem, candidate: &PartialSolution) -> Option<PartialSolution> {
    use std::iter;
    candidate
        .empty_cells
        .as_slice()
        .split_first()
        .map(|(&(i, j), xs)| PartialSolution {
            cell_values: candidate
                .cell_values
                .iter()
                .chain(iter::once(&(i, j, '1')))
                .map(|x| *x)
                .collect::<Vec<(usize, usize, char)>>(),
            empty_cells: xs.to_vec(),
        })
}

fn next_value(c: &char) -> Option<char> {
    match *c {
        '1' => Some('2'),
        '2' => Some('3'),
        '3' => Some('4'),
        '4' => Some('5'),
        '5' => Some('6'),
        '6' => Some('7'),
        '7' => Some('8'),
        '8' => Some('9'),
        _ => None,
    }
}

fn next(_problem: &Problem, candidate: &PartialSolution) -> Option<PartialSolution> {
    use std::iter;
    candidate
        .cell_values
        .as_slice()
        .split_last()
        .and_then(|(&(x, y, z), other_cells)| {
            next_value(&z).map(|value| PartialSolution {
                cell_values: other_cells
                    .iter()
                    .chain(iter::once(&(x, y, value)))
                    .map(|x| *x)
                    .collect::<Vec<(usize, usize, char)>>(),
                empty_cells: candidate.empty_cells.clone(),
            })
        })
}

fn main() {
    let problem = Problem::new(&[(0, 0, '1'), (0, 1, '2'), (0, 2, '3'), (0, 3, '4')]);
    println!("{:?}", root(&problem));

    let r = rule::create_rule(rule::RuleType::Square(0, 0));
    println!("{:?}", r);

    println!("{:?}", rule::mask(problem.cells.as_slice(), r.as_slice()));
    println!("{:?}", rule::check(problem.cells.as_slice(), r.as_slice()));

    println!("{:?}", first(&problem, &root(&problem)));
    let a = first(&problem,&root(&problem)).and_then(|x| next(&problem,&x)) ;
    println!("{:?}", a);
    let b = a.and_then(|x| next(&problem,&x)) ;
    println!("{:?}", b);
    let c = b.and_then(|x| next(&problem,&x)) ;
    println!("{:?}", c);
    let d = c.and_then(|x| next(&problem,&x)) ;
    println!("{:?}", d);
    let e = d.and_then(|x| next(&problem,&x)) ;
    println!("{:?}", e);
    let f = e.and_then(|x| next(&problem,&x)) ;
    println!("{:?}", f);
    let g = f.and_then(|x| next(&problem,&x)) ;
    println!("{:?}", g);
    let h = g.and_then(|x| next(&problem,&x)) ;
    println!("{:?}", h);
    let i = h.and_then(|x| next(&problem,&x)) ;
    println!("{:?}", i);
}