| WXYZ 的个人资料WXYZ的异人馆照片日志列表 |  工具  帮助 |
|
8月23日 数独（Sudoku)——搜索与剪技 数独应该很多人都玩过吧，或至少听说过吧。如果真的不知道请看下面。
（图片来自thebeet的BLOG）
规则就是用1~9的数字把空格填满，使得9行，9列以及9个小的3×3方格内都有1~9这9个数字。
规则虽然简单，但它却吸引着许多人，我曾经也做过很多数独游戏。
现在，不是用人手做了，而是编个程序让电脑来计算。以前做数独也曾经设想过交给电脑去计算，然后就想想一个难的数独大概有60个空格，然后每个空格枚举1~9，然后再检验对不对，然后再想想9^60，可怕，大概就是个五十几位数吧，我相信在我所忍受的时间范围内（当时中学，对编程知识一知半解，算法这些更是什么都不会，也没想很多，就把这时间定在半小时），不可能做完，只好放弃了，并且主观地认为用计算机很难自动完成。
直到上来大学，然后再学习这些知识，才知道，还是绝对有可能的，并且很快完成。
具体到有道在POJ上的解数独题目3074——Sudoku，规则也是同样的简单，多组数据一秒内输出。看到这个后，第一反应是深度优先搜索，即是找到一个空格，然后把数枚举填进去，使得这个格子也满足行、列、小方格内没有重复数字，然后再找到下一空格，重复执行以上动作，如果发现一个格字无法填下任一数字，就返回上一空格重新选择数字，如此执行，直到把整个数独完成。
首先我就按照这思路随便写个1K多的程序从左上角到右下角填格子让它试试，在试Sample时，第二个让我花费了好百多秒才算出来，明显是超时的了，看来得想想办法了。这时我想到的和某些人有点不同，他们想到每填完一步，就寻找那些只有一个数字可填的格子把确定的数字填上，再进行下一步，而我想到的是从一个可能填入的数字个数最小的格子进得下一步搜索（本质还是一样的，因为只有一个数字可填的格子也就是可能填入数字个数最小的格字，如果无数字可填，则肯定是前面填错了，返回上一层即可），然后试试Sample，不到一秒吧，把结果算出来了。我这就把程序提交上去，结果返回一个TLE（超时）。然后我就多次对代码进得优化什么的，再多次提交，结果还是TLE。这时我就向thebeet求助了。thebeet也很热心帮助我，就把它的博客thebeet的BLOG上一篇他自己对这道题的看法的日志给我看。
上面一句话很鼓舞人的：TLE是AC的妈妈。（AC就是通过——WXYZ注）那篇文章中说到：“有人会认为，我们可以先填那些拥有比较小可取值数的格子。实践证明，这个方法并不实用，反而浪费时间在每次找最小可取值的格子。其实道理说起来也很简单，拥有比较大可取值数的格子，它所关联的空白格子也比较多，每次填上这个数字后会使得很多格子的可取值数变小。”对于这点，我有点不同意，找出最小可取值的格子，可以与那些只有一个可取值的格字填完结合起来，在每填入一个格子时，用一个表把每格可取数字保存起来，并不很花时间，每次寻找，也只虽对81格扫描一次，找出空格时，直接从表中得到结果就可以了，并非每次都执得一次函数调用而得到可取值，从第二个Sample中我明显感到这种方法的优势，时间相差几十倍，还是值得用的。
真正对我有极大启发作用的是这句话：“这样我们就需要换一种思路，前面我们都是让格子寻找数字，现在让数字寻找格子。如果有个数字在某一行某一列某个矩阵里面只找到1个位置，那么OK，他就在这里住下了。”就是这句话，这就是一个很大的剪枝，我就朝着这方向写去了，刚好又能用上前面提到的保存每格可取数字的表，就这样了。虽然以前手动做数独时经常用到这个方法，但怎么现在没想到呢？
然后昨天晚上写了一小时，再调试半小时，累了睡醒今天再调试大半小时，终于把这个调试好了（调试过程真的很辛苦，代码7K长，发现有错了还是很难在这7K中找出来，很费精神）。调试好后，试试Sample，0.01秒内算出来，再上网找些数独作为数据，都在瞬间出现正确的结果了。提交上去，234MS的AC，虽然比起thebeet的100多MS还差了些，但还是高兴啊。这些时间差应该就是代码实现的问题了，我代码写得烂，慢就慢点了。
因此，我就上来写写这篇，把思路保存下来，同时也在这里感谢thebeet提供的帮助，同时也表达一下我的兴奋。
总结一下，虽然同样用到深度优先搜索，但具体到某个问题，可以有这个问题独有的剪枝方法，而剪枝在搜索中是至关重要的，因此做题时要具体问题具体分析。（哲学都出来了……） 引用通告此日志的引用通告 URL 是： http://wxyz202.spaces.live.com/blog/cns!D4DC981555112325!487.trak 引用此项的网络日志
|
|
|
%e2%80%94%e2%80%94%e6%90%9c%e7%b4%a2%e4%b8%8e%e5%89%aa%e6%8a%80+%e2%80%94+Windows+Live&referrer=){kind=small}
