补充知识点
DFS常用的剪枝思路:(1)优化搜索顺序;(2)排除冗余信息;(3)可行性剪枝;(4)最优化剪枝。
按照上述的剪枝思路,本题的剪枝方法是:对于所有尚未填上数字的位置,优先从可填数字最少的位置进行搜索(对应思路(1))。
import java.util.*;
public class Main{
static int N = 9;
static char[][] w = new char[N][N];
static int[] row = new int[N]; // 每行能放1-9中的哪些数,用前九个二进制位表示能不能放,1表示能放
static int[] col = new int[N]; // 每列能放1-9中的哪些数
static int[][] cell = new int[3][3]; // 每个3x3九宫格中能放哪些数
static int[] ones = new int[1 << N]; // [0, 1 << N)中每个数所包含的1的个数
static char[] map = new char[1 << N]; // 十进制数与能放的数(1-9)之间的映射
// 预处理出ones数组和map数组
public static void init_global(){
for(int i = 0; i < N; i ++) map[1 << i] = (char)('0' + i + 1);
for(int i = 0; i < 1 << N; i ++){
int cnt = 0;
for(int j = i; j > 0; j -= lowbit(j)) cnt ++;
ones[i] = cnt;
}
}
// 初始化row,col,cell数组
public static void init(){
for(int i = 0; i < N; i ++){
row[i] = (1 << N) - 1;
col[i] = (1 << N) - 1;
cell[i / 3][i % 3] = (1 << N) - 1;
}
}
public static int lowbit(int x){
return x & -x;
}
public static int unite(int x, int y){
return row[x] & col[y] & cell[x / 3][y / 3];
}
public static boolean dfs(int u){
if(u == 0) return true;
// 找出当前为'.'的、且可以填的数字最少的位置
int x = -1, y = -1, min = 10;
for(int i = 0; i < N; i ++)
for(int j = 0; j < N; j ++)
if(w[i][j] == '.')
if(ones[unite(i, j)] < min){
min = ones[unite(i, j)];
x = i;
y = j;
}
// 从前面找到的位置开始dfs
// 对可填的数字进行枚举
for(int i = unite(x, y); i > 0; i -= lowbit(i)){
int lb = lowbit(i);
row[x] -= lb;
col[y] -= lb;
cell[x / 3][y / 3] -= lb;
w[x][y] = map[lb];
if(dfs(u - 1)) return true;
row[x] += lb;
col[y] += lb;
cell[x / 3][y / 3] += lb;
w[x][y] = '.';
}
return false;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
init_global();
while(sc.hasNext()){
String s = sc.next();
if(s.charAt(0) == 'e') break;
for(int i = 0; i < 81; i ++) w[i / 9][i % 9] = s.charAt(i);
init();
int cnt = 0;
for(int i = 0; i < N; i ++)
for(int j = 0; j < N; j ++)
if(w[i][j] != '.'){
int v = w[i][j] - '0';
row[i] -= 1 << (v - 1);
col[j] -= 1 << (v - 1);
cell[i / 3][j / 3] -= 1 << (v - 1);
}else cnt ++;
// dfs
StringBuilder res = new StringBuilder();
if(dfs(cnt)){
for(int i = 0; i < N; i ++)
for(int j = 0; j < N; j ++)
res.append(w[i][j]);
System.out.println(res.toString());
}
}
}
}