Sudoku(9*9)
两个优化：
- 按照人类直觉，可以填的数越少的位置越先填
- 使用二进制数字记录一行、列、宫中哪些数字用过，不使用数组，常数优化
#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]) ;
}
}