题面
数独是一种传统益智游戏，你需要把一个9 × 9的数独补充完整，使得图中每行、每列、每个3 × 3的九宫格内数字1~9均恰好出现一次。
请编写一个程序填写数独。
输入格式
输入包含多组测试用例。
每个测试用例占一行，包含81个字符，代表数独的81个格内数据（顺序总体由上到下，同行由左到右）。
每个字符都是一个数字（1-9）或一个”.”（表示尚未填充）。
您可以假设输入中的每个谜题都只有一个解决方案。
文件结尾处为包含单词“end”的单行，表示输入结束。
输出格式
每个测试用例，输出一行数据，代表填充完全后的数独。
输入样例：
4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end
输出样例：
417369825632158947958724316825437169791586432346912758289643571573291684164875293
416837529982465371735129468571298643293746185864351297647913852359682714128574936
思路
类似8皇后的dfs回溯问题，但是1ms的时间限制，爆搜肯定超时，所以我们要加剪枝。当我们去填一个空格的时候，我们可以选择一个优化剪枝，我每次都选择可选点最少的点先手填，这样我们可以做到尽可能的剪枝，然后我们去找可以填的任意一个状态去填充进行dfs和回溯，最后当我们的cnt减少为0的时候代表我们已经填充完毕，否则我们就填充失败。另外，对于这些繁琐的选择和状态，我们可以利用状态压缩里面的技巧，用二进制数去存储，并且用位运算去修改状态。
代码实现
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn=9;
int ones[1<<maxn],row[maxn],col[maxn],cell[3][3];
int map[1<<maxn];
char str[100];
inline int lowbit (int x) {
return x&(-x); //得到最低位的1，便于改变状态（修改01串）
}
inline int get (int x,int y) {
return row[x]&col[y]&cell[x/3][y/3]; //得到这个位置的可选状态
}
inline void init () {
for (int i=0;i<=8;i++) row[i]=col[i]=(1<<maxn)-1;
for (int i=0;i<3;i++)
for (int j=0;j<3;j++) { //初始的时候所有点都可选，这个01串全为1
cell[i][j]=(1<<maxn)-1;
}
}
bool dfs (int cnt) {
if (cnt==0) return true;
int minv=10;
int mx,my;
for (int i=0;i<maxn;i++) //找到当前可选数最小的点位置
for (int j=0;j<maxn;j++)
if (str[i*9+j]=='.') {
int t=ones[get(i,j)];
if (t<minv) {
minv=t;
mx=i,my=j;
}
}
for (int i=get (mx,my);i;i-=lowbit (i)) {
int t=map[lowbit (i)]; //从这个点开始填入可选数字
row[mx]-=1<<t;
col[my]-=1<<t;
cell [mx/3][my/3]-=1<<t;
str[mx*9+my]='1'+t;
if (dfs (cnt-1)) return true;
row[mx]+=1<<t;
col[my]+=1<<t;
cell[mx/3][my/3]+=1<<t; //回溯
str[mx*9+my]='.';
}
return false;
}
int main () {
for (int i=0;i<=8;i++) map[1<<i]=i;
for (int i=0;i<1<<maxn;i++) {
int cnt=0;
for (int j=i;j;j-=lowbit (j)) cnt++; //记录每个数的1个数，方便后续操作
ones[i]=cnt;
}
while (scanf ("%s",str),str[0]!='e') {
init ();
int cnt=0;
for (int i=0,k=0;i<maxn;i++)
for (int j=0;j<maxn;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;
}