1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| impl Solution {
pub fn solve_sudoku(board: &mut Vec<Vec<char>>) {
let mut line = vec![vec![false;9]; 9];
let mut column = vec![vec![false;9]; 9];
let mut block = vec![vec![vec![false;9];3];3];
let mut space = Vec::new();
(0..9).for_each(|i| {
(0..9).for_each(|j| {
if board[i][j] == '.' {
space.push((i,j));
} else {
let digit = board[i][j].to_digit(10).unwrap() as usize -1;
line[i][digit] = true;
column[j][digit] = true;
block[i/3][j/3][digit] = true;
}
});
});
fn dfs(board: &mut Vec<Vec<char>>,
space: &Vec<(usize,usize)>,
line: &mut Vec<Vec<bool>>,
column: &mut Vec<Vec<bool>>,
block: &mut Vec<Vec<Vec<bool>>>,
pos: usize) -> bool {
if pos == space.len() {
return true;
}
let (i,j) = space[pos];
for digit in 0..9 {
if !line[i][digit] && !column[j][digit] && !block[i/3][j/3][digit] {
line[i][digit] = true;
column[j][digit] = true;
block[i/3][j/3][digit] = true;
board[i][j] = (digit as u8 + b'1') as char;
if dfs(board, space, line, column, block, pos + 1) {
return true;
}
line[i][digit] = false;
column[j][digit] = false;
block[i/3][j/3][digit] = false;
}
}
return false;
}
dfs(board, &mut space, &mut line, &mut column, &mut block, 0);
}
}
|
