是否存在一个能够求解所有的数独谜题的算法(至少能解决有唯一解的题目)。这个算法不得使用穷举或其它试探性方法，也就是说对于有两个以上候选数的格子,不能用候选数逐一试探,而必须直接给出答案。
    我设计了一个算法，编程验证似乎很有效。但有少数的题目解不出来或只能给出部分解（都是只有唯一解的题目），恰好包括“不定期数独【20060227】”中的那个。困惑中...

我也有编数独的程序.不过感觉有时一定得给出穷举或其它试探性方法,因为很难想像一个人找出所有情况并归类,写出相应算法.
比如说本来有一个算法,用一个数独的题去试了,有些格子试不出来,然后通过归纳,把这种情况加入到程序中,做为算法的一个部分(AI)感觉这本身就是有举或其它试探性方法的嫌疑.
我只是感觉不能保证一个算法没有漏洞,所以不得不加一个举或其它试探性方法...以上...

呵呵，专门找的【20060227】就是不能用简单算法算出来的。
数独的设计，本身应该是不需要穷举或试探的，我觉得还是算法不完善。比如：某2个格子都只可能是5或6，那么相应的其他格子应该把5和6的可能排除。这应该是算法的一部分，而显然不属于穷举或试探。手工做多一点，应该可以逐步完善算法。

平时手工作的话也会去做一些试探性搜索阿，算法中也免不了一些搜索吧

    我的方法类似于“反转方格”游戏的解法，就是构造一组线性方程组（矩阵）来描述每个格子可能出现的数及其制约条件。满足这个方程组的解一定是谜题的解。通常这个矩阵可以求出一些确定解，将这些解填好后重新构造新矩阵，如此反复进行，大多数的谜题可以顺利解出（不用进行任何试探）。现在有两个问题：一是为什么很难一次找出全部解，而必须用部分解重新构造矩阵。二是方程组不是总能给出确定解（虽然题目有唯一解）。看来矩阵中需要填加新的独立的行。但似乎找不到独立的方程了。
    比如程序对【20060227】可以算出7个数（还不是一次算出的），然后就再也解不出确定解了（矩阵中每行都有两个以上的变量，没法消除，此时格子中也确实没有能简单确定的数了），不过在剩下的格子中,只要一次正确的试探（试填一个数）即可全部解出。
【20060227】的原题：

zlNzpwWY.gif (8.3 KB)
数独算法

2006-3-5 21:50

程序解出的结果：

xIrkBJP9.gif (8.86 KB)
数独算法

2006-3-5 21:50

我一直认为，数独是不需要试探的（很多资料上也这样说）。
这个题目到这个地方的时，推理顺序是这样的：
1、右下格子的第一列2个空位只能是5或者6；
2、最下一行4个空位中只有第4列的空位可以填1；
3、第3行第5列填1；
4、第1行第7列（你标注的位置）填1。
后面略。
独立方程的话，类似上面推理的第一步应该是可以增加限制条件的。：）

偶也一直想编程,后来觉得在EXCEL里设计模板更为直观,简单得多,所以就弄了.感觉不错.
还有LIKEME说的两个格子有同样数字的问题,其实还可以推广到更多的,如:在九宫格内若同一行/列/小九宫格内出现两个完全相同的两个数字或三个完全相同的三个数字等等以此类推,则可判断该行/列/小九宫格中的其他格不会再出现这两个数字/三个数字/etc..偶也就是这样子填这个游戏的...呼呼..

偶是模板算的,六分多钟.

pA8IXeYf.gif (5.61 KB)
数独算法

2006-3-6 16:48

呼呼,没想到上面的已经算过了.又算了一遍....
有个数独网址,里面好多..
http://sudoku.oubk.com/3x3/mppkpbuondp.sd

写了个程序,给出了推理过程:
WG8daVeE.zip (18.52 KB)

WG8daVeE.zip (18.52 KB)
下载次数: 254

2006-3-7 13:17

[此贴子已经被作者于2006-3-7 13:17:19编辑过]