一直很喜欢玩数独,然后考虑过编程实现自动求解数独。
原则上,采用暴力法肯定是可以完成数独的求解的,但是这样就太没有意思,另外网上还有一种介绍用舞蹈链求解数独的方式,不过数据结构的执行方式和人类玩数独的思路不大一样,所以最终决定采取一种和人类玩数独策略一致的方法,编程实现,主要是练习如何采用GDI+绘图,以及如何实现具体的求解。
在动手之前,也考虑过,是做一个CUI界面的求解器呢,还是做一个GUI界面的互动游戏,后来综合考虑,先给自己定一个小目标,就做一个GUI界面的求解器,这样能够直观显示求解的结果,目前还不考虑单步分析求解的实现,不过这个在编程的时候有所考虑,所以后面修改起来应该也很容易。
先做了一些个基础的工作,目前基本上完成了界面,实现了自定义的控件Grid,自定义的类Cell,并能完成最简单数独的求解。
这个技巧说白了就是不断地采用行(row)、列(column)块(box)的消除,即Row Column Box Elimination,简称RCBE。测试效果如下:
在没有使用RCBE前,未填写的单元格都是1-9 共9个候选数。
反复调用这个方法后,Tada!数独就解决了。
现在还只能对付简单的数独。对于一些稍微复杂点的还是不能解决,需要更多的求解技巧。
评论