题目描述

数独是一种传统益智游戏，你需要把一个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

算法 DFS + 剪枝 时间复杂度 O (?)

我的这个代码好像有点极限啊~。~ 好强的测试点~。~ 985ms
剪枝策略：每次选择分支较小的点进行dfs,思路没什么难度，还是代码比较难写~.~

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 9 , M = N * N , K = 1 << N;

int c[N],r[N],cell[3][3];

int ones[K],mp[K];

char str[85];

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

inline int get(int x,int y)
{
    return r[x] & c[y] & cell[x/3][y/3]; 
}

void init(){

    for(int i=0;i<N;i++)
        c[i] = r[i] = cell[i/3][i%3] = (1 << N) - 1;
}

void draw(int x,int y,int v,bool flag){

    if(flag) str[N * x + y] = '1' + v;

    else str[N * x + y] = '.';

    int t = 1 << v;

    if(!flag) t = -t;

    r[x] -= t;
    c[y] -= t;
    cell[x/3][y/3] -= t;

}

bool dfs(int cnt)
{
    if(cnt == 0) return true;

    int x,y,minv = 10;

    for(int i=0;i<M;i++)
        if(str[i] == '.')
        {
            int v = ones[get(i/N,i%N)];
            if(minv > v)
            {
                minv = v;
                x = i/N;
                y = i%N;
            }
        }

    int state = get(x,y);

    while(state)
    {
        int k = lowbit(state);

        int v = mp[k];

        draw(x,y,v,true);

        if(dfs(cnt - 1)) return true;

        draw(x,y,v,false);

        state -= k;
    }

    return false;
}
int main(){

    for(int i=0;i<N;i++) mp[1 << i] = i;

    for(int i=0;i<K;i++)
        for(int j=0;j<N;j++)
            ones[i] += i >> j & 1;

    while(scanf("%s",str),str[0] != 'e')
    {
        init();

        int cnt = 0;

        for(int i=0;i<M;i++)
            if(str[i] != '.')
                draw(i/N,i%N,str[i] - '1',true);
            else
                cnt ++;

        dfs(cnt);

        puts(str);
    }


    return 0;
}