数独专题

输入

输入包含多组测试用例。

每个测试用例占一行，包含81个字符，代表数独的81个格内数据（顺序总体由上到下，同行由左到右）。

每个字符都是一个数字（1-9）或一个”.”（表示尚未填充）。

您可以假设输入中的每个谜题都只有一个解决方案。

文件结尾处为包含单词“end”的单行，表示输入结束。

输出

每个测试用例，输出一行数据，代表填充完全后的数独。

输入样例 1 

.2738..1..1...6735.......293.5692.8...........6.1745.364.......9518...7..8..6534.
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end

输出样例 1

527389416819426735436751829375692184194538267268174593643217958951843672782965341
416837529982465371735129468571298643293746185864351297647913852359682714128574936

#include<iostream>
#include<algorithm>
using namespace std;

const int N=9;
int ones[1<<N],LOG[1<<N];
int row[N],col[N],block[3][3];
string str;

inline int lowbit(int x)
{
    return x&-x;
}

void init()
{
    for(int i=0;i<N;i++)    row[i]=col[i]=(1<<N)-1;
    
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
        block[i][j]=(1<<N)-1;
}

inline int get(int x,int y)
{
    return row[x]&col[y]&block[x/3][y/3];
}


bool dfs(int cnt)
{
    if(!cnt)    return true;
    int minv=10;
    int x,y;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
        if(str[i*9+j]=='.')
        {
            int t=ones[get(i,j)];
            if(t<minv)
            {
                minv=t;
                x=i;
                y=j;
            }
        }
        for(int i=get(x,y);i;i-=lowbit(i))
        {
            int t=LOG[lowbit(i)];
            row[x]-=1<<t;
            col[y]-=1<<t;
            block[x/3][y/3]-=1<<t;
            str[x*9+y]='1'+t;
            if(dfs(cnt-1))    return true;
            row[x]+=1<<t;
            col[y]+=1<<t;
            block[x/3][y/3]+=1<<t;
            str[x*9+y]='.';
        }
        return false;
}
int main()
{
    for(int i=0;i<N;i++) LOG[1<<i]=i;
    for(int i=0;i<1<<N;i++)
    {
        int s=0;
        for(int j=i;j;j-=lowbit(j))    s++;
        ones[i]=s;
    }
    
    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';
                row[i]-=1<<t;
                col[j]-=1<<t;
                block[i/3][j/3]-=1<<t;
            }
            else    cnt++;
            
            dfs(cnt);
            cout<<str<<endl;
    }
}