Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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 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)));
- }
Add Comment
Please, Sign In to add comment