蓝书P114求调

#include <bits/stdc++.h>
using namespace std;
char c[100];
int low[1 << 9],one[1 << 9];
int row[9],col[9],cell[3][3];
int lowbit(int x){
	return x & -x;
}
void init(){
	for(int i = 0;i < 9;i++){
		row[i] = (1 << 9) - 1;
		col[i] = (i << 9) - 1;
	}
	for(int i = 0;i < 3;i++){
		for(int j = 0;j < 3;j++){
			cell[i][j] = (1 << 9) - 1;
		} 
	}
}
bool dfs(int cnt){
	if(cnt == 0) return true;
	int minn = 10;
	int x,y;
	for(int i = 0;i < 9;i++){
		for(int j = 0;j < 9;j++){
			if(c[i * 9 + j] == '.'){
				int t = one[row[x] & col[y] & cell[x / 3][y / 3]];
				if(t < minn){
					minn = t;
					x = i;
					y = j; 
				}
			}
		}
	}
	for(int i = (row[x] & col[y] & cell[x / 3][y / 3]);i;i -= lowbit(i)){
		int t = low[lowbit(i)];
		row[x] -= 1 << t;
		col[y] -= 1 << t;
		cell[x / 3][y / 3] += 1 << t;
		if(dfs(cnt-1)) return true;
		c[x * 9 + y] = '.';
	}
	return false;
}
int main(){
	for(int i = 0;i < 9;i++) low[1 << i] = i;
	for(int i = 0;i < (1 << 9);i++){
		int cnt = 0;
		for(int j = i;j;j -= lowbit(j)) cnt++;
		one[i] = cnt;
	}
	while(cin>>c&&c[0] != 'e'){
		init();
		int cnt = 0;
		for(int i = 0;i < 9;i++){
			int k = 0;
			for(int j = 0;j < 9;j++){
				k++;
				if(c[k] != '.'){
					int x = c[k] - '1';
					row[i] -= 1 << x;
					col[j] -= 1 << x;
					cell[i/3][j/3] -= 1 << x; 
				}
				else{
					cnt++;
				}
			}
		}
		dfs(cnt);
		cout<<c;
	}
	return 0;
}