数独(搜索练习)

发表于

原题

Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 11304 Accepted: 4028

Description

In the game of Sudoku, you are given a large 9 × 9 grid divided into smaller 3 × 3 subgrids. For example,.2738..1..1…6735…….293.5692.8………..6.1745.364…….9518…7..8..6534.Given some of the numbers in the grid, your goal is to determine the remaining numbers such that the numbers 1 through 9 appear exactly once in (1) each of nine 3 × 3 subgrids, (2) each of the nine rows, and (3) each of the nine columns.

Input

The input test file will contain multiple cases. Each test case consists of a single line containing 81 characters, which represent the 81 squares of the Sudoku grid, given one row at a time. Each character is either a digit (from 1 to 9) or a period (used to indicate an unfilled square). You may assume that each puzzle in the input will have exactly one solution. The end-of-file is denoted by a single line containing the word “end”.

Output

For each test case, print a line representing the completed Sudoku puzzle.

Sample Input

1
2
3
.2738..1..1...6735.......293.5692.8...........6.1745.364.......9518...7..8..6534.
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end

Sample Output

1
2
527389416819426735436751829375692184194538267268174593643217958951843672782965341
416837529982465371735129468571298643293746185864351297647913852359682714128574936

解题

大致意思就是说将一个99的数独补充完整 使得每行，每列，每个3 3的九宫格内数字1-9恰好出现一次

如果用朴素的dfs,搜索树很大，一定会炸

可以考虑，如果我们玩数独，会从所有未填的位置里选择 能填的数最少 的位置，而不是认意找一个位置

对于每行，每列，每个九宫格分别用一个9位二进制数保存哪些数字还可以填

对于每个位置，把它所在的行，列，九宫格分别作&运算，就可以得到该位置可以填什么数，使用lowbit运算把能填的数取出

当一个位置填上数后，把行，列，九宫格相应的二进制位改为0，回溯时改回1还原现场

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char str[10][10];
int row[9], col[9], grid[9], cnt[512], num[512], tot;

inline int g(int x, int y) {
	return ((x / 3) * 3) + (y / 3);
}

inline void flip(int x, int y, int z) {
	row[x] ^= 1 << z;
	col[y] ^= 1 << z;
	grid[g(x, y)] ^= 1 << z;
}

bool dfs(int now) {
	if (now == 0) return 1;
	int temp = 10, x, y;
	for (int i = 0; i < 9; i++)
		for (int j = 0; j < 9; j++) {
			if (str[i][j] != '.') continue;
			int val = row[i] & col[j] & grid[g(i, j)];
			if (!val) return 0;
			if (cnt[val] < temp) {
				temp = cnt[val];
				x = i, y = j;
			}
		}
	int val = row[x] & col[y] & grid[g(x, y)];
	for (; val; val -= val&-val) {
		int z = num[val&-val];
		str[x][y] = '1' + z;
		flip(x, y, z);
		if (dfs(now - 1)) return 1;
		flip(x, y, z);
		str[x][y] = '.';
	}
	return 0;
}

int main() {
	for (int i = 0; i < 1 << 9; i++)
		for (int j = i; j; j -= j&-j) cnt[i]++;
	for (int i = 0; i < 9; i++)
		num[1 << i] = i;
	char s[100];
	while (~scanf("%s", s) && s[0] != 'e') {
		for (int i = 0; i < 9; i++)
			for (int j = 0; j < 9; j++) str[i][j] = s[i * 9 + j];
		for (int i = 0; i < 9; i++) row[i] = col[i] = grid[i] = (1 << 9) - 1;
		tot = 0;
		for (int i = 0; i < 9; i++)
			for (int j = 0; j < 9; j++)
				if (str[i][j] != '.') flip(i, j, str[i][j] - '1');
				else tot++;
		dfs(tot);
		for (int i = 0; i < 9; i++)
			for (int j = 0; j < 9; j++) s[i * 9 + j] = str[i][j];
		puts(s);
	}
}