专栏文章

P10482 Sudoku2 题解

P10482题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqyifm4
此快照首次捕获于
2025/12/04 12:49
3 个月前
此快照最后确认于
2025/12/04 12:49
3 个月前
查看原文

P10482 Sudoku2

蓝书上来的,看到没有人写 DFS 位运算常数优化,于是来写一下,帮助其他和我一样不会的蒟蒻

常数优化

对于每行、每列、每个九宫格,分别用一个 9 位二进制数(全局整数变量)保存哪些数字还可以填
对于每个位置,把它所在行、列、九宫格的 3 个二进制数做位与运算(&),就可以得到该位置能填哪些数,用 lowbit 运算就可以把能填的数字取出
当一个位置填上某数后,把该位置所在的行、列、九宫格记录的二进制数的对应位改为 0 ,即可更新当前状态;回溯时改回 1 即可还原现场。
——《算阶》
更多细节下见代码
CPP
#include<iostream>
#define N (1 << 9)//如果写define位运算一定要记得写括号!!!
#define lowbit(x) (x & -x)
using namespace std;
int T,n,a[10][10];
int cnt[N],f[N],x[9],y[9],z[9];
char c;
int gon(int i,int j){//在第几个九宫格
	return i / 3 * 3 + j / 3;
}
int get_cnt(int i){//二进制下有多少个1,即为可填的数字个数
	int ans=0;
	while(i) ans++ , i-=lowbit(i);
	return ans;
}
void work(int i,int j,int v){
	x[i] ^= (1<<v);//异或的成对变换的运用
	y[j] ^= (1<<v);
	z[gon(i,j)] ^= (1<<v);
}
bool dfs(int tot){
	if(!tot)return true;//找到则返回
	int t=10,nx,ny;
	for(int i=0;i<=8;i++){
		for(int j=0;j<=8;j++){
			if(!a[i][j]){
				int w = x[i] & y[j] & z[gon(i,j)];
				if(cnt[w]<t) nx=i,ny=j,t=cnt[w];//找到能填数目最小的
			}
		}
	}	
	int w=x[nx]&y[ny]&z[gon(nx,ny)];
	while(w){
		int now=f[lowbit(w)];
		a[nx][ny]=now+1;
		work(nx,ny,now);
		if(dfs(tot-1)) return true;
		a[nx][ny]=0;
		work(nx,ny,now);//回溯
		w-=lowbit(w);
	}
	return false;
}
int main(){
	for(int i=0;i<N;i++){
		cnt[i]=get_cnt(i);
	}
	for(int i=0;i<=8;i++){
		f[1<<i]=i;
	}
	while(1){
		int tot=0;
		for(int i=0;i<=8;i++){
			x[i]=y[i]=z[i]=N-1;
		}
		for(int i=0;i<=8;i++){
			for(int j=0;j<=8;j++){
				cin>>c;
				if(c=='e'){
					return 0;
				}
				else if(c=='.')
					a[i][j]=0;
				else{
					a[i][j]=c-'0';
				}
				if(a[i][j]) work(i,j,a[i][j]-1);
				else{
					tot++;
				}
			}
	}
		if(dfs(tot)){
			for(int i=0;i<=8;i++){
				for(int j=0;j<=8;j++){
					printf("%d",a[i][j]);
				}
			}
		}
		cout<<endl;
    }
	return 0;
}

评论

2 条评论,欢迎与作者交流。

正在加载评论...