## vague / leetcode .gitee-modal { width: 500px !important; }

Explore and code with more than 6 million developers，Free private repositories ！：）
_0037_sudoku_solver.rs 11.65 KB
vague authored 2021-07-20 19:44 . fmt
/// https://leetcode-cn.com/problems/sudoku-solver
pub struct Solution;

/// 对比不同数据结构的性能
impl Solution {
pub fn solve_sudoku_bit_simple(board: &mut Vec<Vec<char>>) {
let (board, mut rcb) = Solution::simple(board, RcbBit::new());
Backtrace::simple(0, 0, board, &mut rcb);
}

pub fn solve_sudoku_bit_record(board: &mut Vec<Vec<char>>) {
let (v, board, mut rcb) = Solution::record(board, RcbBit::new());
Backtrace::record(0, &v, board, &mut rcb);
}

pub fn solve_sudoku_bit_valid_record(board: &mut Vec<Vec<char>>) {
let (v, board, mut rcb) = Solution::record(board, RcbBit::new());
let mut valid = false;
Backtrace::valid_record(&mut valid, 0, &v, board, &mut rcb);
}

pub fn solve_sudoku_bits_simple(board: &mut Vec<Vec<char>>) {
let (board, mut rcb) = Solution::simple(board, RcbBits::new());
Backtrace::simple(0, 0, board, &mut rcb);
}

pub fn solve_sudoku_bits_record(board: &mut Vec<Vec<char>>) {
let (v, board, mut rcb) = Solution::record(board, RcbBits::new());
Backtrace::record(0, &v, board, &mut rcb);
}

pub fn solve_sudoku_bits_valid_record(board: &mut Vec<Vec<char>>) {
let (v, board, mut rcb) = Solution::record(board, RcbBits::new());
let mut valid = false;
Backtrace::valid_record(&mut valid, 0, &v, board, &mut rcb);
}

pub fn solve_sudoku_arr_simple(board: &mut Vec<Vec<char>>) {
let (board, mut rcb) = Solution::simple(board, RcbArr::new());
Backtrace::simple(0, 0, board, &mut rcb);
}

pub fn solve_sudoku_arr_record(board: &mut Vec<Vec<char>>) {
let (v, board, mut rcb) = Solution::record(board, RcbArr::new());
Backtrace::record(0, &v, board, &mut rcb);
}

pub fn solve_sudoku_arr_valid_record(board: &mut Vec<Vec<char>>) {
let (v, board, mut rcb) = Solution::record(board, RcbArr::new());
let mut valid = false;
Backtrace::valid_record(&mut valid, 0, &v, board, &mut rcb);
}

pub fn solve_sudoku_arrs_simple(board: &mut Vec<Vec<char>>) {
let (board, mut rcb) = Solution::simple(board, RcbArrs::new());
Backtrace::simple(0, 0, board, &mut rcb);
}

pub fn solve_sudoku_arrs_record(board: &mut Vec<Vec<char>>) {
let (v, board, mut rcb) = Solution::record(board, RcbArrs::new());
Backtrace::record(0, &v, board, &mut rcb);
}

pub fn solve_sudoku_arrs_valid_record(board: &mut Vec<Vec<char>>) {
let (v, board, mut rcb) = Solution::record(board, RcbArrs::new());
let mut valid = false;
Backtrace::valid_record(&mut valid, 0, &v, board, &mut rcb);
}
}

/// record: 记录空位置；simple: 不记录空位置
impl Solution {
fn simple<T: Sudoku>(board: &mut [Vec<char>], mut rcb: T) -> (&mut [Vec<char>], T) {
// 技巧：经过测试，数组遍历元素时，使用迭代器比下标访问更快（对比的代码就不补充了）
for (i, r) in board.iter().enumerate() {
for (j, &c) in r.iter().enumerate() {
let k = i / 3 * 3 + j / 3;
if c != '.' {
let d = c as usize - 49;
rcb.flip(i, j, k, d);
}
}
}
(board, rcb)
}

fn record<T: Sudoku>(board: &mut [Vec<char>], mut rcb: T)
-> (Vec<[usize; 3]>, &mut [Vec<char>], T) {
let mut v: Vec<[usize; 3]> = Vec::with_capacity(81); // 记录空位置
for (i, r) in board.iter().enumerate() {
for (j, &c) in r.iter().enumerate() {
let k = i / 3 * 3 + j / 3;
if c != '.' {
let d = c as usize - 49;
rcb.flip(i, j, k, d);
} else {
v.push([i, j, k]);
}
}
}
(v, board, rcb)
}
}

struct Backtrace;

/// 回溯/递归：三种方式
#[rustfmt::skip]
impl Backtrace {
fn simple(mut i: usize, mut j: usize, board: &mut [Vec<char>], rcb: &mut impl Sudoku) -> bool {
if j == 9 { i += 1; j = 0; }
if i == 9 { return true; }
if board[i][j] != '.' { return Backtrace::simple(i, j + 1, board, rcb); }
let k = i / 3 * 3 + j / 3;
for d in 0..9 {
if rcb.check(i, j, k, d) {
rcb.flip(i, j, k, d);
board[i][j] = (d as u8 + 49) as char;
if Backtrace::simple(i, j + 1, board, rcb) { return true; }
board[i][j] = '.';
rcb.flip(i, j, k, d);
}
}
false
}

fn record(pos: usize, v: &[[usize; 3]], board: &mut [Vec<char>], rcb: &mut impl Sudoku) -> bool {
if pos == v.len() { return true; }
let &[i, j, k] = &v[pos];
for d in 0..9 {
if rcb.check(i, j, k, d) {
rcb.flip(i, j, k, d);
board[i][j] = (d as u8 + 49) as char;
if Backtrace::record(pos + 1, v, board, rcb) { return true; }
board[i][j] = '.';
rcb.flip(i, j, k, d);
}
}
false
}

fn valid_record(valid: &mut bool, pos: usize, v: &[[usize; 3]],
board: &mut [Vec<char>], rcb: &mut impl Sudoku) {
if pos == v.len() { return *valid = true; }
let &[i, j, k] = &v[pos];
for d in 0..9 {
if rcb.check(i, j, k, d) {
rcb.flip(i, j, k, d);
board[i][j] = (d as u8 + 49) as char;
Backtrace::valid_record(valid, pos + 1, v, board, rcb);
rcb.flip(i, j, k, d);
}
if *valid { return (); }
}
}
}

trait Sudoku {
fn new() -> Self;
/// 在这个算法中，已经提前判断了逻辑，所以每次都是反转这个结果
fn flip(&mut self, i: usize, j: usize, k: usize, d: usize);
fn check(&self, i: usize, j: usize, k: usize, d: usize) -> bool;
}

struct RcbBit([[u16; 9]; 3]);

impl Sudoku for RcbBit {
fn new() -> Self { Self([[0; 9]; 3]) }

fn flip(&mut self, i: usize, j: usize, k: usize, d: usize) {
self.0[0][i] ^= 1 << d;
self.0[1][j] ^= 1 << d;
self.0[2][k] ^= 1 << d;
}

fn check(&self, i: usize, j: usize, k: usize, d: usize) -> bool {
let n = 1 << d;
((self.0[0][i] & n) | (self.0[1][j] & n) | (self.0[2][k] & n)).eq(&0)
}
}

#[rustfmt::skip]
struct RcbBits { // 第 d 位的 0 代表无数字，实际只需要后 0-8 位（u8 只有 0-7 共 8 位）
row: [u16; 9], col: [u16; 9], block: [u16; 9]
}

impl Sudoku for RcbBits {
#[rustfmt::skip]
fn new() -> Self { Self { row: [0; 9], col: [0; 9], block: [0; 9] } }

fn flip(&mut self, i: usize, j: usize, k: usize, d: usize) {
// 把第 d 位数字（表示数 d+1 ）设置为相反数
self.row[i] ^= 1 << d;
self.col[j] ^= 1 << d;
self.block[k] ^= 1 << d;
}

fn check(&self, i: usize, j: usize, k: usize, d: usize) -> bool {
// a & (1 << d) 检查 a 的第 d 位是不是 0：如果是 0 ，则返回 0；不是 0 返回非 0
// 这里的位运算虽然不像 bools 那样最少可以比对一次，
// 但位运算在这一个测试例子里大概快 7000 ns ，花销可能在于数字到 bool 的转换需要 eq
// let cmp = |n: u16| (n & (1 << d)).eq(&0);
// cmp(self.row[i]) && cmp(self.col[j]) && cmp(self.block[k])
let n = 1 << d;
((self.row[i] & n) | (self.col[j] & n) | (self.block[k] & n)).eq(&0)
}
}

struct RcbArr([[[bool; 9]; 9]; 3]);

impl Sudoku for RcbArr {
fn new() -> Self { Self([[[false; 9]; 9]; 3]) }

fn flip(&mut self, i: usize, j: usize, k: usize, d: usize) {
self.0[0][i][d] ^= true; // 取反
self.0[1][j][d] ^= true;
self.0[2][k][d] ^= true;
}

fn check(&self, i: usize, j: usize, k: usize, d: usize) -> bool {
!self.0[0][i][d] && !self.0[1][j][d] && !self.0[2][k][d]
}
}

/// 当然，也可以把 bool 换成整数，使用位运算，比如
/// https://rustgym.com/leetcode/37
#[rustfmt::skip]
struct RcbArrs { // row：第一层代表第 i 行，第二层代表 1-9 的每个数字； col、block 类似
row: [[bool; 9]; 9], col: [[bool; 9]; 9], block: [[bool; 9]; 9],
}

impl Sudoku for RcbArrs {
#[rustfmt::skip]
fn new() -> Self {
Self { row: [[false; 9]; 9], col: [[false; 9]; 9], block: [[false; 9]; 9] }
}

fn flip(&mut self, i: usize, j: usize, k: usize, d: usize) {
self.row[i][d] ^= true; // 取反
self.col[j][d] ^= true;
self.block[k][d] ^= true;
}

fn check(&self, i: usize, j: usize, k: usize, d: usize) -> bool {
!self.row[i][d] && !self.col[j][d] && !self.block[k][d]
}
}

#[cfg(test)]
mod tests {
use super::*;

fn assert(f: impl Fn(&mut Vec<Vec<char>>)) {
let mut board = vec![vec!['5', '3', '.', '.', '7', '.', '.', '.', '.'],
vec!['6', '.', '.', '1', '9', '5', '.', '.', '.'],
vec!['.', '9', '8', '.', '.', '.', '.', '6', '.'],
vec!['8', '.', '.', '.', '6', '.', '.', '.', '3'],
vec!['4', '.', '.', '8', '.', '3', '.', '.', '1'],
vec!['7', '.', '.', '.', '2', '.', '.', '.', '6'],
vec!['.', '6', '.', '.', '.', '.', '2', '8', '.'],
vec!['.', '.', '.', '4', '1', '9', '.', '.', '5'],
vec!['.', '.', '.', '.', '8', '.', '.', '7', '9']];
f(&mut board);
let ans = vec![vec!['5', '3', '4', '6', '7', '8', '9', '1', '2'],
vec!['6', '7', '2', '1', '9', '5', '3', '4', '8'],
vec!['1', '9', '8', '3', '4', '2', '5', '6', '7'],
vec!['8', '5', '9', '7', '6', '1', '4', '2', '3'],
vec!['4', '2', '6', '8', '5', '3', '7', '9', '1'],
vec!['7', '1', '3', '9', '2', '4', '8', '5', '6'],
vec!['9', '6', '1', '5', '3', '7', '2', '8', '4'],
vec!['2', '8', '7', '4', '1', '9', '6', '3', '5'],
vec!['3', '4', '5', '2', '8', '6', '1', '7', '9']];
assert_eq!(board, ans);
}

// 测试结果仅供参考：
// solve_sudoku_arrs_record:       122,181 ns/iter (+/- 7,597)
// solve_sudoku_arr_record:        126,718 ns/iter (+/- 4,754)
// solve_sudoku_arrs_simple:       127,047 ns/iter (+/- 5,597)
// solve_sudoku_bit_simple:        128,923 ns/iter (+/- 5,457)
// solve_sudoku_arr_simple:        129,896 ns/iter (+/- 6,582)
// solve_sudoku_bits_simple:       129,547 ns/iter (+/- 83,216)
// solve_sudoku_bit_valid_record:  133,999 ns/iter (+/- 8,108)
// solve_sudoku_bits_valid_record: 135,327 ns/iter (+/- 73,912)
// solve_sudoku_bit_record:        139,431 ns/iter (+/- 5,925)
// solve_sudoku_bits_record:       139,230 ns/iter (+/- 48,954)
// solve_sudoku_arrs_valid_record: 141,431 ns/iter (+/- 20,204)
// solve_sudoku_arr_valid_record:  145,287 ns/iter (+/- 49,714)
bench!(assert Solution::solve_sudoku_arr_simple);
bench!(assert Solution::solve_sudoku_arr_record);
bench!(assert Solution::solve_sudoku_arr_valid_record);

bench!(assert Solution::solve_sudoku_arrs_simple);
bench!(assert Solution::solve_sudoku_arrs_record);
bench!(assert Solution::solve_sudoku_arrs_valid_record);

bench!(assert Solution::solve_sudoku_bit_simple);
bench!(assert Solution::solve_sudoku_bit_record);
bench!(assert Solution::solve_sudoku_bit_valid_record);

bench!(assert Solution::solve_sudoku_bits_simple);
bench!(assert Solution::solve_sudoku_bits_record);
bench!(assert Solution::solve_sudoku_bits_valid_record);
}