数独终局计数问题

mathe

我来个计数问题，这个问题我部分解决过， 在我的CSDN博客上有源代码，不过今天CSDN博客在更新不能访问，我也不知道链接是什么。 关于数独，可以查看: http://mathworld.wolfram.com/Sudoku.html 简单来说，就是一个9*9的正方形，里面可以分成9个3*3的小正方形，我们通常称为9个宫格 其终局就是在81个格子分别里面填上1-9各9个，使得，每行，每列，和每个宫格里面都没有重复的数字。 问题是数独终局总共有多少个，上面的wolfram链接里面我们可以找到这个答案是： 6670903752021072936960 这个结果我的程序计算过，在我的双CPU(P4 3.6G)的Linux机器上需要运行2个多小时。 看看大家能否设计出更加快的代码。 另外一个问题是对于每个数独终局，我们通过置换1-9这9个数字（比如1改成2，2改成1），可以得到另外一个数独终局，所以这两个数独终局本质是相同的，同样的，如果我们将任意数独终局旋转90度，或者翻转，或者交换前面3行中任意两行等等超作，都可以得到另外一个数独终局，所以这些局面也是本质相同的。 现在问，本质不同的（也就是无法通过置换数字和简单的旋转，翻转，行列交换操作相互转化的）数独终局有多少个。 上面wolfram链接里面可以找到答案是5472730538 看看大家能否设计一个较好的程序予以计算。

mathe

csdn blog又可以访问了， 我那个计算终局数目的代码在: http://blog.csdn.net/mathe/archive/2006/11/27/1416891.aspx 分成两个可执行程序

northwolves

mathe兄真高手也,佩服之至. 以后不免有大量问题请教,还得辛苦mathe兄. 对于给定的数独题目,什么方法解决最合理? 递归?还是动态规划?

mathe

解数独题，我不知道有什么动态规划的方法，但是只使用递归方法可能速度上有问题，通常会将递归同一些简单的策略相结合（比如发现某行只留下某个格子没有填充了，某个格子对应的行列宫格已经使用了8个数字等），通过这种方法计算机已经可以非常迅速的求解。

mathe

今天在电脑里面找到一个比较早的版本的我的数独的源代码（最新代码已经丢失了）。 由于我已经对于它失去了继续开发的兴趣，现特意发布到这里，有兴趣的朋友可以参考一下。

mathe

根据资源文件，这个版本应该对应1.13版本，对应功能可以参考csdn中连接: http://mathe.download.csdn.net/user/mathe/all/6

无心人

汗 光数独游戏你就赚了多少资源分啊

northwolves

mathe兄的这个程序是我见过的最棒的数独程序

mathe

多谢夸奖。不过程序可改善的地方还有很多。 大家如果有兴趣可以继续改良一下。上面附件提供的版本有点老（新版本丢失了），但是基本功能提供了（当然界面方面的功能比较落后）。此外还有里面的forcing chain的方法还没有实现，而这个算法的实现需要使用图的数据结构。 此外程序里面基本数据结构采用了位运算，但是这种方法不见得最好（我只是试验一下采用这个数据结构，后来发现效率还可以就没有改良了）。我挺想知道如果采用其它数据结构效率会如何。 另外程序里面产生数独局面的代码效率不是很高，最好有人能够继续优化一下（而且这部分使用不同的数据结构应该效率会更好）

mathematica

我觉得这个问题的计数还需要用到群论，不是那么简单的问题！