[开发测试]数独（一道经典的dfs题目）

数独

数独是一种传统益智游戏，你需要把一个 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
思路分析：这里我们用一个二进制数来表示每一行每一列所填数的情况，对于某一行和某一列我们一共需要9位二进制数来表示每个位置是否已经填好了数，如果是某个位置上的二进制位为1，则表示这个位置还没有填好数，同时对于每一个九宫格也是如此，对于初始化时我们就每一个位置都初始化为可以填数，然后对于输入进行处理，我们用draw函数进行处理void draw(int x,int y,int t,bool flag){
if(flag)str[xN+y]=‘1’+t;
else str[xN+y]=’.’;
int v=1<<t;
if(!flag)v=-v;
row[x]-=v;
col[y]-=v;
cell[x/3][y/3]-=v;
}
在这个draw函数中，我们有四个参数，首先是行的位置x，列的位置y，以及当前的数t，以及一个bool类型的变量flag来标记我们能填该数，还是在已经填好该数的位置减去，使得这个位置不填该数，这也是我们在dfs爆搜时的回溯，而在判断某一位上是否是1时，我们可以用二进制中的lowbit运算，能够快速的得到最后一位二进制1，而在dfs时我们怎么样来判断某个位置能填多少个数呢？我们可以用行，列和每一个九宫格对应做与运算即可得到这个状态下可以填的位置数量，对于dfs来说我们可以先搜索节点数目少的分支，所以我们可以先找到这个分支进行搜索

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 9,M=1<<N;
int ones[M],map[M];//用于存储每个状态对应有多少个1，以及对于1<<i映射到i
int row[N],col[N],cell[3][3];//对于每行每列以及每个九宫格能填数的9位二进制状态
char str[100];
void init(){//初始化，将每一个位置均初始化为可以填状态
    for(int i=0;i<N;i++)col[i]=row[i]=(1<<N)-1;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    cell[i][j]=(1<<N)-1;
}
int lowbit(int x)  // 返回末尾的1
{
    return x & -x;//lowbit运算，非常简单的一个运算
}
void draw(int x,int y,int t,bool flag){
    if(flag)str[x*N+y]='1'+t;
else str[x*N+y]='.';
int v=1<<t;
if(!flag)v=-v;
row[x]-=v;
col[y]-=v;
cell[x/3][y/3]-=v;
}
int get(int x,int y){
    return row[x]&col[y]&cell[x/3][y/3];//获得当前状态的函数
}
bool dfs(int cnt){
    if(!cnt)return true;//如果当前剩下需要填的位置为0，则说明已经找到一组合法的方案
    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 state = get(i, j);
                if (ones[state] < minv)
                {
                    minv = ones[state];
                    x = i, y = j;
                }
            }//剪枝优化，找到需要填的位置最少的分支，从这个分支开始搜索
    int state=get(x,y);
    for(int i=state;i;i-=lowbit(i)){
        int t=map[lowbit(i)];
        draw(x,y,t,true);
        if(dfs(cnt-1))return true;
        draw(x,y,t,false);
    }
    return false;
}
int main()
{
    for(int i=0;i<N;i++)map[1<<i]=i;
    for(int i=0;i<1<<N;i++)
    for(int j=0;j<N;j++)
    ones[i]+=i>>j&1;
     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';
                    draw(i, j, t, true);
                }
                else cnt ++ ;

        dfs(cnt);

        puts(str);
    }
    return 0;
}