2022-06-05：不规则数独问题。
3*3填数独，
每一行要填1~3，
每一列要填1~3，
3*3的区域会拆分成不规则的三个集团区域，
每个集团区域3个格子，
每个集团的区域都一定是一个连在一起的整体，可能不规则，
每个集团内要填1~3，
如果只有一个解返回"Unique"，如果有多个解返回"Multiple"，如果没有解返回"No"。
解析请看，大厂刷题班，28节，leetcode原题，数独那两个题。
本题就是改变一下桶的归属而已。
来自网易。
答案2022-06-05：
具体见代码。
代码用rust编写。代码如下：
代码语言：rust复制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;
}
}执行结果如下：
在这里插入图片描述左神java代码
