题意

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;
}

LYD蓝书做法整理。位运算优化 165ms 完美通过。如果交到 P10481，可以 4ms AC。

//常数优化
//1.对于每行每列每个九宫格，分别用一个 9 位二进制保存有哪些数能用。
//2.对于每个数字，把它所在的行、列、九宫格的三个二进制数做按位与运算，
//就可以知道该位置可以填哪些数，再用 lowbit 运算就可以将能填的数字取出。
//3.当一个位置上填上某个数后，把该位置所在行、列、九宫格的二进制数对应位改为 0 更新装态，
//回溯时改为 1 还原现场。可以利用异或的性质来省去判断是搜索还是回溯。
//4.用 lowbit 运算预处理每个 9 位二进制数有几位 1 ，即可快速确定能填的合法数字最少的位置。
//5.打表确定用 lowbit 运算取出来的位置对应的数字。例如f['0001']=1，f['0100']=3。
#include <iostream>
#include <cstdio>
using namespace std;

int s[9][9]; // 记录数独题面
int x[9], y[9], z[9]; // 记录每行、每列、每宫的填写情况
// 例如 x[3][0] 为1，表示第3行还能填数字1（=0+1）

const int N = 1 << 9;
int cnt[N], f[N]; // 打表用的
void init() {
	for (int i = 1; i < N; i++) cnt[i] = __builtin_popcount(i); // 优化4
	for (int i = 0; i < 9; i++) f[1 << i] = i + 1; // 优化5
}

inline int gong(int i, int j) {
	return i / 3 * 3 + j / 3;
}

void fill(int i, int j, int v) {
	int t = 1 << v;
	x[i] ^= t;
	y[j] ^= t;
	z[gong(i, j)] ^= t; // 异或，就不用判断是搜索还是回溯在改状态了
}

// rest表示剩下还要填的数的个数
bool dfs(int rest) {
	if (!rest) return true;
	// 优化搜索顺序：寻找能填的合法数字最少的位置。
	// nx、ny记录位置，tmp记录最少个数。
	int nx = 0, ny = 0, min_cnt = 10;
	for (int i = 0; i < 9; i++)
		for (int j = 0; j < 9; j++) {
			if (!s[i][j]) {
				int t = x[i] & y[j] & z[gong(i, j)]; // 优化2
				if (cnt[t] < min_cnt)
					nx = i, ny = j, min_cnt = cnt[t];
//				printf("dbg: x=%d y=%d min_cnt=%d\n", nx, ny, min_cnt);
			}
		}
	int t = x[nx] & y[ny] & z[gong(nx, ny)];
	// 可填的数字一个个尝试
	while (t) {
		int now = f[t & -t]; // now就是lowbit(t)这个状态对应的数字
//		printf("dbg: now=%d\n", now);
		s[nx][ny] = now;
		fill(nx, ny, now - 1);
		if (dfs(rest - 1)) return true;
		// 回溯
		s[nx][ny] = 0;
		fill(nx, ny, now - 1); // 撤销上面dfs(rest-1)更深层的递归造成的修改
		t -= (t & -t); // t-=lowbit(t)
	}
	return false;
}

int main() {
	init();

	string str;
	cin >> str;
	while (str != "end") {
		// 注意多测的全局变量设置
		for (int i = 0; i < 9; i++) x[i] = y[i] = z[i] = N - 1; // 优化1
		int tot = 0; // 记录需要填的空的数量
		for (int i = 0; i < 9; i++)
			for (int j = 0; j < 9; j++) {
				char ch = str[i * 9 + j];
				if (ch == '.') s[i][j] = 0;
				else s[i][j] = ch - '0';
				if (s[i][j]) fill(i, j, s[i][j] - 1);
				else tot++;
			}

		if (dfs(tot)) {
			for (int i = 0; i < 9; i++)
				for (int j = 0; j < 9; j++)
					cout << s[i][j];
			cout << '\n';
		}

		cin >> str;
	}
	return 0;
}