algorithms_edu/problems/backtracking/
sudoku.rs

1//! Write a program to solve a Sudoku puzzle by filling the empty cells.
2//!
3//! A sudoku solution must satisfy all of the following rules:
4//!
5//! - Each of the digits 1-9 must occur exactly once in each row.
6//! - Each of the digits 1-9 must occur exactly once in each column.
7//! - Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
8//!
9//! The '.' character indicates empty cells.
10//!
11//! # Strategy
12//!
13//! DFS.
14//!
15//! # See also
16//!
17//! - [LeetCode](https://leetcode.com/problems/sudoku-solver/)
18
19pub struct Sudoku {
20    inner: [[char; 9]; 9],
21}
22
23impl Sudoku {
24    pub fn solve_iterative(&mut self) {
25        let mut stack = Vec::new();
26        let [i, j] = self.next_blank().unwrap();
27        for x in '1'..='9' {
28            stack.push((i, j, x));
29        }
30        loop {
31            let (i, j, v) = stack.pop().unwrap();
32
33            if v == '.' {
34                self.set(i, j, v);
35            } else if self.can_set(i, j, v) {
36                self.set(i, j, v);
37                if let Some([i, j]) = self.next_blank() {
38                    // if 1..=9 all fail, remember to empty this cell.
39                    stack.push((i, j, '.'));
40                    for x in '1'..='9' {
41                        stack.push((i, j, x));
42                    }
43                } else {
44                    return;
45                }
46            }
47        }
48    }
49}
50
51impl Sudoku {
52    pub fn solve_recursive(&mut self) -> bool {
53        if let Some([i, j]) = self.next_blank() {
54            for v in '1'..='9' {
55                if self.can_set(i, j, v) {
56                    self.set(i, j, v);
57                    if self.solve_recursive() {
58                        return true;
59                    } else {
60                        self.erase(i, j);
61                    }
62                }
63            }
64        } else {
65            return true;
66        }
67        false
68    }
69}
70
71impl Sudoku {
72    pub fn new(matrix: [[char; 9]; 9]) -> Self {
73        Self { inner: matrix }
74    }
75
76    fn next_blank(&self) -> Option<[usize; 2]> {
77        for i in 0..9 {
78            for j in 0..9 {
79                if self.inner[i][j] == '.' {
80                    return Some([i, j]);
81                }
82            }
83        }
84        None
85    }
86    fn can_set(&self, i: usize, j: usize, n: char) -> bool {
87        // check row
88        for j_ in 0..9 {
89            if self.inner[i][j_] == n {
90                return false;
91            }
92        }
93        // check column
94        for i_ in 0..9 {
95            if self.inner[i_][j] == n {
96                return false;
97            }
98        }
99        // check 3x3 grid
100        let i1 = i / 3;
101        let j1 = j / 3;
102        for i2 in 0..3 {
103            for j2 in 0..3 {
104                if self.inner[i1 * 3 + i2][j1 * 3 + j2] == n {
105                    return false;
106                }
107            }
108        }
109        true
110    }
111
112    fn set(&mut self, i: usize, j: usize, v: char) {
113        self.inner[i][j] = v
114    }
115
116    fn erase(&mut self, i: usize, j: usize) {
117        self.inner[i][j] = '.';
118    }
119}
120use std::fmt;
121
122impl fmt::Display for Sudoku {
123    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
124        let mut s = String::with_capacity(180);
125        for i in 0..9 {
126            for j in 0..9 {
127                s.push_str(&format!("{} ", self.inner[i][j]))
128            }
129            s.push('\n')
130        }
131        s.push('\n');
132        write!(f, "{}", s)
133    }
134}
135
136#[cfg(test)]
137mod tests {
138    use super::*;
139    #[test]
140    fn test_sudoku() {
141        let ans = [
142            ['5', '1', '9', '7', '4', '8', '6', '3', '2'],
143            ['7', '8', '3', '6', '5', '2', '4', '1', '9'],
144            ['4', '2', '6', '1', '3', '9', '8', '7', '5'],
145            ['3', '5', '7', '9', '8', '6', '2', '4', '1'],
146            ['2', '6', '4', '3', '1', '7', '5', '9', '8'],
147            ['1', '9', '8', '5', '2', '4', '3', '6', '7'],
148            ['9', '7', '5', '8', '6', '3', '1', '2', '4'],
149            ['8', '3', '2', '4', '9', '1', '7', '5', '6'],
150            ['6', '4', '1', '2', '7', '5', '9', '8', '3'],
151        ];
152
153        let s = [
154            ['.', '.', '9', '7', '4', '8', '.', '.', '.'],
155            ['7', '.', '.', '.', '.', '.', '.', '.', '.'],
156            ['.', '2', '.', '1', '.', '9', '.', '.', '.'],
157            ['.', '.', '7', '.', '.', '.', '2', '4', '.'],
158            ['.', '6', '4', '.', '1', '.', '5', '9', '.'],
159            ['.', '9', '8', '.', '.', '.', '3', '.', '.'],
160            ['.', '.', '.', '8', '.', '3', '.', '2', '.'],
161            ['.', '.', '.', '.', '.', '.', '.', '.', '6'],
162            ['.', '.', '.', '2', '7', '5', '9', '.', '.'],
163        ];
164
165        let mut sudoku = Sudoku::new(s);
166        sudoku.solve_iterative();
167        println!("{}", &sudoku);
168        assert_eq!(sudoku.inner, ans);
169
170        let mut sudoku = Sudoku::new(s);
171        sudoku.solve_recursive();
172        println!("{}", &sudoku);
173        assert_eq!(sudoku.inner, ans);
174
175        let ans = [
176            ['5', '3', '4', '6', '7', '8', '9', '1', '2'],
177            ['6', '7', '2', '1', '9', '5', '3', '4', '8'],
178            ['1', '9', '8', '3', '4', '2', '5', '6', '7'],
179            ['8', '5', '9', '7', '6', '1', '4', '2', '3'],
180            ['4', '2', '6', '8', '5', '3', '7', '9', '1'],
181            ['7', '1', '3', '9', '2', '4', '8', '5', '6'],
182            ['9', '6', '1', '5', '3', '7', '2', '8', '4'],
183            ['2', '8', '7', '4', '1', '9', '6', '3', '5'],
184            ['3', '4', '5', '2', '8', '6', '1', '7', '9'],
185        ];
186
187        let s = [
188            ['5', '3', '.', '.', '7', '.', '.', '.', '.'],
189            ['6', '.', '.', '1', '9', '5', '.', '.', '.'],
190            ['.', '9', '8', '.', '.', '.', '.', '6', '.'],
191            ['8', '.', '.', '.', '6', '.', '.', '.', '3'],
192            ['4', '.', '.', '8', '.', '3', '.', '.', '1'],
193            ['7', '.', '.', '.', '2', '.', '.', '.', '6'],
194            ['.', '6', '.', '.', '.', '.', '2', '8', '.'],
195            ['.', '.', '.', '4', '1', '9', '.', '.', '5'],
196            ['.', '.', '.', '.', '8', '.', '.', '7', '9'],
197        ];
198
199        let mut sudoku = Sudoku::new(s);
200        sudoku.solve_iterative();
201        println!("{}", &sudoku);
202        assert_eq!(sudoku.inner, ans);
203
204        let mut sudoku = Sudoku::new(s);
205        sudoku.solve_recursive();
206        println!("{}", &sudoku);
207        assert_eq!(sudoku.inner, ans);
208    }
209}
algorithms_edu/problems/backtracking/sudoku.rs

algorithms_edu/problems/backtracking/
sudoku.rs
