Poj2676/3074 Sudoku（dfs+位运算）

描述Sudoku is a very simple task. A square table with 9 rows and 9 columns is divided to 9 smaller squares 3×3 as shown on the Figure. In some of the cells are written decimal digits from 1 to 9. The other cells are empty. The goal is to fill the empty cells with decimal digits from 1 to 9, one digit per cell, in such way that in each row, in each column and in each marked 3×3 subsquare, all the digits from 1 to 9 to appear. Write a program to solve a given Sudoku-task.
输入The input data will start with the number of the test cases. For each test case, 9 lines follow, corresponding to the rows of the table. On each line a string of exactly 9 decimal digits is given, corresponding to the cells in this line. If a cell is empty it is represented by 0.输出For each test case your program should print the solution in the same format as the input data. The empty cells have to be filled according to the rules. If solutions is not unique, then the program may print any one of them.样例输入

1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

样例输出

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

 题意：行、列、块中1~9不重复填充。

题解：

• 朴素方法：dfs每个状态
• 但是这样dfs时间肯定爆炸，所以我们可以用策略来简化它。
• 可以尝试用A*算法，但是现在没时间哈哈哈。
• 我们用这样一个简单策略：
  • 在每个状态下，从所有未填过的位置里选择“能够填入的合法数字”最少的位置，考虑该位置上该填什么数，而不是任意找出一个数。
  • 我们可以用位运算来代替数组执行“对数独各个位置所填入的数字的记录”以及可填性的检查与统计。这就是我要的滑板鞋我们所说的程序“常数优化”。具体来说：
    1. 对于每行每列每块（分块有个小技巧）的九宫格，分别用一个9位二进制数字（全局变量）保存哪些数字还可以填入。
    2. 对于每个位置，把它所在行、列、九宫格的3个二进制数做位与(&)运算，就可以得到该位置能填入哪些数字，用lowbit运算就能够将其取出。
    3. 当一个位置填上某个数以后，把该位置所在的行、列、九宫格记录的二进制数的对应位改为0，即可更新当前状态；回溯时改为1即可还原现场。
• 好吧，就是书上的做法，因为赶时间，所以参考了源代码。

• //#include<bits/stdc++.h>
  #include<algorithm>
  #include <iostream>
  #include  <fstream>
  #include  <cstdlib>
  #include  <cstring>
  #include  <cassert>
  #include   <cstdio>
  #include   <vector>
  #include   <string>
  #include    <cmath>
  #include    <queue>
  #include    <stack>
  #include      <set>
  #include      <map>
  using namespace std;
  #define P(a,b,c) make_pair(a,make_pair(b,c))
  #define rep(i,a,n) for (int i=a;i<=n;i++)
  #define per(i,a,n) for (int i=n;i>=a;i--)
  #define CLR(vis) memset(vis,0,sizeof(vis))
  #define MST(vis,pos) memset(vis,pos,sizeof(vis))
  #define pb push_back
  #define mp make_pair
  #define all(x) (x).begin(),(x).end()
  #define fi first
  #define se second
  #define SZ(x) ((int)(x).size())
  typedef pair<int,pair<int,int> >pii;
  typedef long long ll;
  typedef unsigned long long ull;
  const ll mod = 1000000007;
  const int INF = 0x3f3f3f3f;
  ll gcd(ll a, ll b) {
  	return b ? gcd(b, a%b) : a;
  }
  template <class T>
  inline bool scan_d(T &ret) {
  	char c;
  	int sgn;
  	if(c=getchar(),c==EOF) return 0; //EOF
  	while(c!='?'&&(c<'0'||c>'9')) c=getchar();
  	sgn=(c=='?')?-1:1;
  	ret=(c=='?')?0:(c-'0');
  	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
  	ret*=sgn;
  	return 1;
  }
  inline void outt(int x) {
  	if(x>9) outt(x/10);
  	putchar(x%10+'0');
  }
  const int MAXN = 1e5+10;
  int t,row[10],col[10],squ[10],cnt[512], num[512], tot;
  char s[10];
  int g[10][10];
  int lowbit(int n) {
  	return n&-n;
  }
  inline int G(int x, int y) {//为块编号//可以作为技巧记下 
  	return ((x / 3) * 3) + (y / 3);
  }
  inline void flip(int x, int y, int z) {
  	row[x] ^= 1 << z;
  	col[y] ^= 1 << z;
  	squ[G(x, y)] ^= 1 << z;
  }
  bool dfs(int now) {
  	if (now == 0) return 1;
  	int temp = 10, x, y;
  	for (int i = 0; i < 9; i++)
  		for (int j = 0; j < 9; j++) {
  			if (g[i][j] != 0) continue;
  			int val = row[i] & col[j] & squ[G(i, j)];
  			if (!val) return 0;
  			if (cnt[val] < temp) {
  				temp = cnt[val];
  				x = i, y = j;
  			}
  		}
  	//找到可以填的最少的空 
  	int val = row[x] & col[y] & squ[G(x, y)];//找到能填哪些数字 
  	for (; val; val -= val&-val) {//lowbit运算找到所有为1的位置 
  		int z = num[val&-val];//得到位次 
  		g[x][y] = 1 + z;//原来的值要多加一，之前为了统一位运算而减一 
  		flip(x, y, z);//标记 
  		if (dfs(now - 1)) return 1;//退出的条件 
  		flip(x, y, z);//标记回来 
  		g[x][y] = 0;
  	}
  	return 0;
  }
  void init() {
  	tot=0;
  	rep(i,0,8)row[i] = col[i] = squ[i] = (1 << 9) - 1;
  	for (int i = 0; i < 9; i++)
  			for (int j = 0; j < 9; j++)
  				if (g[i][j] != 0) flip(i, j, g[i][j]-1);
  				else tot++;
  }
  int main() {
  	cin>>t;
  	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++)num[1 << i] = i;
  	while(t--) {
  		rep(i,0,8) {
  			scanf("%s", s);
  			rep(j,0,8)g[i][j]=s[j]-'0';
  		}
  		init();
  		dfs(tot);
  		rep(i,0,8){
  			rep(j,0,8){
  				outt(g[i][j]);
  			}
  			printf("\n");
  		}
  	}
  	return 0;
  }