https://www.acwing.com/problem/content/168/

数独

#include<bits/stdc++.h>
#define M 9
using namespace std;
string s;
int now;
int Map[1<<M],row[M],col[M],cel[3][3],ones[M]; 
int lowbit(int x){
	return x&-x;
}
void push(int x,int y,int t,bool f){
	if(f==true) s[x*M+y]=48+t;
	else s[x*M+y]='.';
	int v=1<<t;
	if(f==false) v=-v;
	row[x]-=v; 
	col[y]-=v;  
	cel[x/3][y/3]-=v;
}
int get(int x,int y){
	return row[x]&col[y]&cel[x/3][y/3];
}
int init(){
	int cnt=0,state=(1<<M)-1;
	for(int i=0;i<M;i++) row[i]=state,col[i]=state;
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			cel[i][j]=state;
	for(int i=0,k=0;i<M;i++){
		for(int j=0;j<M;j++,k++){
			if(s[k]!='.'){
				push(i,j,s[k]-48,true);
			}else cnt++;
		}
	}
	return cnt;
}
bool dfs(int cnt){
	if(!cnt) return true;
	int minv=10,x,y;
	for(int i=0;i<M;i++){
		for(int j=0;j<M;j++){
			if(s[i*M+j]=='.'){
				int state=get(i,j);
				if(ones[state]<minv){
					minv=ones[state];
					x=i,y=j;
				}
			}
		}
	} 
	for(int i=get(x,y);i;i-=lowbit(i)){
		int t=Map[lowbit(i)];
		push(x,y,t,true);
		if(dfs(cnt-1)) return true;
		push(x,y,t,false);
	}
}
int main(){
	for(int i=0;i<M;i++) Map[1<<i]=i;
	for(int i=0;i<M;i++){
		for(int j=i;j!=0;j-=lowbit(j)){
			ones[i]++;
		}
	}
	while(cin>>s,s!="end"){
		now=init();		
		dfs(now);
		cout<<s<<endl;
	}
	return 0;
}