sudoku/
gen.rs

1use rand::{thread_rng, Rng};
2use sol::PossibilityMap;
3use Difficulty;
4use Element;
5use Grid;
6use Score;
7use Sudoku;
8
9/// The maximum number of times the hardening algorithm will try to make a harder puzzle in a
10/// single pass.
11const MAX_HARDEN_ITERATIONS: u8 = 20;
12
13/// Trait to generate a puzzle.
14///
15/// Requires that the puzzle be solvable (to ensure the desired difficulty is
16/// attained).
17pub trait Generate: Score + Sized {
18    /// Generates a puzzle of the desired order and difficulty.
19    fn generate(order: u8, difficulty: Difficulty) -> Self;
20}
21
22fn take_random<T>(values: &mut Vec<T>) -> Option<T> {
23    let mut rng = thread_rng();
24    let mut indices = (0..values.len()).collect::<Vec<_>>();
25    rng.shuffle(&mut indices);
26    indices.get(0).map(|index| values.remove(*index))
27}
28
29fn recurse(puzzle: Sudoku) -> Option<Sudoku> {
30    let map: PossibilityMap = puzzle.clone().into();
31    match map.next() {
32        (None, _) => {
33            let puzzle = puzzle.clone();
34            if puzzle.is_complete() {
35                Some(puzzle)
36            } else {
37                None
38            }
39        }
40        (Some(index), Some(set)) => {
41            let mut possibilities = (1..=(puzzle.order as usize).pow(2))
42                .filter(|v| set.contains(*v))
43                .collect::<Vec<_>>();
44            while let Some(candidate) = take_random(&mut possibilities) {
45                let solution = recurse(puzzle.substitute(index, Some(Element(candidate as u8))));
46                if solution.is_some() {
47                    return solution;
48                }
49            }
50            None
51        }
52        _ => unreachable!(),
53    }
54}
55
56/// Creates a randomized sudoku grid of the specified order.
57fn grid(order: u8) -> Option<Sudoku> {
58    let mut rng = thread_rng();
59    let mut puzzle = Sudoku::new(order);
60    // TODO(#14): Revisit this block when NLL lands.
61    {
62        // Top-left box
63        let mut first_box = (1..=order.pow(2))
64            .map(|v| Some(Element(v)))
65            .collect::<Vec<_>>();
66        rng.shuffle(&mut first_box);
67        let order = order as usize;
68        let axis = order.pow(2);
69        {
70            let elements = &mut puzzle.elements;
71            for i in 0..axis {
72                let index = i / order * axis + i;
73                elements[index] = first_box[i];
74            }
75        }
76        // TODO(#13): Reduce the number of cells that are filled with backtracking.
77        // The rest
78        recurse(puzzle)
79    }
80}
81
82/// Makes the sudoku harder to the desired level, modifying it in-place.
83///
84/// # Notes
85/// No validation is performed on the passed puzzle.
86fn harden(mut sudoku: &mut Sudoku, target: Difficulty) -> Result<(), ()> {
87    let current = sudoku.score().unwrap();
88    let mut points = sudoku.points();
89    for _ in 0..MAX_HARDEN_ITERATIONS {
90        if let (Some(one), Some(two)) = (take_random(&mut points), take_random(&mut points)) {
91            let (one, two) = (one.fold(sudoku.order), two.fold(sudoku.order));
92            let mut puzzle = sudoku.clone();
93            // Faster than substituting twice.
94            puzzle.elements[one] = None;
95            puzzle.elements[two] = None;
96            match puzzle.score() {
97                Some(score) => {
98                    if score > current {
99                        let difficulty: Difficulty = score.into();
100                        if difficulty > target {
101                            // We overshot the target difficulty
102                            continue;
103                        }
104                        sudoku.elements[one] = None;
105                        sudoku.elements[two] = None;
106                        return if difficulty == target {
107                            Ok(())
108                        } else {
109                            harden(&mut sudoku, target)
110                        };
111                    }
112                }
113                _ => {}
114            }
115        }
116    }
117    Err(())
118}
119
120impl Generate for Sudoku {
121    fn generate(order: u8, difficulty: Difficulty) -> Self {
122        let mut puzzle = grid(order).unwrap();
123        let _ = harden(&mut puzzle, difficulty);
124        puzzle
125    }
126}
127
128#[cfg(test)]
129mod tests {
130    use gen;
131    use Solve;
132    #[cfg_attr(feature = "2D", test)]
133    fn test_grid() {
134        let grid = gen::grid(3);
135        let grid = grid.unwrap();
136        assert!(grid.is_complete());
137        assert!(grid.is_uniquely_solvable());
138    }
139}
sudoku/gen.rs

sudoku/
gen.rs
