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

信息 灵感 创新

I? =Information,Inspiration,Innovation

 
 
 
 

日历

 
 
模块内容加载中...
 
 
 
 
 

天气

 
 
模块内容加载中...
 
 
 
 
 
 
 

湖北省 武汉市 天秤座

 发消息  写留言

 
we are 5. Mathematics, Computation, Programming, Engineering, and Making fun of life.
 
近期心愿make it happen, make it happy, make it harmony
博客等级加载中...
今日访问加载中...
总访问量加载中...
最后登录加载中...
 
 
 
 
 
 
 
 

数独解法之-Empty Rectangle

2016-11-9 18:35:38 阅读39 评论0 92016/11 Nov9

这个策略牵扯到的候选数较多,所以有点复杂,网上的关于该策略的中文版介绍,都是语焉不详,索性硬着头皮把英文版本看了一下,总算是摸着点门道,大概知道了是怎么回事。

什么是Empty Rectangle(ER)?

Empty Rectangle翻译过来就是空矩形的意思,如果一个候选数,被限制在了一个块中,同时还只能在该块中位于一行和一列,则剩下的两行、两列的四个顶点构成了ER。

ER不仅仅是上面这种,还有其他可能的构型,下面的图1是候选数8可能存在的几个分布情况,图中的+号就构成了ER,因为这个矩形的四个顶点上都不包含了该候选数(Empty),因此该策略得名Empty Rectangle。由于构成ER的行、列分别可以从行(r1,r2,r3)和列(c1,c2,c3)中挑选两个,因此总共有9种不同的构型(当然这个不是该策略的重点)。

图1

接下来要介绍的是空矩形交点。现在把重点回到块中的候选数上。刚才说过了,空矩形的模式是,一个候选数被限制在了一个块中,同时还只能在该块中位于一行和一列,因此,这一行和这一列必然会存在一个交点单元格,图2中用橙色标识的单元格就是针对图1形成的空矩形交点,即Empty Rectangle Intersection,简写为ERI,这个ERI对后面的求解很关键。不过值得一提的是,ERI中可能包含,也可能不包含候选数,这都很正常。例如图2中b2、b6和b7中的ERI都包含了候选数,而b4和b5中的ERI则不包含候选数。

图2

在找到了ERI之后,接下来需要找到一行或一

作者  | 2016-11-9 18:35:38 | 阅读(39) |评论(0) | 阅读全文>>

获取程序的引用集

2016-11-1 23:32:11 阅读37 评论0 12016/11 Nov1

关键:使用Assembly.Load()加载组件,然后使用Assembly.GetReferencedAssemblies()获取应用组件。

代码如下:

private List<string> ListReference(string fileName)

{

List<string> result = new List<string>();

Assembly assm = null;

try

{

assm = Assembly.LoadFile(fileName);

foreach (AssemblyName an in assm.GetReferencedAssemblies())

result.Add(an.FullName);

return result;

}

catch (System.Exception ex)

{

throw ex;

}

}

作者  | 2016-11-1 23:32:11 | 阅读(37) |评论(0) | 阅读全文>>

数独求解器开发(3)

2016-11-1 23:31:15 阅读31 评论0 12016/11 Nov1

今天把LockCandidateType1& Type2实现了,测试OK,同时也完成了NakedPair的求解。

能解决的:

不能解决的:

其实就需要求解器编写了这个函数而已,而已。

后面那是NakedTriple和HiddenPair,看看先写哪一个吧。

作者  | 2016-11-1 23:31:15 | 阅读(31) |评论(0) | 阅读全文>>

数独求解器开发(2)

2016-10-26 20:03:40 阅读39 评论0 262016/10 Oct26

这次实现了HiddenSingles和NakedPair的查找,已经能求解部分中等难度的题目了。

图中button1用来载入数独题目,而button2用于求解。只要两次迭代就解决问题了。

但是对于这个题目就不能解决了:

这个需要使用LockedCandidateType,接下来有时间想想如何实现LockedCandidateType1 & LockedCandidateType2。

作者  | 2016-10-26 20:03:40 | 阅读(39) |评论(0) | 阅读全文>>

数独求解器开发(1)

2016-10-24 10:10:11 阅读49 评论0 242016/10 Oct24

一直很喜欢玩数独,然后考虑过编程实现自动求解数独。

原则上,采用暴力法肯定是可以完成数独的求解的,但是这样就太没有意思,另外网上还有一种介绍用舞蹈链求解数独的方式,不过数据结构的执行方式和人类玩数独的思路不大一样,所以最终决定采取一种和人类玩数独策略一致的方法,编程实现,主要是练习如何采用GDI+绘图,以及如何实现具体的求解。

在动手之前,也考虑过,是做一个CUI界面的求解器呢,还是做一个GUI界面的互动游戏,后来综合考虑,先给自己定一个小目标,就做一个GUI界面的求解器,这样能够直观显示求解的结果,目前还不考虑单步分析求解的实现,不过这个在编程的时候有所考虑,所以后面修改起来应该也很容易。

先做了一些个基础的工作,目前基本上完成了界面,实现了自定义的控件Grid,自定义的类Cell,并能完成最简单数独的求解。

这个技巧说白了就是不断地采用行(row)、列(column)块(box)的消除,即Row Column Box Elimination,简称RCBE。测试效果如下:

在没有使用RCBE前,未填写的单元格都是1-9 共9个候选数。

反复调用这个方法后,Tada!数独就解决了。

现在还只能对付简单的数独。对于一些稍微复杂点的还是不能解决,需要更多的求解技巧。

作者  | 2016-10-24 10:10:11 | 阅读(49) |评论(0) | 阅读全文>>

查看所有日志>>

 
 
 
 
 
 
 
模块内容加载中...
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

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

注册 登录  
 加关注