|
|
package class_2022_03_4_week;
|
|
|
|
|
|
// 来自网易
|
|
|
// 不规则数独问题
|
|
|
// 3*3填数独
|
|
|
// 每一行要填1~3
|
|
|
// 每一列要填1~3
|
|
|
// 3*3的区域会拆分成不规则的三个集团区域
|
|
|
// 每个集团区域3个格子
|
|
|
// 每个集团的区域都一定是一个连在一起的整体，可能不规则
|
|
|
// 每个集团内要填1~3
|
|
|
// 如果只有一个解返回"Unique"，如果有多个解返回"Multiple"，如果没有解返回"No"
|
|
|
// 解析请看，大厂刷题班，28节，leetcode原题，数独那两个题
|
|
|
// 本题就是改变一下桶的归属而已
|
|
|
public class Code07_IrregularSudoku {
|
|
|
|
|
|
// sudoku[i][j] == 0，代表这个位置没有数字，需要填
|
|
|
// sudoku[i][j] != 0，代表这个位置有数字，不需要填
|
|
|
// map[0] = {0,0}、{0,1}、{1,0} 代表0集团拥有的三个点
|
|
|
// map[i] = {a,b}、{c,d}、{e,f} 代表i集团拥有的三个点
|
|
|
public static String solution(int[][] sudoku, int[][][] map) {
|
|
|
boolean[][] row = new boolean[3][4];
|
|
|
boolean[][] col = new boolean[3][4];
|
|
|
boolean[][] bucket = new boolean[3][4];
|
|
|
int[][] own = new int[3][3];
|
|
|
for (int i = 0; i < 3; i++) {
|
|
|
for (int[] arr : map[i]) {
|
|
|
own[arr[0]][arr[1]] = i;
|
|
|
}
|
|
|
}
|
|
|
for (int i = 0; i < 3; i++) {
|
|
|
for (int j = 0; j < 3; j++) {
|
|
|
if (sudoku[i][j] != 0) {
|
|
|
row[i][sudoku[i][j]] = true;
|
|
|
col[j][sudoku[i][j]] = true;
|
|
|
bucket[own[i][j]][sudoku[i][j]] = true;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
int ans = process(sudoku, 0, 0, row, col, bucket, own);
|
|
|
return ans == 0 ? "No" : (ans == 1 ? "Unique" : "Multiple");
|
|
|
}
|
|
|
|
|
|
public static int process(int[][] sudoku, int i, int j, boolean[][] row, boolean[][] col, boolean[][] bucket,
|
|
|
int[][] own) {
|
|
|
if (i == 3) {
|
|
|
return 1;
|
|
|
}
|
|
|
int nexti = j != 2 ? i : i + 1;
|
|
|
int nextj = j != 2 ? j + 1 : 0;
|
|
|
if (sudoku[i][j] != 0) {
|
|
|
return process(sudoku, nexti, nextj, row, col, bucket, own);
|
|
|
} else {
|
|
|
int ans = 0;
|
|
|
int bid = own[i][j];
|
|
|
for (int num = 1; num <= 3; num++) {
|
|
|
if ((!row[i][num]) && (!col[j][num]) && (!bucket[bid][num])) {
|
|
|
row[i][num] = true;
|
|
|
col[j][num] = true;
|
|
|
bucket[bid][num] = true;
|
|
|
sudoku[i][j] = num;
|
|
|
ans += process(sudoku, nexti, nextj, row, col, bucket, own);
|
|
|
row[i][num] = false;
|
|
|
col[j][num] = false;
|
|
|
bucket[bid][num] = false;
|
|
|
sudoku[i][j] = 0;
|
|
|
if (ans > 1) {
|
|
|
return ans;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
return ans;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
public static void main(String[] args) {
|
|
|
int[][] sudoku1 = {
|
|
|
{ 0, 2, 0 },
|
|
|
{ 1, 0, 2 },
|
|
|
{ 0, 0, 0 }
|
|
|
};
|
|
|
int[][][] map1 = {
|
|
|
{ { 0, 0 }, { 0, 1 }, { 1, 0 } },
|
|
|
{ { 0, 2 }, { 1, 1 }, { 1, 2 } },
|
|
|
{ { 2, 0 }, { 2, 1 }, { 2, 2 } }
|
|
|
};
|
|
|
System.out.println(solution(sudoku1, map1));
|
|
|
|
|
|
int[][] sudoku2 = {
|
|
|
{ 0, 0, 3 },
|
|
|
{ 0, 0, 0 },
|
|
|
{ 0, 0, 0 }
|
|
|
};
|
|
|
int[][][] map2 = {
|
|
|
{ { 0, 0 }, { 1, 0 }, { 1, 1 } },
|
|
|
{ { 0, 1 }, { 0, 2 }, { 1, 2 } },
|
|
|
{ { 2, 0 }, { 2, 1 }, { 2, 2 } }
|
|
|
};
|
|
|
System.out.println(solution(sudoku2, map2));
|
|
|
|
|
|
int[][] sudoku3 = {
|
|
|
{ 0, 0, 3 },
|
|
|
{ 1, 0, 0 },
|
|
|
{ 0, 0, 2 }
|
|
|
};
|
|
|
int[][][] map3 = {
|
|
|
{ { 0, 0 }, { 1, 0 }, { 1, 1 } },
|
|
|
{ { 0, 1 }, { 0, 2 }, { 1, 2 } },
|
|
|
{ { 2, 0 }, { 2, 1 }, { 2, 2 } }
|
|
|
};
|
|
|
System.out.println(solution(sudoku3, map3));
|
|
|
|
|
|
int[][] sudoku4 = {
|
|
|
{ 3, 0, 3 },
|
|
|
{ 1, 0, 0 },
|
|
|
{ 0, 0, 2 }
|
|
|
};
|
|
|
int[][][] map4 = {
|
|
|
{ { 0, 0 }, { 1, 0 }, { 1, 1 } },
|
|
|
{ { 0, 1 }, { 0, 2 }, { 1, 2 } },
|
|
|
{ { 2, 0 }, { 2, 1 }, { 2, 2 } }
|
|
|
};
|
|
|
System.out.println(solution(sudoku4, map4));
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
