2022-06-05：不规则数独问题。3*3填数独，每一行要填1~3，每一列要填1~3，3*3的区域会拆分成不规则的三个集团区域

fn main() {
    let mut sudoku1: Vec<Vec<i32>> = vec![vec![0, 2, 0], vec![1, 0, 2], vec![0, 0, 0]];
    let mut map1: Vec<Vec<Vec<i32>>> = vec![
        vec![vec![0, 0], vec![0, 1], vec![1, 0]],
        vec![vec![0, 2], vec![1, 1], vec![1, 2]],
        vec![vec![2, 0], vec![2, 1], vec![2, 2]],
    ];
    println!("{}", solution(&mut sudoku1, &mut map1));

    let mut sudoku2: Vec<Vec<i32>> = vec![vec![0, 0, 3], vec![0, 0, 0], vec![0, 0, 0]];
    let mut map2: Vec<Vec<Vec<i32>>> = vec![
        vec![vec![0, 0], vec![1, 0], vec![1, 1]],
        vec![vec![0, 1], vec![0, 2], vec![1, 2]],
        vec![vec![2, 0], vec![2, 1], vec![2, 2]],
    ];
    println!("{}", solution(&mut sudoku2, &mut map2));

    let mut sudoku3: Vec<Vec<i32>> = vec![vec![0, 0, 3], vec![1, 0, 0], vec![0, 0, 2]];
    let mut map3 = vec![
        vec![vec![0, 0], vec![1, 0], vec![1, 1]],
        vec![vec![0, 1], vec![0, 2], vec![1, 2]],
        vec![vec![2, 0], vec![2, 1], vec![2, 2]],
    ];
    println!("{}", solution(&mut sudoku3, &mut map3));

    let mut sudoku4: Vec<Vec<i32>> = vec![vec![3, 0, 3], vec![1, 0, 0], vec![0, 0, 2]];
    let mut map4 = vec![
        vec![vec![0, 0], vec![1, 0], vec![1, 1]],
        vec![vec![0, 1], vec![0, 2], vec![1, 2]],
        vec![vec![2, 0], vec![2, 1], vec![2, 2]],
    ];
    println!("{}", solution(&mut sudoku4, &mut map4));
}

fn solution(sudoku: &mut Vec<Vec<i32>>, map: &mut Vec<Vec<Vec<i32>>>) -> String {
    let mut row: Vec<Vec<bool>> = vec![];
    let mut col: Vec<Vec<bool>> = vec![];
    let mut bucket: Vec<Vec<bool>> = vec![];
    for i in 0..3 {
        row.push(vec![]);
        col.push(vec![]);
        bucket.push(vec![]);
        for _ in 0..4 {
            row[i as usize].push(false);
            col[i as usize].push(false);
            bucket[i as usize].push(false);
        }
    }
    let mut own: Vec<Vec<i32>> = vec![];
    for i in 0..3 {
        own.push(vec![]);
        for _ in 0..3 {
            own[i as usize].push(0);
        }
    }
    for i in 0..3 {
        for arr in map[i as usize].iter_mut() {
            own[arr[0] as usize][arr[1] as usize] = i;
        }
    }
    for i in 0..3 {
        for j in 0..3 {
            if sudoku[i as usize][j as usize] != 0 {
                row[i as usize][sudoku[i as usize][j as usize] as usize] = true;
                col[j as usize][sudoku[i as usize][j as usize] as usize] = true;
                bucket[own[i as usize][j as usize] as usize]
                    [sudoku[i as usize][j as usize] as usize] = true;
            }
        }
    }
    let ans = process(sudoku, 0, 0, &mut row, &mut col, &mut bucket, &mut own);
    return if ans == 0 {
        "No".to_string()
    } else {
        if ans == 1 {
            "Unique".to_string()
        } else {
            "Multiple".to_string()
        }
    };
}

fn process(
    sudoku: &mut Vec<Vec<i32>>,
    i: i32,
    j: i32,
    row: &mut Vec<Vec<bool>>,
    col: &mut Vec<Vec<bool>>,
    bucket: &mut Vec<Vec<bool>>,
    own: &mut Vec<Vec<i32>>,
) -> i32 {
    if i == 3 {
        return 1;
    }
    let nexti = if j != 2 { i } else { i + 1 };
    let nextj = if j != 2 { j + 1 } else { 0 };
    if sudoku[i as usize][j as usize] != 0 {
        return process(sudoku, nexti, nextj, row, col, bucket, own);
    } else {
        let mut ans = 0;
        let bid = own[i as usize][j as usize];
        for num in 1..=3 {
            if (!row[i as usize][num as usize])
                && (!col[j as usize][num as usize])
                && (!bucket[bid as usize][num as usize])
            {
                row[i as usize][num as usize] = true;
                col[j as usize][num as usize] = true;
                bucket[bid as usize][num as usize] = true;
                sudoku[i as usize][j as usize] = num;
                ans += process(sudoku, nexti, nextj, row, col, bucket, own);
                row[i as usize][num as usize] = false;
                col[j as usize][num as usize] = false;
                bucket[bid as usize][num as usize] = false;
                sudoku[i as usize][j as usize] = 0;
                if ans > 1 {
                    return ans;
                }
            }
        }
        return ans;
    }
}