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

信息 灵感 创新

I? =Information,Inspiration,Innovation

 
 
 

日志

 
 
关于我

we are 5. Mathematics, Computation, Programming, Engineering, and Making fun of life.

网易考拉推荐

数独解法之-Empty Rectangle  

2016-11-09 18:35:38|  分类: 乱七八糟 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这个策略牵扯到的候选数较多,所以有点复杂,网上的关于该策略的中文版介绍,都是语焉不详,索性硬着头皮把英文版本看了一下,总算是摸着点门道,大概知道了是怎么回事。
什么是Empty Rectangle(ER)?
Empty Rectangle翻译过来就是空矩形的意思,如果一个候选数,被限制在了一个块中,同时还只能在该块中位于一行和一列,则剩下的两行、两列的四个顶点构成了ER。
ER不仅仅是上面这种,还有其他可能的构型,下面的图1是候选数8可能存在的几个分布情况,图中的+号就构成了ER,因为这个矩形的四个顶点上都不包含了该候选数(Empty),因此该策略得名Empty Rectangle。由于构成ER的行、列分别可以从行(r1,r2,r3)和列(c1,c2,c3)中挑选两个,因此总共有9种不同的构型(当然这个不是该策略的重点)。
数独解法之-Empty Rectangle - Lemniscate - 信息 灵感 创新
图1
接下来要介绍的是空矩形交点。现在把重点回到块中的候选数上。刚才说过了,空矩形的模式是,一个候选数被限制在了一个块中,同时还只能在该块中位于一行和一列,因此,这一行和这一列必然会存在一个交点单元格,图2中用橙色标识的单元格就是针对图1形成的空矩形交点,即Empty Rectangle Intersection,简写为ERI,这个ERI对后面的求解很关键。不过值得一提的是,ERI中可能包含,也可能不包含候选数,这都很正常。例如图2中b2、b6和b7中的ERI都包含了候选数,而b4和b5中的ERI则不包含候选数。
数独解法之-Empty Rectangle - Lemniscate - 信息 灵感 创新
图2
在找到了ERI之后,接下来需要找到一行或一列(为便于描述,以下只讨论行),该行恰好有两个单元格(简记为A和B)含有该候选数,然后这两个候选数之一(不妨认为是A)能“看到”ERI(列标相同),则另外一个候选数B所在行,ERI所在列交点处的单元格(记为C)中,可以将该候选数移除(如果有的话)。
下图是一个实例。
 数独解法之-Empty Rectangle - Lemniscate - 信息 灵感 创新
图3
观察b7中候选数8,可以发现黄色区域就是ER,然后红色圈圈处r9c1就是ERI,然后留意r2,恰好有两个单元格r2c1(A)、r2c9(B)中含有候选数8,此时检查r2c9所处的列(c9),ERI所处的行(r9)交点处的单元格r9c9,其中含有候选数8,可以将其排除。
那么问题来了,为什么可以排除?还是以上面的例子说明,把重点放在单元格B上面。
B单元格中所填写的数,最后无外乎两种可能:
1.就是8,那显然r9c9中不能为8,排除。
2.不是8,那么,单元格A中必然为8(该行仅有两个单元格含有候选数8),如果A中为8,则A所在的列都不能为8,即图3中r789c1中都不能为8,b7中含有候选数的单元格只占有一行和一列,这个时候如果该列不能含有此候选数8,则候选数8必然位于另外一行r9中,同样说明r9c9不能为8。
所以不管那种情形,r9c9中的8都要排除,其他构型的ER,原理都是一样的。
另外,有一种很惊奇的构型是,双空矩形(Double Empty Rectangle):
数独解法之-Empty Rectangle - Lemniscate - 信息 灵感 创新
图4
双空矩形就是在找到ER之后,同时有一行和一列都能对应ERI,图4中2 in b1,r6、c5都能消除潜在候选数,选r6时可消除r2c5中的候选数2,而选择c5时可消除r6c3中的候选数2。
  评论这张
 
阅读(38)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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