[−][src]Function leetcode_for_rust::cd0037_sudoku_solver::solve_sudoku
pub fn solve_sudoku(board: &mut Vec<Vec<char>>)
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 } }