Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
附上剪枝条件和优化措施看过大牛的代码,总结如下: 剪枝: 1.遍历当前所有的空格: 1)如果发现某个空格1-9都放不下,则返回上一层。 2)如果只有1个数可以填,则此空格就只能填上此数,这样就消除一个空格。 3)如果有2个以上的数可以填,则不做处理。 2.遍历当前所有的空格: 1)如果发现在某行中,某个数字不能存在于该行的任一个空格中,则返回上一层。 2)如果发现某个空格所在的行中,某个数字只能填在此空格中,则直接填上,这样就 消除一个空格;有2个以上则不做处理。 3.同2,把2中的行替换为列。 4.同2,把2中的行替换为子数独。 5.选择一个空格时,这个空格须是可填字母最少的一个。 优化: 1.使用位运算,减少恢复现场的开销,unsigned short tbl[i][j]表示第i行的第j个格子的可存放字母的情况。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator