Sudoku(9*9)

link1：数据强度弱
link2：数据强度强

两个优化：

1. 按照人类直觉，可以填的数越少的位置越先填
2. 使用二进制数字记录一行、列、宫中哪些数字用过，不使用数组，常数优化

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std ;

typedef long long ll ;
const int N = 1000010 ;
const int M = (1 << 11) ;

bool flag ;
int n, T, tot ;
char s[20][20] ;
int row[20], col[20], blk[20] ; // block -> int
int belong[20][20] ;
int cnt[M], dig[M] ;

void pre() {
	for (int i = 0; i <= 2; i++)
	for (int j = 0; j <= 2; j++) {
		belong[i][j] = 0 ;
		belong[i][j + 3] = 1 ;
		belong[i][j + 6] = 2 ;
		belong[i + 3][j] = 3 ;
		belong[i + 3][j + 3] = 4 ;
		belong[i + 3][j + 6] = 5 ;
		belong[i + 6][j] = 6 ;
		belong[i + 6][j + 3] = 7 ;
		belong[i + 6][j + 6] = 8 ;
	}
	for (int i = 0; i <= (1 << 9); i++) 
	for (int j = i; j; j -= j & -j) cnt[i]++ ;
	for (int i = 0; i <= 9; i++) dig[1 << i] = i ;
	
}

void init() {
	tot = 0 ;
	for (int i = 0; i < n; i++) row[i] = col[i] = blk[i] = (1 << 9) - 1 ;
}

void flip(int x, int y, int z) {
	row[x] ^= (1 << z) ;
	col[y] ^= (1 << z) ;
	blk[belong[x][y]] ^= (1 << z) ;
}

int dfs(int step) {
	if (step == 0) {
		flag = true ;
		return 1 ;
	}
	int ans = (1 << 9) - 1, dx, dy ;
	for (int i = 0; i < 9; i++)
	for (int j = 0; j < 9; j++)
	if (s[i][j] == '0') {
		int t = row[i] & col[j] & blk[belong[i][j]] ;
		if (cnt[t] < cnt[ans]) {
			ans = t ;
			dx = i, dy = j ; 
		}
	}
	while (ans) {
		int t = ans & -ans ; ans -= ans & -ans ; t = dig[t] ;
		s[dx][dy] = t + '1' ;
		flip(dx, dy, t) ;
		if (dfs(step - 1)) return 1 ;
		s[dx][dy] = '0' ;
		flip(dx, dy, t) ;
	}
	return 0 ; 
}

int main() {
	n = 9 ;
	scanf("%d", &T) ;
	pre() ;
	while (T--) {
		init() ;
		for (int i = 0; i < n; i++) scanf("%s", s[i]) ;
		for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		if (s[i][j] == '0') tot++ ;
		else flip(i, j, s[i][j] - '1') ;
		dfs(tot) ;
		for (int i = 0; i < n; i++) printf("%s\n" , s[i]) ;
	} 
}