玩数独, acwing 166题

acwing_166.cpp

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 9, M = 1 << N;

int ones[M], map[M];
// ones存的是， 一个数，的二进制中，有几个1
int row[N], col[N], cell[3][3];
char str[100]; 

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

void init(){
	for (int i=0; i<N; ++i) row[i] = col[i] = (1 << N) -1;	// 左移变成 100000, 再减1， 变成 011111, 完成初始化
	for (int i=0; i<3; ++i){
		for (int j=0; j<3; ++j){
			cell[i][j] = (1 << N) -1;
		}
	}
}

inline int get(int x, int y){
	return row[x] & col[y] & cell[x / 3][y / 3];
}

bool dfs(int cnt){
	if (!cnt) return true;

	int minv = 10;
	int x, y;
	for (int i=0; i<N; ++i){
		for (int j=0; j<N; ++j){
			if (str[i * N + j] == '.'){
				// 选择 可以填的选项最少的那个格子 
				int t = ones[get(i, j)];
				if (t < minv){
					minv = t;
					x = i, y = j;
				}
			}	
		}
	}

	for (int i=get(x,y); i; i -= lowbit(i)){
		int t = map[lowbit(i)];

		// 修改状态
		row[x] -= 1 << t;
		col[y] -= 1 << t;
		cell[x / 3][y / 3] -= 1 << t;
		str[x * N + y] = '1' + t;

		if(dfs(cnt-1)) return true;

		// 恢复状态
		row[x] += 1 << t;
		col[y] += 1 << t;
		cell[x / 3][y / 3] += 1 << t;
		str[x * N + y] = '.';
	}
	
	return false;
}

int main(){
	for (int i=0; i<N; ++i) map[1 << i] = i;
	for (int i=0; i< 1<<N; ++i){
		int s = 0;
		for (int j=i; j; j -= lowbit(j)){
			++s;
		}
		ones[i] = s;		
	}

	while (cin >> str, str[0] != 'e'){
		init();

		int cnt = 0;
		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';
					row[i] -= 1 << t;
					col[j] -= 1 << t;
					cell[i / 3][j / 3] -= 1 << t;
				}
				else{ cnt++;}
			}
		}

		dfs(cnt);

		cout << str << endl;
	}

	return 0;
}