用PLSQL解数独(SUDOKU)

firmrock

第一次听说这个游戏，支持。。。

sunfly1983

newid的大哥真的太强了，学习！

宁静的自得

thanks

clinglei

留名，想研究算法

addm

five sudoku : 1
5 8 2   4 6 9   7 1 3
9 6 4   1 3 7   2 8 5
7 3 1   8 5 2   4 6 9

1 7 3   5 2 8   6 9 4
4 9 6   3 7 1   8 5 2
2 5 8   6 9 4   1 3 7

8 2 5   9 4 6   3 7 1
6 4 9   7 1 3   5 2 8
3 1 7   2 8 5   9 4 6
------------------
2 5 4   6 1 9   7 8 3
6 7 9   5 8 3   4 1 2
3 1 8   4 2 7   5 6 9

4 2 5   1 9 6   3 7 8
7 9 6   3 4 8   1 2 5
8 3 1   7 5 2   9 4 6

5 4 2   9 6 1   8 3 7
9 6 7   8 3 4   2 5 1
1 8 3   2 7 5   6 9 4
------------------
3 7 1   6 9 8   5 4 2
5 2 8   3 4 1   9 6 7
9 4 6   7 2 5   1 8 3

8 3 7   5 1 9   6 2 4
1 5 2   4 3 6   7 9 8
6 9 4   8 7 2   3 1 5

2 6 3   9 5 4   8 7 1
4 8 5   1 6 7   2 3 9
7 1 9   2 8 3   4 5 6
------------------
7 5 9   1 8 4   2 6 3
1 2 3   7 6 9   4 8 5
6 8 4   5 2 3   7 1 9

9 7 5   4 3 8   1 2 6
4 1 2   9 7 6   5 3 8
3 6 8   2 1 5   9 4 7

5 9 6   3 4 1   8 7 2
8 4 7   6 9 2   3 5 1
2 3 1   8 5 7   6 9 4
------------------
8 7 1   3 6 9   5 2 4
2 3 9   5 4 7   6 1 8
4 5 6   2 8 1   7 9 3

7 4 2   8 1 5   9 3 6
5 6 3   9 2 4   1 8 7
9 1 8   7 3 6   2 4 5

3 8 7   6 9 2   4 5 1
1 2 5   4 7 8   3 6 9
6 9 4   1 5 3   8 7 2
------------------
0.172000 seconds

用回溯法，先得出左上、右上、左下、右下四个大九宫，再将结果与中间大九宫合并，最后解出“五毒俱全”。
程序源码： sudoku_five.zip (33.6 KB, 下载次数: 37)

2008-11-9 02:07 上传

点击文件名下载附件

newkid

addm真棒！我也刚刚完成，代码下周一再整理贴出。先下载你的版本学习！

582469713***254619783
964137285***679583412
731852469***318427569
173528694***425196378
496371852***796348125
258694137***831752946
825946371698542961837
649713528341967834251
317285946725183275694
******837519624******
******152436798******
******694872315******
759184263954871369524
123769485167239547618
684523719283456281793
975438126***742815936
412976538***563924187
368215947***918736245
596341872***387692451
847692351***125478369
231857694***694153872

newkid

我的PL/SQL代码已经更新到一楼主贴附件中。

addm的C++解法我看了，这个解法思路很简单, 因此代码比较好读。他对每个空位循环用1-9测试；测试的办法是和本行、列、区的所有非空值作比较。
我的方法则对此作了些预处理优化：我为每个空位建立了候选值清单，因为已知值是可以从里面划掉的，这样就不必1-9都测试；当检验一个值是否可用，我没有遍历和本行、列、区的所有位置，而是用了如下两种方法：
1.为每个行，列，区各设置9个标志位，某值被用过则置1, 回溯时重设为0. 这样有些额外动作，但只要三个判断就可决定某值是否可用，总体来说是合算的。
2.在我的版本3中放弃了标志位，采用维护候选值清单的办法。对每个空格设置一组指针，指向其后续的其它空格，当本空格取某值时，将它从后续空格的候选清单中删除。回溯时则补回去。用这个办法根本不用测试了，有值就是可用的；虽然它也多了维护清单的开销，额外的好处是在删除时如果发现已经是最后一个了，则可以快速放弃，相当于提早回溯。经过1000个题目测试，这方法比方法1更好。

addm对所有空格按照行，列的顺序处理，我事先排了一下序，当然这个排序没有理论支持，但实际效果不错。
addm先解好上下左右四个方位的所有解，最后穷尽所有解的排列来解中部的标准数独。我的方法则只有一条线，由于各空格的链接事先处理好，在对重叠部分求解的时候相当于一下子就解了两个题。

说了这么多，到底实际效果孰优孰劣？C++的用时0.07秒，PL/SQL用时0.35秒。毕竟PL/SQL是种解释型语言，和C++没得比。
如果addm老兄有空，把自己的C++代码移植到PL/SQL, 我很有兴趣再来PK一下!

zhitler

mark it for study

decode360

潜水N年，不得不上来顶一下。佩服！

aids_ag

.......太弓虽了