注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

再看noip2009数独  

2010-10-24 21:31:52|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
(本文涉及的代码均可在
http://cid-354ed8646264d3c4.office.live.com/self.aspx/.Public/noip2009.zip
找到)

因为做过poj的某题,我一上来就照搬了那题的代码,结果就是代码很长很长,并且tle了。
为什么呢?因为,这个数独是要把所有的解都找出来,而那个poj上的数独题是要找出唯一一个解,
所以要加入强大的剪枝;而此题加入强剪枝反而耗费了过多的时间。
于是,砍掉一些剪枝,终于过了。
(详见sudoku.cpp)
看着臃肿的代码,我高呼“这不是fhq的风格"。精炼的代码就是生产力,本着这个原则,我开始思考解决方法。

首先,精简搜索的框架:
-每次dfs的时候,
-找出还能填的数字个数最少的一个格子,枚举它的值,继续递归。
可以想象,如果某个格子已经无法填,或者它只有一种填法,那么是可以立即在下一层的递归中被找出,
这样可以避免写出很多繁琐的代码(例如用栈维护可以推理出的格子)。

问题是如何维护每个格子都可以填哪些数字。
双向循环链表?
呵呵,像我这种热爱位运算的人是十分鄙视它的。
于是,通过位压缩,可以用一个short数组M[9][9]存储每个格子能填的数字。
每填一个数字,就更新和它同行、同列、同3*3的格子。
同时,使用某种机制(暴力备份/增量备份)使得回溯的时候能够把M数组恢复原样。
加入一小点优化,这个算法就可以过了。

不过,我并不满足于此。
首先,每次更新M数组和恢复M数组都是十分耗时的。那么能不能通过某种方法来解决它呢?
高级数据结构?冷静会儿吧。
这时,我突然想到了一个办法:
用row[9]代表每行还没有填的数字都有哪些(用位压缩)
col[9]代表每列还没有填的数字有哪些(用位压缩)
grid[9]代表每个3*3还没有填的数字有哪些(用位压缩)
这样,一个格子(x,y)能够填的数字的集合就是row[x]&col[y]&grid[x/3*3+y/3],
而填一个数字进去之后,更新只需要3句话:(向(x,y)填入数字a)
row[x]^=(1<<a)
col[y]^=(1<<a)
grid[x/3*3+y/3]^=(1<<a)
而撤销也只有三句话:
row[x]^=(1<<a)
col[y]^=(1<<a)
grid[x/3*3+y/3]^=(1<<a)
是不是很方便?
通过这个改进,可以AC了。(见sudoku2.cpp)

看了年鉴上的解题报告,它说程序主要的耗时计算集中在寻找能够填的数字最少的那个格子上了。
而改变这个境况的方法就是:在搜索之前用某种启发式的策略将搜索的顺序规定好,
搜索时无论当前分叉数最小的格子是谁,都按照既定的搜索顺序走。
我试了一下,发现快了30%(见sudoku3.cpp)
不过,这个方法是有风险的。因为它的表现严重依赖于搜索顺序确定的策略,并且对于不同的数据这些策略的表现是很飘忽不定的。
(具体的内容请自己测试一下)
  评论这张
 
阅读(1137)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017