用PLSQL解数独(SUDOKU)

dingjun123 · 发表于 2008-10-22 23:49

grubbyoo 正则高手，期待中，好久没有见到他了！

newkid · 发表于 2008-10-23 02:53

这里是我的另一种尝试，在进入主循环之前对所有空位排序。排序的原则是从最薄弱的环节开始击破，即查找那些行、列、区中空位最少的单元。除此之外和原来的算法一样。

我到老地方下载了“高手进阶”的五万个题目，只对其中1000个进行了测试并和上一种解法作比较。一千个做下来平均0.27秒，最坏的情况是5.6秒；旧方法平均是1.15秒，最坏情况54.38秒。可见新算法有所改进。但其中也有约三分之一是旧算法更快，尽管差距不大。

我在新代码中有意使用了VARRAY, 这下子三种COLLECTION都用上了，显得很花哨，也可当作COLLECTION应用的范例来看。

源代码已上传到主贴的附件中。

[ 本帖最后由 newkid 于 2008-10-23 02:58 编辑 ]

nyfor · 发表于 2008-10-23 09:07

newkid 太牛了...

zhangweicai74 · 发表于 2008-10-23 10:24

强帖.
留名学习

idoTen · 发表于 2008-10-23 10:41

膜拜下, 我sudoku的过关记录都要5分钟以上了

newkid · 发表于 2008-10-28 04:41

现在像我这么执著的人不多了

第三种尝试：放弃前面用的标志位方法，为每个空位设置一个候选值数组。此方法的优势是不需要判断，有值就肯定是未用过的；代价就是每当用了一个值，必须从后续节点的候选值（可用值数组）删除它。另一好处就是当要删除时如果发现此值是唯一的，则可以快速断定该值不可用。实际效果：1000个题目的平均用时从0.27减少为0.17秒。
未实现的思路就是动态选择遍历顺序了，如果不想每次都排序的话就必须在内存中维护一个类似B*TREE的结构，这我可就没办法了。
源代码上传到一楼主贴，测试脚本还是原来的，把调用的SUDOKU2改为SUDOKU3即可。

qingyun · 发表于 2008-11-2 10:30

呵呵，我和楼主很像，写了程序后，还是想着不断的优化效率，这个算法用pl/sql实现的，

所以，如果再进一步提高效率，除了从算法上考虑优化外，是否可以考虑在语言上的效率提高；
因为这里面其实没有怎么用到“数据库”；
所以是否可以在pl/sql嵌入 C 活java 脚本，来实现更高的效率；

还有，如果把这个算法放到 c#,c++,delphi里去实现，是不是比这里的PL/SQL还要速度块；

lastwinner · 发表于 2008-11-6 11:08

两年多前用java写过一个
http://lastwinner.itpub.net/post/7102/59094

仅供楼主参考

程序不完善，只能解出有唯一解的局
但稍加修改，加入尝试环节，就可以解出所有的局

lastwinner · 发表于 2008-11-6 11:11

程序中有注释，应该很好理解

newkid · 发表于 2008-11-7 00:51

java的一下子看不懂，等会再研究，谢谢分享！

用PLSQL解数独(SUDOKU)

浏览过的版块