/// 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);
}