算法1
dfs + 位运算
-
1、通过位运算表示描绘出当前的局面,某一行某一列某一某一宫格均用
1
个长度是9
为的二进制数表示,若当前位置是1
表示该行该列或者该宫格可填入 -
2、在选择当前需要填数的位置时,选择分支最少的格子
-
3、
state = row[x] & col[y] & cell[x / 3][y / 3]
表示当前位置(x,y)
可填数的状态,某二进制为是1
表示可填该数
参考文献
算法提高课
Java 代码
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
static char[] str;
static int[] ones = new int[1 << 9];
static int[] row = new int[9];
static int[] col = new int[9];
static int[][] cell = new int[3][3];
static Map<Integer,Integer> map = new HashMap<Integer,Integer>();
//初始化二进制全是1,表示均可以选择
static void init()
{
Arrays.fill(row, (1 << 9) - 1);
Arrays.fill(col, (1 << 9) - 1);
for(int i = 0;i < 3;i ++) Arrays.fill(cell[i], (1 << 9) - 1);
}
//若isSet为true 则填进n数,否则恢复现场
static void draw(int x, int y, int n, boolean isSet) {
if (isSet) {
str[x * 9 + y] = (char) ('1' + n);
}
else str[x * 9 + y] = '.';
int dv = 1 << n;
if (!isSet) dv = -dv;
row[x] -= dv;
col[y] -= dv;
cell[x / 3][y / 3] -= dv;
}
static int lowbit(int x)
{
return x & -x;
}
public static boolean dfs(int cnt) {
if (cnt == 0) return true;
//选择分支最少的格子
int min = 10, x = -1, y = -1;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (str[i * 9 + j] == '.') {
int options = ones[row[i] & col[j] & cell[i / 3][j / 3]];
if (options < min) {
min = options;
x = i;
y = j;
}
}
}
}
int state = row[x] & col[y] & cell[x / 3][y / 3];
int op = ones[state];
for (int i = state; i != 0; i -= lowbit(i)) {
int n = map.get(lowbit(i));
draw(x, y, n, true);
if (dfs(cnt - 1)) return true;
draw(x, y, n, false);
}
return false;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//预处理0到(1 << 9) - 1中有多少个1
for(int i = 0;i < 1 << 9;i ++)
{
for(int j = 0;j < 9;j ++)
ones[i] += i >> j & 1;
}
//预处理二进制的第几位
for(int i = 0;i < 9;i ++) map.put(1 << i, i);
while(true)
{
String temp = scan.next();
if (temp.equals("end")) break;
str = temp.toCharArray();
init();
//描绘出当前九宫格的局势
int count = 81;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (str[i * 9 + j] != '.') {
draw(i, j, str[i * 9 + j] - '1', true);
count--;
}
}
}
dfs(count);
System.out.println(new String(str));
}
}
}
这道题目搜索的时候假如不定义成bool dfs()而是直接用void dfs()去搜会是神马情况?神马情况下dfs要定义成返回bool 类型