Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

附上剪枝条件和优化措施

Posted by damacheng009 at 2010-10-27 21:39:03 on Problem 3076
看过大牛的代码,总结如下:
剪枝:
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator