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
    }
}