题目描述

数独是一种传统益智游戏，你需要把一个9 × 9的数独补充完整，使得图中每行、每列、每个3 × 3的九宫格内数字1~9均恰好出现一次。

请编写一个程序填写数独。

输入格式
输入包含多组测试用例。

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

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

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

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

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

样例

输入样例：
.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
输出样例：
527389416819426735436751829375692184194538267268174593643217958951843672782965341
416837529982465371735129468571298643293746185864351297647913852359682714128574936

搜索+剪枝(位运算,排除等效冗余,优化搜索顺序)

搜索不用说,相信你一眼就可以看到是搜索算法,问题是这道题目纯搜索明显是要时间爆炸的,所以我们得剪枝.

优化搜索顺序:很明显,我们肯定是从当前能填合法数字最少的位置开始填数字

排除等效冗余:任意一个状态下,我们只需要找一个位置填数即可,而不是找所有的位置和可填的数字.

位运算:很明显这里面check判定很多,我们必须优化这个check,所以我们可以对于,每一行,每一列,每一个九宫格,都利用一个九位二进制数保存,当前还有哪些数字可以填写.

lowbit:我们这道题目当前得需要用lowbit运算取出当前可以能填的数字.

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define fir(i,a,b) for(int i=a;i<=b;i++)
char str[10][10];
int r[9],c[9],g[9],cnt[512],num[512],tot;
inline int gc(int x, int y)//将二维数组变成一维数组
{
    return ((x/3)*3)+(y/3);
}
inline void pd(int x, int y, int z)//位运算,修改当前位数z,第z位1变为0,0变为1.
{
    r[x]^=1<<z;//横坐标
    c[y]^=1<<z;//纵坐标
    g[gc(x,y)]^=1<<z;//九宫格
}
inline int lowbit(int x)//得到当前可以选择的合法数值.
{
    return x&(-x);
}
inline bool dfs(int now)
{
    if (now==0)
        return 1;
    int temp=10,x,y;
    fir(i,0,8)
    fir(j,0,8)
    {
        if (str[i][j]!='.')
            continue;
        int val=r[i] & c[j] & g[gc(i,j)];//判断这一位是否合法,1为合法,0为不合法
        if (!val)
            return 0;
        if (cnt[val]<temp)//找到当前能填合法数字最小的位置
        {
            temp=cnt[val];
            x=i,y=j;
        }
    }
    int val=r[x] & c[y] & g[gc(x, y)];
    for (; val; val-=lowbit(val))
    {
        int z=num[lowbit(val)];
        str[x][y]='1'+z;
        pd(x,y,z);
        if (dfs(now-1))//下一位
            return 1;
        pd(x,y,z);//回溯
        str[x][y]='.';
    }
    return 0;
}
int main()
{
//  freopen("stdin.in","r",stdin);
    for (int i=0; i<1<<9; i++)
        for (int j=i; j; j-=lowbit(j))
            cnt[i]++;
    fir(i,0,8)
    num[1<<i]=i;
    char s[100];
    while (~scanf("%s",s) && s[0]!='e')
    {
        fir(i,0,8)
        fir(j,0,8)
        str[i][j]=s[i*9+j];
        fir(i,0,8)
        r[i]=c[i]=g[i]=(1<<9)-1;//初始的是否都是合法的
        tot=0;
        fir(i,0,8)
        fir(j,0,8)
        if (str[i][j]!='.')
            pd(i,j,str[i][j]-'1');//这一位已经选择
        else
            tot++;//统计需要修改的个数
//      cout<<tot<<endl;
        dfs(tot);
        fir(i,0,8)
        fir(j,0,8)
        s[i*9+j]=str[i][j];//答案输出
        puts(s);
    }
}