谁能写一个高效的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,khttp://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方法，记录已计算矩阵，避免重复计算。