puzzle_solver/constraint/
alldifferent.rs

1//! All different implementation.
2
3use std::collections::HashMap;
4use std::rc::Rc;
5
6use ::{Constraint,PsResult,PuzzleSearch,Val,VarToken};
7
8pub struct AllDifferent {
9    vars: Vec<VarToken>,
10}
11
12impl AllDifferent {
13    /// Allocate a new All Different constraint.
14    ///
15    /// # Examples
16    ///
17    /// ```
18    /// let mut send_more_money = puzzle_solver::Puzzle::new();
19    /// let vars = send_more_money.new_vars_with_candidates_1d(8,
20    ///         &[0,1,2,3,4,5,6,7,8,9]);
21    ///
22    /// puzzle_solver::constraint::AllDifferent::new(&vars);
23    /// ```
24    pub fn new<'a, I>(vars: I) -> Self
25            where I: IntoIterator<Item=&'a VarToken> {
26        AllDifferent {
27            vars: vars.into_iter().cloned().collect(),
28        }
29    }
30}
31
32impl Constraint for AllDifferent {
33    fn vars<'a>(&'a self) -> Box<Iterator<Item=&'a VarToken> + 'a> {
34        Box::new(self.vars.iter())
35    }
36
37    fn on_assigned(&self, search: &mut PuzzleSearch, var: VarToken, val: Val)
38            -> PsResult<()> {
39        for &var2 in self.vars.iter().filter(|&v| *v != var) {
40            try!(search.remove_candidate(var2, val));
41        }
42
43        Ok(())
44    }
45
46    fn on_updated(&self, search: &mut PuzzleSearch) -> PsResult<()> {
47        // Build a table of which values can be assigned to which variables.
48        let mut num_unassigned = 0;
49        let mut all_candidates = HashMap::new();
50
51        for &var in self.vars.iter().filter(|&var| !search.is_assigned(*var)) {
52            num_unassigned = num_unassigned + 1;
53
54            for val in search.get_unassigned(var) {
55                if all_candidates.contains_key(&val) {
56                    all_candidates.insert(val, None);
57                } else {
58                    all_candidates.insert(val, Some(var));
59                }
60            }
61        }
62
63        if num_unassigned > all_candidates.len() {
64            // More unassigned variables than candidates, contradiction.
65            return Err(());
66        } else if num_unassigned == all_candidates.len() {
67            // As many as variables as candidates.
68            for (&val, &opt) in all_candidates.iter() {
69                if let Some(var) = opt {
70                    try!(search.set_candidate(var, val));
71                }
72            }
73        }
74
75        Ok(())
76    }
77
78    fn substitute(&self, from: VarToken, to: VarToken)
79            -> PsResult<Rc<Constraint>> {
80        if let Some(idx) = self.vars.iter().position(|&var| var == from) {
81            if !self.vars.contains(&to) {
82                let mut new_vars = self.vars.clone();
83                new_vars[idx] = to;
84                return Ok(Rc::new(AllDifferent{ vars: new_vars }));
85            }
86        }
87
88        Err(())
89    }
90}
91
92#[cfg(test)]
93mod tests {
94    use ::{Puzzle,Val};
95
96    #[test]
97    fn test_contradiction() {
98        let mut puzzle = Puzzle::new();
99        let v0 = puzzle.new_var_with_candidates(&[1]);
100        let v1 = puzzle.new_var_with_candidates(&[1]);
101        let v2 = puzzle.new_var_with_candidates(&[1,2,3]);
102
103        puzzle.all_different(&[v0,v1,v2]);
104
105        let solution = puzzle.solve_any();
106        assert!(solution.is_none());
107    }
108
109    #[test]
110    fn test_elimination() {
111        let mut puzzle = Puzzle::new();
112        let v0 = puzzle.new_var_with_candidates(&[1]);
113        let v1 = puzzle.new_var_with_candidates(&[1,2,3]);
114        let v2 = puzzle.new_var_with_candidates(&[1,2,3]);
115
116        puzzle.all_different(&[v0,v1,v2]);
117
118        let search = puzzle.step().expect("contradiction");
119        assert_eq!(search[v0], 1);
120        assert_eq!(search.get_unassigned(v1).collect::<Vec<Val>>(), &[2,3]);
121        assert_eq!(search.get_unassigned(v2).collect::<Vec<Val>>(), &[2,3]);
122    }
123
124    #[test]
125    fn test_contradiction_by_length() {
126        let mut puzzle = Puzzle::new();
127        let v0 = puzzle.new_var_with_candidates(&[1,2]);
128        let v1 = puzzle.new_var_with_candidates(&[1,2]);
129        let v2 = puzzle.new_var_with_candidates(&[1,2]);
130
131        puzzle.all_different(&[v0,v1,v2]);
132
133        let search = puzzle.step();
134        assert!(search.is_none());
135    }
136
137    #[test]
138    fn test_constrain_by_value() {
139        let mut puzzle = Puzzle::new();
140        let v0 = puzzle.new_var_with_candidates(&[1,2]);
141        let v1 = puzzle.new_var_with_candidates(&[1,2]);
142        let v2 = puzzle.new_var_with_candidates(&[1,2,3]);
143
144        puzzle.all_different(&[v0,v1,v2]);
145
146        let search = puzzle.step().expect("contradiction");
147        assert_eq!(search.get_unassigned(v0).collect::<Vec<Val>>(), &[1,2]);
148        assert_eq!(search.get_unassigned(v1).collect::<Vec<Val>>(), &[1,2]);
149        assert_eq!(search[v2], 3);
150    }
151}
puzzle_solver/constraint/alldifferent.rs

puzzle_solver/constraint/
alldifferent.rs
