在这里插入图片描述

166. 数独

显然要用到DFS，对于每个未填的空格，要排除掉同行同列同九宫内出现过的数字。不加优化不出意外的话会T飞︿(￣︶￣)︿。

考虑剪枝：

  1. 优化搜索顺序
  2. 排除冗余信息
  3. 可行性剪枝（照当前分支这样走后面不可能达成）
  4. 最优性剪枝（照当前分支这样走的最优解都比当前解差）
  5. 记忆化搜索

这里我们主要考虑优化搜索顺序。这其实是跟大家做数独的时候的朴素感知是一样的，从可选的数少的空格开始试探。所以我们在每次搜索时都判断一下哪个格子的可选到数最小（可以预先处理出来可能会用到的所有二进制数里1的个数，用时直接调用）。

记录每个格子可选的数，可以用二进制状态压缩，开九位表示九个数。为了方便，我们把1~9映射成0 ~8。开三个数组$row[N],col[N],cell[N/3][N/3]$分别记录每行、每列、每个九宫格内有哪些数不能填。对于位置在$(x,y)$的数，用 row[x] & col[y] & cell[x/3][y/3] 可以查到该空格可以填哪些数，那就老老实实搜索这些数吧233，可以用lowbit获得二进制下为1的每一位，将其转化成十进制数（1的位置对应的位数，可以预先处理出来）。搜索到每一个数时改变一下row.col.cell的状态，回溯的时候复原。

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h> 
using namespace std;
const int N=9;
string str;
int mp[1<<N],nums[1<<N],row[N],col[N],cell[N][N];

inline int lowbit(int x)
{
	return x&(-x);
}

int get(int x,int y)
{
	return row[x]&col[y]&cell[x/3][y/3];//求出这一个位置可能会被填哪些数字 
}

void init()//初始化：所有位所有数字都可以填 
{
	for(int i=0;i<N;i++) 
		row[i]=col[i]=(1<<N)-1;
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			cell[i][j]=(1<<N)-1;
}

bool dfs(int cnt)
{
	if(cnt==0) return true;//所有待填数字都已经被填上 
	int minn=10,x,y;
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
		{
			if(str[i*9+j]=='.')
			{
				int temp=nums[get(i,j)];
				if(temp<minn)
				{
					minn=temp;
					x=i,y=j;
				}
			}
		}//找到所有剩下的待填格中数字集合最小的一个，是一个剪枝过程 
	for(int i=get(x,y);i;i-=lowbit(i))//枚举这一格所有可能填的数字 
	{
		int t=mp[lowbit(i)];
		row[x]-=(1<<t);
		col[y]-=(1<<t);
		cell[x/3][y/3]-=(1<<t);
		str[x*9+y]='1'+t;
		if(dfs(cnt-1)) return true;
		row[x]+=(1<<t);
		col[y]+=(1<<t);
		cell[x/3][y/3]+=(1<<t);
		str[x*9+y]='.';//复原 
	}
	return false;
}


int main()
{
	for(int i=0;i<N;i++) mp[1<<i]=i;//预先存下二进制1所在的位置 
	for(int i=1;i<(1<<N);i++)
		for(int j=i;j;j-=lowbit(j)) nums[i]++;
		//预先存下每个之后可能会枚举到的二进制数内有几个1 
	while(cin>>str&&str[0]!='e')
	{
		init();
		int cnt=0;
		for(int i=0,k=0;i<9;i++)
			for(int j=0;j<9;j++,k++)
			{
				if(str[k]!='.')
				{
					int t=str[k]-'1';//1~9映射到0~8 
					row[i]-=(1<<t);
					col[j]-=(1<<t);
					cell[i/3][j/3]-=(1<<t);
				}//这一位数字是题给的，把它存进对应位置 
				else cnt++;//待填数字+1 
			}
		dfs(cnt);
		cout<<str<<endl;
	}
	return 0;
}