华工象棋论坛

标题: 一个人的精彩顶楼附源代码 [打印本页]

作者: 周运栋 时间: 2012-2-8 23:15
标题: 一个人的精彩顶楼附源代码
三年前,在数独论坛上逛逛,发现国人写的数独解一道题要用1秒钟,还自吹什么"数独博士". 于是自己写了个数独,花了几个月的时间,尝试了好多算法,从1秒提速到几百毫秒,到几十毫秒,到几毫秒,到1毫秒,最终速度提升到200微秒. 那时的我以为这是神速了,去国外的论坛逛了逛.老外的破解速度是20多微秒(2.4G,17sodoku),一个美国壮汉还给我发了照片,我们成为了朋友.他还热情地把源代码给了我,我也把我写的(破解速度不算什么,但是有另一项成就,就是编辑功能,可以说是为数混界做了一个贡献)给了Briturner. 时隔两年,软件水平有了提高,我再次研究了下我的算法,花了2个月提高到35微秒,并把另外一份代码打上了"封存的数独灵魂"的标签.35微秒的到了极限了,而"灵魂"存在严重的缺陷. 是否放弃?我不服气.我3年前就固执地坚持我的"三格一步法"一定厉害.在马上就要搁笔的时刻,我不服气地又研究了一下"灵魂",我发现了什么,我把一个猜测的难题解决了!灵魂之所以封存就是因为猜测不好搞,而我竟然突发奇想地灵光一现,就那么一瞬间,灵魂发光了! 接下去是用了一个星期的时间逐步提速,简单地说就是任何华丽的算法都费时.当铅华褪尽时,我又为它粉饰了下.从灵魂的24微秒,每个提速的小妙着基本都能提升0.4微秒左右. 终于到了我认为的极限了,竟然比我预期的14微秒极限还要快1微秒.13微秒的速度是极限吗? 愿后来人学习我的算法,学习我孜孜不倦追求的精神. 我是孤军奋战,一个人的辛苦与精彩,特记.与朋友们分享. 4.15微秒也许是极限吧

ZSolver.rar (19.52 KB, 下载次数: 20)

作者: 高原红 时间: 2012-2-8 23:30

孤独求败！

作者: 667 时间: 2012-2-9 01:38
当铅华褪尽时

作者: sdj 时间: 2012-2-9 07:27
学习！学习！再学习！探索！探索！再探索！

作者: 古婺 时间: 2012-2-9 08:51
赞一下周先生的求学精神!!!!

这求学三个境界非常人能做到: 第一个境界是" 昨夜西风凋碧树，独上高楼，望尽天涯路"---------这是立志的阶段；第二阶段就是 "衣带渐宽终不悔，为伊消得人憔悴-"------------说的是殚精竭虑，百折不挠；第三阶段， "众人寻他千百度，蓦然回首，那人却在灯火阑珊处"----------说的是上下求索，终有所得。

作者: yjr123 时间: 2012-2-9 16:57
愿后来人学习我的算法,学习我孜孜不倦追求的精神.

算法公开了吗？

作者: zhiqihuang 时间: 2012-2-9 22:54
先赞下令人惊叹的速度。这个是13微秒必然破解还是平均需要13微秒破解？如果是必然破解就实在太神奇了。我凭空设想了一下比较直接的必解算法，普通单核机上至少几十毫秒。周兄如果去研究下GPU编程说不定可以百尺竿头更进一步。一般不需要大量数据交换的程序用GPU可以提高数倍至数十倍的速度。

作者: 周运栋 时间: 2012-2-10 07:29
是否公开算法,我还没决定.但是基本思想会公开. 当然是必破.zhi兄也写程序的吧. 我的测试文件是17个数的数独,数独家们称17数独虽然已知数少,但是难度不大. 如果是破解其他类型的数独的话,时间要多一些.比如难度很大的,要30微秒. 比较直接的必解算法,这个恐怕没什么技术含量,速度当然慢得很了.

作者: zhiqihuang 时间: 2012-2-10 09:50
是否公开算法,我还没决定.但是基本思想会公开. 当然是必破.zhi兄也写程序的吧. 我的测试文件是17个数的数 ...[/quote]

像13微秒这种把普通算法提升几千倍速度的算法，需要的更多是数学功底和钻研精神，编程技巧我觉得倒是次要的。我不是专业写程序的，但从小受数学方面的训练，现在工作中大量的东西要用程序计算，所以碰到问题能快速想个解法。在国外工作其实跟国内差不多，也是人际关系大于工作能力，靠闷头干活永远出不了头，以后混不下去了还不知道去干嘛。最近家里又闹不愉快。看着版上几位在国内虽然生活平淡却也算是享福，心里也是非常羡慕。

作者: yjr123 时间: 2012-2-10 12:57
用EXCEL做的数独游戏，解题速度虽然不能达到微秒级别，但也可能是发挥VBA到极致了。

SuDoku.rar (34.03 KB, 下载次数: 16)

作者: 周运栋 时间: 2012-2-11 05:18
程序上有突破，睡眠上可就惨了。最近老是失眠，很严重。昨天提高到12微了。我发现还有提升的可能。整个算法来其实很简单，只是第一个算法思想光芒四射。它把数独算法的阴暗面都照亮了，前段时间采用的手段是开个小灯。直到昨天，我才发现这个阴暗死角已经被照亮。今天早晨才发现：第一个思想因能完全照亮（保留小灯以更亮）这个死角而光芒万丈。我只是坚持了这第一思想——如山巅之冰，剩下的就是水到渠成了。

作者: yjr123 时间: 2012-2-11 10:14
其中的甘苦只有作者知道，别人是无法体会的。

对于软件使用者来说，1微秒和1秒并没有太大的差别。

作者: 周运栋 时间: 2012-2-11 16:35
哈哈,余先生正解! 所以我的作品系列的"斗智**"是和软件作者斗的.呵呵. 不过这次差点就输了,曾经准备放弃. 自评数独明月般皎洁幽雅(代码), 太阳般光芒万丈(算法), 闪电般迅捷无匹(速度), 沧桑般豪情泪眼(心情), ——记于数独完成日从此别再想有一个算法能快过这个了,除了在此基础上改进.呵呵.

作者: 周运栋 时间: 2012-2-11 16:38
如果这个算法能够公布在大学教科书里,再要学生好好地学,中国的软件水平将会大大提高一个档次. 可是外国的人也会学去,这是我不想要的,呵呵.

作者: 周运栋 时间: 2012-3-10 20:45
目前速度17数独10.12微秒,比老外的速度快了25%. (只局限于这种类型的题目) 然而我总觉得还有个瓶颈需要改进,完成这个我才能跟它说再见. 失眠困扰着我,我也决心封埋,永不开启这份代码. 可我做不到,结. 在看了老外的Locked Candidate的算法后,发现无法应用到自己的程序里,水火不容. 昨天吃安眠药,总算改善了一下睡眠,一醒来,我就发现了一个算法改进.我深深地感到这个改进算法太可怕,太恐怖,,,,对于想超越这个算法的人来说! 所以我起个名字叫作邪恶数独

作者: 周运栋 时间: 2012-3-10 20:51
这个算法其实就几行代码,然而它忽隐忽现地飘荡着Locked Candidate的灵魂,和我的整个大思想的精华结合在一起,放射着无尽的光芒.

作者: 667 时间: 2012-3-10 23:03

作者: sdj 时间: 2012-3-10 23:39
第三阶段， "众人寻他千百度，蓦然回首，那人却在灯火阑珊处"----------说的是上下求索，终有所得。

作者: 周运栋 时间: 2012-3-11 11:24
经过一夜的工作,提速(13.3 - 11.6) / 13.3 = 12%

作者: 周运栋 时间: 2012-3-11 11:38
删除了一段代码后,速度 10.33 us (2.2G CPU),特别是复杂题的提升更大,达到50%

作者: 周运栋 时间: 2012-3-11 11:42
//Complex Self Method
int Shrink = FULL_TO_SHRINK(F[B]);
if ((F[B] &= TblComplexMask[Shrink]) == 0)
return false;

这就是3年来的精华,把计算都压缩进来了.

作者: 周运栋 时间: 2012-3-11 11:48
这个快到原来那些代码都显得慢而要删除了. 果然超快.

作者: 周运栋 时间: 2012-3-11 12:05
当算法的小细节左右逢源的时候,经验告诉我将会有奇迹.
这个算法三渠交会了!

作者: 周运栋 时间: 2012-3-11 12:49
当前速度: 9.9 us . (13.3 - 9.9) / 13.3 = 25.5% 提升

作者: yanyun 时间: 2012-3-11 14:54
胜利属于不懈探索研究的人！！！一定会到达光辉的顶点！！！

作者: 周运栋 时间: 2012-3-11 15:50
http://forum.enjoysudoku.com/zso ... ny-case-t30480.html

作者: 周运栋 时间: 2012-3-11 21:09
在几种测试例上,与当前第一快的进行速度测试, ZSolver 获得全面胜利. 现在的速度是7.5us

告别了,数独.

作者: fullzzone 时间: 2013-1-30 10:08
执迷数独注意保重学习了谢谢

欢迎光临华工象棋论坛 (http://www.hgchess.com/BBS/)