题意

9宫格数独填数

思路

先做这道题

在上题中我们用搜索回溯找出正确的解

但是这道题用那道题的代码(有输入输出改动)提交,会TLE

先考虑较简单的一个优化

• 状压

顾名思义,将存储状态的数组降维

注意到,记录"行,列,宫"不可用的位置,可以从二维到一维

所以,写一个新的函数,更改这个状压的某一位的值

0为这个数字没有被填,1反之

//*s为改的数组指针(row/line/gong),x为行(1~9),y为列(1~9),k为改的值(0/1)
void set_(int *s,int x,int y,bool k)
{
	if(k)s[x]|=(1<<y);
	else s[x]&=(~(1<<y));
}

• 填数

在上面,用状压记录那些数字哪些可以填,哪些数字不可以填

但是,如何获取哪些数字可以填哪些不可以填

考虑用位运算

一个循环i从1~9,如果"行,列,宫"都是0就可以填

如何获取某一位的值(0/1)

//*s为改的数组指针(row/line/gong),x为行(1~9),y为列(1~9)
bool check(int *s,int x,int y)
{
	return s[x]&(1<<y);
}

注意到,我们还可以用"| & ~"更快地获取哪一位可以填,这样就不用"check()"了

//m[x][y]为第x行第y列的格子属于哪个宫
t= ~ ( row[x] | line[y] | gong[m[x][y]] )

这样就可以通过叠加求出哪些可以填

考虑for循环遍历这个状压,如果是1则填这个数,0反之

还可以用"lowbit+数组",更快的找出填的数

• 搜索顺序

上面的两种优化都写对了之后照样TLE

这是寻找最优解,并非要全部遍历完

所以,可以通过优化搜索顺序提升效率

想一想,要如何优化搜索顺序?

实现:

最先搜索 能填数字最少 的点

最后搜索 能填数字最多 的点

这样能大幅提高搜索效率(这是真的!)

写一个函数,找出9*9中能填数字最少的点(不含已填的)

还是通过叠加找出最少能填的点

使用popcount()求出某个点"1"的个数(可以提前做预处理)

得到相应的点后对这点后进行"搜索+回溯"

因此,搜索函数有所改变(建议参考代码):

搜索函数的形参为"dep",记录搜索深度(填数个数,为0时说明所有空点填完了)

在"main"中需要记录这个数独有多少个空点(tot),再进行dfs(tot)

代码

#include<bits/stdc++.h>
using namespace std;
int sk[10][10];
bool Flag=0;
int m[10][10]=
{
	{},
	{0,1,1,1,2,2,2,3,3,3},
	{0,1,1,1,2,2,2,3,3,3},
	{0,1,1,1,2,2,2,3,3,3},
	{0,4,4,4,5,5,5,6,6,6},
	{0,4,4,4,5,5,5,6,6,6},
	{0,4,4,4,5,5,5,6,6,6},
	{0,7,7,7,8,8,8,9,9,9},
	{0,7,7,7,8,8,8,9,9,9},
	{0,7,7,7,8,8,8,9,9,9}
};
int row[10],line[10],gong[10],f[1<<10];

void init()
{
	for(int i=1;i<(1<<10);i++)
		f[i]=__builtin_popcount(i);//预处理
}
void clear()
{
	memset(row,0,sizeof row);
	memset(line,0,sizeof line);
	memset(gong,0,sizeof gong);
	Flag=0;
}
void set_(int *s,int x,int y,bool k)//更改位
{
	if(k)s[x]|=(1<<y);
	else s[x]&=(~(1<<y));
}
pair<pair<int,int>,int>get_min()//获取最优点
{
	int mi=0;
	pair<int,int>xy={0,0};
	for(int i=1;i<=9;i++)
		for(int j=1;j<=9;j++)
		{
			if(sk[i][j])continue;
			int s=row[i]|line[j]|gong[m[i][j]];
			if(f[s]>f[mi])xy=pair<int,int>{i,j},mi=s;
		}
	return pair<pair<int,int>,int>{xy,mi};//位置+行,列,宫的情况
}
bool dfs(int dep)
{
	if(!dep)return 1;//填完了
	pair<pair<int,int>,int>xy=get_min();
	int x=xy.first.first,y=xy.first.second,t=~xy.second;
	for(int i=1;i<=9;i++)
	{
		t>>=1;
		if(!(t&1))continue;//这个数字不可填
		set_(row,x,i,1),set_(line,y,i,1),set_(gong,m[x][y],i,1);
		sk[x][y]=i;
		if(dfs(dep-1))return 1;
		sk[x][y]=0;
		set_(row,x,i,0),set_(line,y,i,0),set_(gong,m[x][y],i,0);
	}
	return 0;
}
int main()
{
	init();
	while(1)
	{
		clear();
		int tot=0;
		for(int i=1;i<=9;i++)
		{
			for(int j=1;j<=9;j++)
			{
				char o;cin>>o;
				if(o=='e')return 0;
				sk[i][j]=(o=='.'?(++tot&&0):o-48);//记录要填的个数
				set_(row,i,sk[i][j],1);
				set_(line,j,sk[i][j],1);
				set_(gong,m[i][j],sk[i][j],1);
			}	
		}
		if(dfs(tot))
			for(int i=1;i<=9;i++)
				for(int j=1;j<=9;j++)
					cout<<sk[i][j];
		cout<<"\n";
	}	
	return 0;
}