AcWing 166. 数独(Java 暴搜)
原题链接
中等
作者:
Limited
,
2021-02-08 20:09:27
,
所有人可见
,
阅读 462
要点
- 选取最小搜索分支
- 每个空位可选择的数字个数不定,每次先遍历所有空位,找到可选方案数最小的位置优先尝试
- 使用二进制数记录使用状态
- 用int的低九位记录数字使用状态
- 求某格可选数字只需某格所在 行、列、九宫格的状态表示按位与 如
row[i] & col[j] & cell[k]
- lowbit求二进制数的数值最小的含1序列 如 110110010 ==> 10
- 打表 存$2^9$内所有数字各自的二进制表示中含1总数,以及某个
10*
的序列对应数字
- 如果某格可填但可选方案数为0,证明当前方案必定无解,需特判退出(不退出能AC,但总觉得有bug,数据问题?)
代码
import java.lang.*;
import java.util.*;
public class Main {
static Scanner scanner = new Scanner(System.in);
static int[] ones = new int[1 << 9], map = new int[1 << 9];
static int[] row = new int[10], col = new int[10], cell = new int[10];
static int[][] f = new int[10][10];
// 固定写法 获取最后一个10*序列
static int lowbit(int x) {
return x & (-x);
}
// 获取(x,y)所属九宫格编号 从左到右从上到下从0开始编号
// 0 1 2
// 3 4 5
// 6 7 8
static int getCellIndex(int x, int y) {
return x / 3 * 3 + y / 3;
}
// 获取(x,y)格当前数字可选择情况 值为一个int 低九位有效二进制数 从右到左从0开始
// 876543210
// 100100101 ===> 表示数字0、2、5、8可用
static int getStatus(int x, int y) {
return row[x] & col[y] & cell[getCellIndex(x, y)];
}
// 传入参数为待填空总个数
static boolean dfs(int n) {
// 待填个数为0时 方案可行 返回true
if (n == 0) {
return true;
}
// minv记录当前最小可选方案数 (x,y)为拥有最小可选数的空位坐标
int minv = Integer.MAX_VALUE, x = -1, y = -1;
// 遍历所有格子 找到可选方案最小的格子 即最短分支
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
// ones[number] 用于查找number的低九位共有多少个1 即有多少个可选方案
int temp = ones[getStatus(i, j)];
// f[i][j]<0 即为待填空格
if (f[i][j] < 0) {
// 如本格可选方案为0 证明无可填数字 本方案无解
if (temp == 0) {
return false;
} else if (temp < minv) {
minv = temp;
x = i;
y = j;
}
}
}
}
// 遍历所有方案
for (int i = getStatus(x, y); i > 0; i -= lowbit(i)) {
// map[number] 返回低九位的1代表哪个数字 此处事先保证number的二进制表示有且仅有一个1
int temp = map[lowbit(i)];
// 该空位赋值
f[x][y] = temp;
// 在row、col、cell中标记该值已使用
row[x] -= 1 << temp;
col[y] -= 1 << temp;
cell[getCellIndex(x, y)] -= 1 << temp;
// 递归下一个空位 注意总数-1 如果方案最终可行 将逐层返回true
if (dfs(n - 1)) {
return true;
}
// 方案不可行则还原现场 进行下一个方案
f[x][y] = -3;
row[x] += 1 << temp;
col[y] += 1 << temp;
cell[getCellIndex(x, y)] += 1 << temp;
}
return false;
}
public static void main(String[] args) {
// 打表 map[x]表示x的低九位的1代表哪个数字 使用时保证x的二进制表示有且仅有一个1
for (int i = 0; i < 9; i++) {
map[1 << i] = i;
}
// 打表 ones[x]记录x的低九位共有多少个1
for (int i = 0; i < (1 << 9); i++) {
for (int j = i; j > 0; j -= lowbit(j)) {
ones[i]++;
}
}
String str;
while (!"end".equals(str = scanner.next())) {
char[] chs = str.toCharArray();
// n记录待填空位总数
int n = 0;
// 初始化row、col、cell为 111111111 表示数字0~8均可用
Arrays.fill(row, (1 << 9) - 1);
Arrays.fill(col, (1 << 9) - 1);
Arrays.fill(cell, (1 << 9) - 1);
// 转输出字符为数字 1~9偏移一位到0~8 待填位置赋值-2以作区分
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (chs[i * 9 + j] == '.') {
f[i][j] = -2;
n++;
} else {
f[i][j] = chs[i * 9 + j] - '1';
// 更新行、列、对应九宫格的数字使用状态
row[i] -= 1 << f[i][j];
col[j] -= 1 << f[i][j];
cell[getCellIndex(i, j)] -= 1 << f[i][j];
}
}
}
dfs(n);
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(f[i][j] + 1);
}
}
System.out.println();
}
}
}
强,很清楚