谁能写一个高效的c++数独代码呢？

mathematica

如果还不知道什么叫做数独，那么请看百度百科吧。
九宫格数独：http://baike.baidu.com/view/451932.html?fromsyno&hold=source
写的代码要求如下：
1、高效
2、简洁
3、必须有注释，如果没有注释，你就不要贴上来了，我最讨厌没有注释的程序
4、尽可能地能求出所有解
5、在开始的时候先判断下是否有解，有的时候给出的数独根本没有解。
请高人露面吧。贴上你的c++之类的代码吧。

风云剑

最高效的是DLX算法，对任何布局可瞬间求解。但网上的程序都没注释，就不贴上来了。

   Dancing Link算法(以下简称DLX)是解NPC难题中的精确覆盖(Exact Cover)的高效算法，一个问题，如果能转化成Exact Cover模型，则都能用DLX解。数独的解法也不列外。
       对于一个N*N的(N=K*K)数独，我们可以用一个3位的N进制数rck(0<=r,c,k<N)来表示第r行第c列放的数是k+1。这样我们就可以用N*N*N个状态来表示所有可能的状态，这同时也是转化成Exact Cover后矩阵的行的个数。
       而对于每一个状态rck，该状态的Exact Cover的模型放置是怎样的呢？我们可以用[0,N*N)区间表示行冲突，[N*N,2*N*N)区间表示小方块冲突，[2*N*N,3*N*N)区间表示列冲突，[3*N*N,4*N*N)区间表示k这个数放置的位置。这里的4*N*N就是转化成Exact Cover后矩阵的列的个数。
       至此，数独的Exact Cover模型已经建立完毕，剩下的就是DLX算法的实现了。

http://blog.163.com/lightyue_ley ... 607720097247414100/

gxqcn

风云剑 在人工智能方面研究比较深，发的帖子比较切中主题。

zeroieme

被机器人弄起来的


说说我对DLX算法的体会
是将求解状态以十字链表形式保留，减少了出入栈的花费，但本质上依然是NP的，而且可能出现重复求解。
选择最短的列来寻找适合的行，在递归前几层会迅速消耗“密切相关”的行与列，造成强烈剪枝的假象；但“关系疏远”的就没有改善。以我处理过的例子，各层循环数大概为 19、15、10、6、2、1（貌似很好）、20、17、11、8、3、1（又来？）、、20、17、11、8、3、1（还来！）……19、15、10、 6、2、1…… 你慢慢玩，偶回家吃饭了。
估计DLX近似O(a^n)。

zeroieme

1、DLX做对称性01矩阵时存在重复分析的情况
如下面矩阵
11000000
10100000
01010000
00110000
00001100
00001010
00000101
00000011
它实质是两个相同子矩阵组成的，按基本DLX方法，会在求左上子矩阵一解后对右下矩阵重复求解。更好的办法是分割子矩阵，然后全问题解就是两部分解的组合。

zeroieme

2、再看一般的精确覆盖01矩阵，任两行、任两列的交换后解是不变的。我们可以将一个0和1均匀分布的矩阵通过行列交换变成
左下、右上都是零的矩阵：

lll++000
lll++000
lll++000
xxx++xxx
000++rrr
000++rrr

“x” 是不能彻底划分到左侧右侧的那些行，“+”是前“x”这类行的公共列。类似DLX算法的剪枝，不过我们首先选择的是“+”这类列。很快整个01矩阵被分成 L和R两个小矩阵，再分治。
如是这般，似乎能通向O(n^v * log n)的复杂性，log n是分治成本，n^v则是每次行列交换的计算成本。v是多少在于行列交换算法成本，我现在能到 3，但交换结果一般。

行列的交换算法有很大的优化潜力。高效的交换结果应当是L和R矩阵尽量大而接近，“+”列列数少而且每列短。这样能充分发挥分割分治的优势。

zeroieme

还有就是，既然矩阵任两行、任两列的交换后解是不变的，能否构建一个HASH方法，记录已计算矩阵，避免重复计算。