Question

17初盘超难数独，我至今碰到的最难数独求电脑编程爱好者挑战，来比比谁的解算所花的时间最少吧！！

题目如下图：该题是合格的17初盘数独题，我碰到最难的，不要问我为什么不是那个芬兰数学家出的11级的数独题，因为呢个是21初盘的、这个是最小初盘17.并且我运算那个仅需3599次。这个花了14284次。所以我认为这个更难。至少是我碰到的最难的。人就不要去算了。

那么我先给大家看看我的程序战况
解算耗时: 寻找第一个解花费：371 毫秒 , 全部检查一边耗时：440毫秒。在AMD240双核WIN764位系统下。

大家都把自己编写的数独运算器拿出来试试吧。来亮出成就，相互交流，综合一下优秀的地方。

最快的程序，悬赏分给他。如果完胜别人的。外加100悬赏分。
个人认为，用舞蹈链算法写出来的数独解算器是目前最快的。但是涉及到检查全部解的时候，可能有点力不从心没有什么不懂的。就是一个数独题。希望各位大神能把自己的结算程序拿出来算算。至于17初盘，的意思是指数独题开始有17个已知的数值至于我程序的运算次数，那个就不用在乎了。是根据我的算法的，不用管他，只需知道运算次数越长说明，数独越难。至于舞蹈链是指DancingLink双十字链表搜索算法。这个不懂就更不用管它了。因为我也不懂。

来来来，围观，我在网上找到个数独运算器，非常的精简，被我加了计时的功能，仅有69行代码。它采用的是回溯算法。所以如此精简，但是速度不是非常理想，22235毫秒。

这个源码写的非常好，较好地运用了递归函数。这个方法我一般都不用，因为用不好。
汗本来想把代码发上来的，长度限制。给地址：
http://zhidao.baidu.com/question/519339961.html?sort=6&;;;old=1&afterAnswer=1#answer-1320303761

我正在完善这个数独运算器，有好的意见或者想法，告诉我把、Q912461339

还差40悬赏分就到200了，届时不能够再提升悬赏分了，不能提高，则就要沉掉了。





Answer 1

楼主弄错了吧，这道题目一点也不难。我用数独中的两大知名软件Sudoku Explainer和HoDoku试过了，都证实这道题目就是最简单的类型而已，根本用不到高级解法。已知数少的数独未必一定是高难度的，不知道楼主对数独的了解有多少。

刚才自己走了一遍这道数独题，用的候选数法，再次证实，此题具有唯一解，但所需解法极为简单。

追问

大哥你一语就中，我不懂啥数独高级解法，我就会简单的解法。我就会让电脑解题，你可以试想一下，让电脑学会高级解法是多么困难的事，所以只能让他学会通用的解法。数独题的难度不容易划分，Sudoku Explainer这款软件分析像芬兰这样的10.7级数独题估计要一小时左右，他划分考虑考虑很多。我的程序却认为简单。我本意是想让电脑程序解，比程序速度，不过我发现去找多解更能比较速度，下楼有个十亿余解的题，花了1天才得解的数目。

追答

额，看来我们是走在两条完全不同的道路上的人啊。。。我不是学程序设计的，只在大学简单的学过一些C语言，更没编写过程序，所以你说的程序问题我也不完全理解。

同时，我玩数独也只是兴趣而已，也用Hodoku测试过芬兰的那道题目，花的时间倒不是太多，但难度系数极大，Sudoku Explainer倒是没试过。不过这两个软件对数独难度的计算方式不同，Hodoku是对每种解法计不同分数，难度分数是整个题目所用解法对应分数之和，而Sudoku Explainer则是将所使用的最高难度的解法的难度系数作为题目整体难度。

楼主在此设置题目是征求程序的，我就不懂程序设计了。不小心打断了一下楼主的问题，不好意思了

Answer 2

我的55毫秒多一点

Answer 3

#include <bits/stdc++.h>
#define R register
using namespace std;
const int maxn=1e5+7;
typedef long long ll;
template <typename T> void inline read(T &x){
    x=0;int f=1;char ch=getchar();if(ch==EOF) return ;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^'0');ch=getchar();}
    x*=f;
}
template <typename T> void inline write(T x){
    if(x<0) x=-x,putchar('-');
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int a[10][10];
bool row[10][10],col[10][10],q[10][10];
int r[10],c[10];
#define get(x,y) ((x-1)/3*3+1+(y-1)/3)
#pragma comment(linker, "/STACK:134217728,134217728")
void inline findnxt(int &_r,int &_c){
	_r=_c=1;int mx=-1;
    for(R int i=1;i<=9;++i){
        if(r[i]>mx&&r[i]<9) _r=i,mx=r[i];
    }
    mx=-1;
    for(R int i=1;i<=9;++i){
        if(c[i]>mx&&(!a[_r][i])) _c=i,mx=c[i];
    }
}
void print(){
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			write(a[i][j]);putchar(' ');
		}
		putchar('\n');
	}
	return ;
}
bool fl=false;
void dfs(int x,int y,int dep){
	if(fl) return ;
    if(dep==81){
        print();
        fl=true;
        return ;
    }
    for(R int i=1;i<=9;++i){
        if(row[x][i]||col[y][i]||q[get(x,y)][i]) continue;
        row[x][i]=col[y][i]=q[get(x,y)][i]=1;
        ++r[x];++c[y];
        a[x][y]=i;
        int _r,_c;
        findnxt(_r,_c);
        dfs(_r,_c,dep+1);
        if(fl) return ;
        row[x][i]=col[y][i]=q[get(x,y)][i]=0;
        --r[x];--c[y];
        a[x][y]=0;
    }
}
int main(){
    int cnt=0;
    for(R int i=1;i<=9;++i){
        for(R int j=1;j<=9;++j){
            read(a[i][j]);
            if(a[i][j]){
                row[i][a[i][j]]=col[j][a[i][j]]=q[get(i,j)][a[i][j]]=1;
                r[i]++;c[j]++;
                cnt++;
            }
        }
    }
    int _r,_c;
    findnxt(_r,_c);
    dfs(_r,_c,cnt);
    return 0;
}

Answer 4

写了个玩，我的被完爆，100秒

追问

终于有人投标了。

你采用的是什么算法。是直接从1开始对所有空位进行假设的穷举法么。

Answer 5

这个源码写的非常好，较好地运用了递归函数。这个方法我一般都不用，因为用不好。
汗本来想把代码发上来的