pub fn solve_sudoku(board: &mut Vec<Vec<char>>)
Expand description
§Solutions
§Approach 1: DFS
-
Time complexity:
-
Space complexity:
-
Runtime: 12 ms
-
Memory: 2.4 MB
impl Solution {
pub fn solve_sudoku(board: &mut Vec<Vec<char>>) {
if board.is_empty() { return; }
Self::solve(board);
}
pub fn solve(board: &mut Vec<Vec<char>>) -> bool {
for row in 0..board.len() {
for col in 0..board[row].len() {
if board[row][col] != '.' { continue; }
for c in "123456789".chars().collect::<Vec<_>>() {
if !Self::is_valid(&board, row, col, c) { continue; }
board[row][col] = c;
if Self::solve(board) { return true; }
board[row][col] = '.';
}
return false;
}
}
return true;
}
pub fn is_valid(board: &Vec<Vec<char>>, row: usize, col: usize, c: char) -> bool {
for i in 0..9 {
if board[row][i] != '.' && board[row][i] == c { return false; } // check row
if board[i][col] != '.' && board[i][col] == c { return false; } // check col
let block = board[(3 * (row as i32 / 3) + i as i32 / 3) as usize][(3 * (col as i32 / 3) + i as i32 % 3) as usize];
if block != '.' && block == c { return false; } // check 3 * 3 block;
}
true
}
}
§Approach 2: DFS
-
Time complexity:
-
Space complexity:
-
Runtime: 0 ms
-
Memory: 2.5 MB
use std::char;
impl Solution {
pub fn solve_sudoku(board: &mut Vec<Vec<char>>) {
if board.is_empty() { return; }
// 快速检索第i, j列, 第k宫的数字是否被占用
let mut lines = [[false; 9]; 9];
let mut columns = [[false; 9]; 9];
let mut ceils = [[false; 9]; 9];
let mut origins = [[false; 9]; 9];
// initialize lines columns ceils and origins
for row in 0..9 {
for col in 0..9 {
let num = match board[row][col].to_digit(10) {
Some(n) => (n - 1) as usize,
None => continue,
};
lines[row][num] = true;
columns[col][num] = true;
origins[row][col] = true;
ceils[Self::ceil_pos((row, col))][num] = true;
}
}
Self::solve(board, (0, 0), &mut lines, &mut columns, &mut ceils, &mut origins);
}
pub fn solve(board: &mut Vec<Vec<char>>,
(row, col): (usize, usize),
lines: &mut[[bool; 9]; 9],
columns: &mut[[bool; 9]; 9],
ceils: &mut[[bool; 9]; 9],
origins: &mut[[bool; 9]; 9]) -> bool {
if row >= 9 { return true; }
let next_pos = (row + (col + 1) / 9, (col + 1) % 9);
if origins[row][col] { return Self::solve(board, next_pos, lines, columns, ceils, origins); }
let mut flag = false;
for num in 0..9 {
let ceil = Self::ceil_pos((row, col));
if lines[row][num] || columns[col][num] || ceils[ceil][num] { continue; }
// 数字num + 1没用过
lines[row][num] = true;
columns[col][num] = true;
ceils[ceil][num] = true;
board[row][col] = char::from_digit(num as u32 + 1, 10).unwrap();
flag |= Self::solve(board, next_pos, lines, columns, ceils, origins);
if flag { break; } // 已填数 OK
lines[row][num] = false;
columns[col][num] = false;
ceils[ceil][num] = false;
}
flag
}
// 求出pos属于第几个ceil
pub fn ceil_pos(pos: (usize, usize)) -> usize {
(pos.0 / 3) * 3 + pos.1 / 3
}
}