AcWing 166. 数独 题解（搜索—DFS的剪枝）

AcWing 166. 数独
DFS剪枝，这里的剪枝操作是考虑优先考虑的需要填的数最少的格子，这样就能快速将所有格子填满，因为答案唯一，所以可行

#include

using namespace std;

const int N = 9;

int col[N], row[N], cell[3][3];
char str[100];
int mp[1 << N];  //记录第i位是1的二进制数对应的数字i
int ones[1 << N];  //记录二进制数里有几个1

int get(int x, int y){  //取交集，得到这个格子可以有那些情况，返回的是个二进制数 
	return col[y] & row[x] & cell[x / 3][y / 3];
} 

int lowbit(int x){
	return x & (-x);
}

void draw(int x, int y, char t, bool flag){  //更新格子信息 
	if(flag) str[x * N + y] = t + '1';
	else str[x * N + y] = '.';  //恢复现场 
	
	int v = 1 << t;
	if(!flag) v = -v;
	
	row[x] -= v;
	col[y] -= v;
	cell[x / 3][y / 3] -= v;
}

void init(){  //将所有行列九宫格的备选方案都初始化为9个1，表示目前所有数都可以选 
	for(int i = 0; i < N; i ++ ) col[i] = row[i] = (1 << N) - 1;  //初始化行列 
	for(int i = 0; i < 3; i ++ ){  //初始化九宫格 
		for(int j = 0; j < 3; j ++ ){
			cell[i][j] = (1 << N) - 1;
		}
	}
}

bool dfs(int cnt){
	
	if(!cnt) return true;  //如果可以填数的格子数为0，就直接返回 
	
	int x, y;
	int minv = 10;
	
	for(int i = 0; i < N; i ++ ){
		for(int j = 0; j < N; j ++ ){
			if(str[i * N + j] == '.'){  //找到可以填数的格子
				int state = get(i, j);  //找到存储这个坐标可以填的方案 
				if(ones[state] < minv){  //找到最小的可以填的情况数，这一步是剪枝
					minv = ones[state];  //ones[state]就是方案对应的可以填的数的数量 
					x = i, y = j;
				}
			}
		}
	}
	
	int state = get(x, y);
    for (int i = state; i; i -= lowbit(i))
    {
        int t = mp[lowbit(i)];  //应该填几 
        draw(x, y, t, true);
        if (dfs(cnt - 1)) return true;  //遍历下一层 
        draw(x, y, t, false);  //恢复现场 
    }
	return false;
}

int main()
{
	for(int i = 0; i < N; i ++ ) mp[1 << i] = i;  //map记录的是二进制数最后一个1对应的数(比如1000对应的4，100000对应的是6)
	for(int i = 0; i < 1 << N; i ++ ){
		for(int j = 0; j < N; j ++ ){
			ones[i] += i >> j & 1;  //ones[i]记录的是二进制数i有几个1
		}
	}
	
	while(cin>>str, str[0] != 'e'){  //读入一行字符串，就是一组样例 
		init();
		
		int cnt = 0;  //cnt记录的是可以填数的格子数 
		//i代表行，j代表列，k代表每个格子 
		for(int i = 0, k = 0; i < N; i ++ ){
			for(int j = 0; j < N; j ++ , k ++ ){
				if(str[k] != '.'){  //找到已经有数的格子
					int t = str[k] - '1';
					draw(i, j, t, true);
				}
				else cnt ++ ;
			}
		}
		dfs(cnt);
		
		puts(str);
	}
	return 0;
}