基于wpf的数独游戏的开发-毕设论文.doc

毕业设计（论文）

基于WPF的数独游戏的开发

毕业设计（论文）原创性声明和使用授权说明

原创性声明
本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得 及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。
作 者 签 名：　　 　 　　日　 期：　　 　 　　 
指导教师签名：　　 　 　　 日　　期：　　 　 　　

使用授权说明

本人完全了解 大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。
作者签名：　　 　 　　 日　 期：　　 　 　　 
【摘 要】“数独”（Sudoku），顾名思义——每个数字只能出现一次。玩家必须在一个已经填充有几个数字的n×n矩阵中填入数字，使得每一行、列和宫格里的数字不重复。这种游戏全面考验做题者观察能力和推理能力，虽然玩法简单，但数字排列方式却千变万化，所以不少教育者认为数独游戏是训练头脑的绝佳方式。因此，一些科学家和研究人员建议将数独游戏作为日常活动的一部分。
游戏将在.NET Framework 3.5架构上进行开发。主要使用的技术 WPF（Windows Presentation Foundation）的开发技术，是微软新一代图形系统。基于DirectX 9/10技术的WPF不仅带来了前所未有的3D界面，而且其图形向量渲染引擎也大大改进了传统的2D界面。通过WPF，.NET Framework 3.5提供了一种比较完整和一致的解决方案，以用于应对用户界面方面的难题。程序员在WPF的帮助下，将更加有效的工作开发出媲美Mac程序的炫酷界面。本论文着眼于WPF技术的应用，开发一款具有精致美观界面的Windows游戏程序——数独。
本论文介绍了WPF的相关技术及本程序的结构分析和具体功能的实现。
【关键词】数独；WPF；C#；XAML

目录
1. 绪论 1
1.1 选题背景 1
1.2 数独游戏简介 1
2. 开发环境及相关技术的介绍 2
2.1 .NET Framework开发平台 2
2.2 WPF简介 2
2.3 传统Windows游戏开发技术比较 2
2.4 WPF技术的开发优势 3
2.5 数独的通解方法 3
3. 可行性分析与需求分析 4
3.1 系统软件开发环境 4
3.2 系统任务的可行性分析 4
3.2.1 经济可行性 4
3.2.2 技术可行性 4
3.2.3 系统安全性分析 4
3.3 系统功能需求分析 4
4. 系统设计 6
4.1 系统模块划分 6
4.2 模块内部关系说明 6
4.3 数独的数据结构设计 7
4.4 逻辑处理设计 7
4.4.1 快速随即生成数独题目 7
4.4.2 使用解题器生成数独题目 8
4.4.3 数独解题算法的实现 8
4.5 UI界面设计 9
4.5.1 游戏棋盘设计 9
4.5.2 游戏菜单设计 10
4.5.3 计时器设计 10
4.5.4 解题器插件设计 10
4.5.5 其他界面设计 10
4.6 用户功能实现 10
5. 系统实现 11
5.1 数独的数据结构实现 11
5.2 逻辑处理模块实现 12
5.2.1 快速随机生成数独题目实现 12
5.2.2 使用解题器生成数独题目 12
5.2.3 解题器实现 12
5.3 UI界面实现 14
5.3.1 游戏菜单实现 14
5.3.2 数独棋盘实现 15
5.3.3 计时器实现 16
5.3.4 解题器实现 17
5.3.5 其他界面实现 17
5.4 用户功能模块实现 17
5.4.1 新游戏实现 17
5.4.2 保存游戏、读取游戏实现 18
5.4.3 游戏设定 18
5.4.4 计时功能实现 18
5.4.5 解题器插件实现 18
6. 测试打包的过程 19
6.1 打包 19
6.2 发现的BUG及解决情况 20
6.3 未完善的功能 20
7. 结论 21
7.1 游戏的总结和展望 21
7.2 感想 21

22

1. 绪论
1.1 选题背景
数独游戏，由于规则简单，却变化无穷，在推敲之中完全不必用到数学计算，只需运用逻辑推理能力，所以无论老少中青男女，人人都可以玩，而且容易入手、容易入迷。作为数独游戏的爱好者，我认为有必要在Windows上开发一个功能全面的数独游戏。选择以WPF技术开发是因为WPF其实不仅仅是图形引擎而已，它将给Windows应用程序的开发带来一次革命，因为它的架构提供了一种崭新的开发模式。对于普通用户而言，最直观的就是界面越来越漂亮，看起来越来越舒服了；但对于开发人员而言，界面显示和代码将更好的得到分离，这与从前的桌面应用程序开发有很多不同（界面设置和代码是融合在一起的）。目前，WPF已经有很大的推广，很多开发人员主要以技术研究为主，也有少数公司已经开始从事基于WPF的产品研发工作。WPF它代表了Windows编程的未来，是一项Windows开发者需要紧密关注的技术。开发一款WPF版的数独游戏不但可以检验自己大学四年的学习成果，也可以为广大数独爱好者提供一个良好的游戏体验过程，可谓一举两得。

1.2 数独游戏简介
“数独”来自日文发音“Sudoku”，但概念源自“拉丁方块”，是18世纪末瑞士数学家莱昂哈德•欧拉发明游戏。常见的数独游戏规格是9×9，游戏规则很简单：在九个九宫格里，填入1到9的数字，让每个数字所在的每个行、每个列和每个宫格里都不重复的出现一次。谜题中会预先填入几个数字，其它数格则留白，玩家得依谜题中的数字分布状况，逻辑推敲出剩下的空格里是什么数字。
20多年前，美国人重新挖掘它的魅力，接着日本杂志出版商在八○年代末期的一本美国杂志上看到这个游戏，带回日本后，增加它的游戏难度，提出了“独立的数字”的概念，意思就是“这个数字只能出现一次”或者“这个数字必须是惟一的”，并将这个游戏命名为“数独”（Sudoku）。韦恩．古德（Wayne Gould）一九九七年旅游日本时，买了一本数独游戏书，从此就迷上了，进而研究出计算机程序，并供稿给全球十几家报社，立即受到读者的热烈回响Error! Bookmark not defined.。
只需九个九宫格，及1到9不重复的阿拉伯数字，也超越了文字的障碍，因此自从出现后，从东方到西方，风靡亿万人。有些人认为玩数独是缓解工作压力的最佳方式；有些人认为玩数独可以保持头脑灵活，尤其适合老年人；也有些老师认为玩数独需要耐心、专心和推理能力，所以拿数独当题目给学生练习。
2. 开发环境及相关技术的介绍
2.1 .NET Framework开发平台
.NET Framework 是Microsoft为开发应用程序而创建的一个富有革命性的新平台，其具有两个主要组件：公共语言运行库和.NET Framework类库。它的代码库可以在客户语言（如C#）中通过面向对象编程技术（OOP）来使用这些代码[1] 佚名.Vista之后:WPF[J]. 互联网天地，2007,04:45.
[2] Charles Petzold. Applications = Code + Markup[M]. Microsoft Press, 2006,8
[3] Karli Watson,Christian Nagel.C#入门经典（第三版）[M].北京.清华大学出版社,2006,5,1-2.
。
2006年底，微软公司发布.NET Framework 3.0。.NET Framework 3.0默认内置于Vista操作系统中，并担当最主要的应用程序接口。.NET Framework 3.0以2.0版本为基础，同时增加四个重要组件。从高层来看，.NET 3.0基类库由表格 21 .NET 3.0的核心功能所示的技术组成[4] Allen Feldman. WPF in Action with Visual Studio 2008 [M].Manning Publications Co,2009.
4]。
表格 21 .NET 3.0的核心功能
技术
意义
WPF
WPF通过集成几个先前不相关的API（2D和3D呈现、动画、控件等）为构建GUI提供了一个统一的模型
WCF
WCF为多个分布式API提供了一个统一的编程模式
WF
WF提供了一种直接在.NET应用程序集成工作流的方式
WCS
WCS是一个身份标识无系统，用于保存和提供用户的数字标识，并提供了统一的为特定事物选择标识的接口

.NET 3.0中的第一个组件WPF，是构建桌面GUI应用程序的一个全新的方式。与ASP.NET Web程序类似，WPF应用程序可以将功能与UI设计分离，这些功能使用“代码隐藏”的思路来驱动。使用XAML，界面设计人员可以尝试创作与C#类的定义相绑定的专业级的前端界面。最后，WPF应用程序还支持Web服务器承载的浏览器呈现功能[5] Troelsen. C#与.NET 3.0高级程序设计[M].北京.人民邮电出版社.2008,11,788.
。
2.2 WPF简介
WPF的全称是Windows Presentation Foundation，是微软新发布的Vista操作系统的三大核心开发库之一，其主要负责的是图形显示，所以叫Presentation（呈现）。它将彻底改变应用程序的用户体验，支持丰富的、具有炫丽视觉效果的交互式体验，并且可以随处实现:无论是在浏览器内、在移动设备上，还是在桌面操作系统中[6] 佚名. XAML [EB/OL].
。
作为新的图形引擎，WPF是基于DirectX的，当然增加了很多新的功能。它提供非常强大的2D和3D引擎，通过新出来的Windows Vista和Windows 7系统就可以看出，其对Aero图形引擎的支持，更加让人感到神奇。
2.3 传统Windows游戏开发技术比较
微软在1985发行了第一个版本的Windows。从那以后，Windows进步被更新和加强，最戏剧性的是Microsoft Windows NT (1993) 和 Windows 95 (1995)，Windows从16位体系结构升级到32位的体系结构。当 Windows 首先被发行时，仅仅有一种方式可以编写Windows应用程序，那就是使用C语言去编写Windows API[7] 佚名. Visual Studio 2008 [EB/OL].
[8] 佚名. Expression Blend [EB/OL].
。多年以来，许多其他的编程语言被用在Windows编程，包括Visual Basic 和C++。基于C语言，当前提供给编写Windows应用程序的4条途径，下列表格 22使用基于C语言开发的Windows应用程序详细说明。
表格 22使用基于C语言开发的Windows应用程序
引进年份
语言
接口
1985
C
Windows API
1992
C++
MFC
2001
C#
Windows Forms
2006
C#
Windows Presentation Foundation

过去几年采用的主流Windows开发技术是MFC和Windows Forms，下面将其与WPF开发相比较：
A. 界面显示速度。MFC是在本机生成代码，速度很快。可是，消息循环，减缓了界面显示速度。WPF是可以硬件加速的，在DirectX 9的显卡和安装了较新的驱动的情况下，WPF会得到部分或完全的硬件加速。Windows Forms是基于GDI+的，没有硬件加速。所以，长远来说，WPF有更好的性能。
B. 开发效率上，Windows Forms效率最高，MFC最低。MFC开发效率低，作为现在的软件开发项目来说时间跟效率能决定项目的成败，所以应该尽量选择开发效率高的WPF而避免使用MFC。
C. 开发灵活性和美观上，WPF远高于Windows Forms和MFC，MFC要开发出一个华丽的UI极其困难，而WPF不需要使用商业控件就可以很容易就做出Windows 7那样的UI特效。
D. 使用范围上，WPF范围最广，WPF意图利用简化版本WPF/E走进各种装置，包括浏览器和手机。目前Windows Forms虽然可以用在Windows Mobile 5上，但是不能用在浏览器内。而WPF/E可以用在Windows Mobile 6上和各种浏览器内。
WPF大有取代Windows Forms和MFC之势，从未来net的发展看，MFC会变成一种经典，作为一种技术来供开发者学习。随着时代发展，WPF最终实现桌面应用程序和浏览器应用程序的统一。
2.4 WPF技术的开发优势
使用WPF技术进行开发有很多优势，其优势如下：
A. 充分使用现代的硬件——硬件在近十年改变了很多，但是想利用硬件要求专业化的编码，可能需要使用DirectX或OpenGL。通过WPF，程序员可以更好的利用硬件的优势进行编程。
B. 使用现代的软件设计——当Windows 的图形分系统最初被创造时，面向对象的开发、设计模式，还有垃圾收集这类的事情是不存在的或者并不成熟的。
C. 界面显示和代码将更好的得到分离——使得开发人员和设计人员能够更加密切地合作完成同一个项目，而不会延误各自的进度。
D. 简化编码——有许多IDE对WPF的开发提供支持，比如Visual Studio和Expression Blend，这些工具将为程序员与设计人员节省更多的编码时间。
总而言之，通过WPF，.NET Framework 3.0提供了一种比较完整和一致的解决方案，以用于应对用户界面方面的难题。
2.5 数独的通解方法
数独解法全是由规则衍生出来的，基本解法分为两类思路，一类为基础摒除法，一类为唯一法[9]。
基础摒除法就是利用1～9 的数字在每一行、每一列、每一宫都只能出现一次的规则进行解题的方法。首先，根据横列、竖列和宫格的限制条件排除各个数格不可能出现的数字，并从1－9将各个可能的候选数用小字体逐个写进每个空白的格子。寻找九宫格摒除解：找到了某候选数在某一个九宫格可填入的位置只余一个的情形，亦即找到了该数在该九宫格中的填入位置。寻找列摒除解：找到了某候选数在某列可填入的位置只余一个的情形，亦即找到了该数在该列中的填入位置。寻找行摒除解：找到了某候选数在某行可填入的位置只余一个的情形，亦即找到了该数在该行中的填入位置。基础摒除法的提升方法是区块摒除法，是直观法中使用频率最高的方法之一。
唯一解法如下：当某行已填数字的宫格达到8个，那么该行剩余宫格能填的数字就只剩下那个还没出现过的数字了，成为行的唯一解。当某列已填数字的宫格达到8个，那么该列剩余宫格能填的数字就只剩下那个还没出现过的数字了，成为列的唯一解。当某九宫格已填数字的宫格达到8个，那么该九宫格剩余宫格能填的数字就只剩下那个还没出现过的数字了，成为九宫格的唯一解。

3. 可行性分析与需求分析
3.1 系统软件开发环境
系统环境：Windows Vista或Windows 7以上版本或者Windows XP安装.NET Framework 3.5
硬件环境：支持DirectX9/10的显卡支持
开发语言：C#和XAML
IDE：Microsoft Visual Studio 2008、Expression Blend

3.2 系统任务的可行性分析
3.2.1 经济可行性
本游戏使用面向对象编程思想设计，易于编写和维护，总体开发成本低。由于游戏规则简单，入门度低，人人都可以玩，而且容易入迷。
3.2.2 技术可行性
.NET Framework 3.5提供了丰富的公共语言运行库和基类库，对于本游戏的开发可以简化编码，避免不必要的错误。同时使用的WPF技术提供了一种比较完整和一致的解决方案，以用于应对用户界面设计方面的难题。
AI算法方面，将建立解题器插件，可以提供多种算法来解决数独谜题。充分利用当今计算机的优越性能，使用成熟的算法——递归算法，实现起来容易。
3.2.3 系统安全性分析
游戏使用到的解题器是经过动态加载预编译模块实现的，为了帮助保护计算机系统防止受信任的代码有意或无意地危害安全，使用了.NET Framework提供了一种称为“代码访问安全性”的安全机制。根据代码请求的权限和安全策略允许的操作，向加载的每个程序集授予权限，这将最大限度地减少由于代码中的安全脆弱性而造成的损害。
.NET Framework 的垃圾回收机制，通过回收器管理应用程序的内存分配和释放，从而使内存得到优化。垃圾回收器优化引擎根据正在进行的分配情况确定执行回收的最佳时间。当垃圾回收器执行回收时，它检查托管堆中不再被应用程序使用的对象并执行必要的操作来回收它们占用的内存[10] 佚名. MSDN Library[EB/OL]. ms-help://MS.MSDNQTR.v90.chs/dnmsdn2/html/msdnstart.htm.
。

3.3 系统功能需求分析
按照用户需求，本系统大致分为三大功能：游戏界面（UI）功能、数据处理功能和用户功能。
游戏界面（UI）功能，向用户显示游戏的信息，包括数独棋盘、计时器、游戏菜单等。
数据处理功能负责内部数据的处理，是该游戏的核心，包括数独迷局生成、数独填充完成的验证、数独的AI解题功能等。
下面介绍用户功能，图表 31用户功能用例图为用户功能用例图，是用户直接使用的游戏功能，其功能主要通过鼠标操作完成。每个用例的简要说明如下：

图表 31用户功能用例图
A. 新游戏：产生新的数独游戏。
B. 保存游戏：保存当前游戏状态。
C. 读取游戏：读取保存的游戏状态。
D. 游戏设定：包括设定游戏生成方法、游戏时间难易程度和游戏规格等。
E. 电脑解题：通过电脑解决迷局。

4. 系统设计
4.1 系统模块划分
根据上一章的需求分析的结果采用模块化程序设计法，将系统分为三大模块：用户功能模块、用户界面UI模块和数据处理模块。
图表 41系统模块图

图表 41系统模块图，实线连接的为用户可见模块，用户模块是用户可通过鼠标操作的模块；UI模块为呈现给用户的界面；虚线连接的为不可见模块（数据处理模块），即内部实现模块。

4.2 模块内部关系说明
模块内部关系说明模块之间的联系是通过内部数据实现的，下面介绍模块之间的联系。

图表 42模块关系图

图表 42模块关系图所示模块设计相对独立，各个模块都是通过内部数据进行联系的。
游戏内核包括所有游戏信息，全部为类的成员数据，而它的各个模块则为类的方法（函数）用于相应用户的按键事件。
绘图（UI）功能，向用户显示游戏的信息，包括数独游戏迷局、计时器、游戏菜单等，这些主要由XAML来实现。
当用户按键时触发UI的绘图，同时后台的代码处理按键事件，从而使得绑定到前台的内部数据改变。
AI功能负责内部数据的处理，是该游戏的核心，所有功能的实现几乎都与本模块有关，包括数独迷局游戏生成、数独填充完成的验证、数独的AI解题等。AI模块由很多松散的方法组成，各个函数实现单一的功能，便于修改和移植。

4.3 数独的数据结构设计
由于数独游戏的特殊性和模块设计的独立性，各个模块间的通信必须依靠全局变量来实现。在此，设计类用以封装所需要的字段和方法，这样就可以实现游戏的大部分功能。对于这个类中的函数（方法），类的成员数据相当于全局变量，这样各个函数的通信就不会成为问题。

图表 43数独结构图

通过观察一个典型的9×9数独如图表 43数独结构图，数独是由3×3个宫格组成，而每个宫格又可以由3×3个数格组成，在此将其棋盘抽象为最小的数格。棋盘预先放入的已知数应该是只读的，不可以修改，同时应该有用于标志数字是否合法的字段。
主要数据表示方法：
（1）棋盘的最小单位——数格用Cell类定义。定义字段valueValue存放数字，readOnlyValue标识数格是否为只读数据，possibleValuesValue存放可填入的数，isValidValue标识数数格是否成立。
（2）宫格用Box类定义。动态数据集合Rows存放宫格里数格，isValidValue标识值是否成立。
（3）数独棋盘用Board类定义。Board类及其类似Box类，只是字段动态数据集合Rows存放的是数独棋盘里的宫格，isValidValue标识填入的数是否成立，isFullValue标识棋盘是否填满。

4.4 逻辑处理设计
逻辑处理部分主要涉及到的是题目的生成方法，默认的题目生成方式采用随机生成的方法，速度较快，但生成的题目不一定有解。在玩家选择相应的解题器后，可以通过解题器产生有解的题目。
4.4.1 快速随即生成数独题目
一种创建数独迷局的方法是通过使用穷举法（Brute Force），通过这种方法可以快速生成大量不同的题目。在2005年，数学家贝米耳与罗思坦算出一共有6670903752021072936960种可能的数独谜题[11] Bertram Felgenhauer & Frazer Jarvis. There are 6670903752021072936960 Sudoku grids[EB/OL]. http://www.afjarvis.staff.shef.ac.uk/sudoku/.
。通过用1-9的随机数填充一个数组，然后检查数组是否满足数独游戏的三个属性：即行、列和宫格不存在冲突的数字，但是并不是所有产生的游戏都有解。
好的数独题目要求要有唯一解而且已知数要越少越好。目前，对于9×9的数独只要18个数字就可以产生出唯一解的数独谜题。如果不要求对称，给定的数字是17个就可以产生有解的数独题目，通过使用17个已知数，数学家Gordon Royle发现了35396这样不同的难题[12] Gordon Royle. Minimum Sudoku[EB/OL].http://www.csse.uwa.edu.au/~gordon/sudokumin.php.
。到目前为止，少于17个已知数的数独题目都不能产生唯一解。在此，本游戏采用使用至少18个已知数来产生数独题目。
本游戏采用的快速生成游戏的实现方法：随机生成一个数填充随机的还没有值的数格，并检测该数所在的行、列和宫格是否已经有此数。如果没有此数则赋值，否则跳出。接着，继续前面的步骤，直到填充到指定数目的数格。
4.4.2 使用解题器生成数独题目
严格的说，数独题目要求要有唯一解，通过快速法产生的游戏不一定有解，为此需要解题器的帮助以生成有唯一解的数独游戏。实现方法如下：首先在将一个随机数填入空白棋盘里随机的一个数格，然后让解题器填充上剩下的所有数格，接下来就是再挖空一定的数格。这种方法将花费比较长的时间，主要取决于解题器算法的效率。
4.4.3 数独解题算法的实现
本游戏开发使用了解题器插件，它可以提供多种的解题算法，玩家可以选择相应的解题器用于实现解题和生成题目。
解题器默认使用的是成熟的算法——递归回溯实现的。虽然，理论上递归回溯算法需要多次的调用函数自己，需增加额外的系统堆栈，可能消耗大量空间，对执行效率有一定的影响。但由于处理的数独游戏数据量较小，同时现在计算机的高性能也减小了递归回溯对时间的影响。因此，默认采用了代码清晰简洁，可读性很强的递归算法实现解题。
实践证明，成熟的递归回溯法解决数独问题，可以有着极快的效果。在递归之前，可以通过一点小小的预处理，可以使递归算法时间缩短，这个处理可以称为“有限递推”[13] 雷蕾,沈富可. 关于数独问题的算法的设计与实现[J].电脑知识与技术：481-482.
[14] Victor Gaudioso. Foundation Expression Blend 2 Building Applications in WPF and Silverlight[M].USA.Apress and friends of ED,2008.
[15] Lucas Magder.Coding4Fun[EB/OL]

Development of the Sudoku Game Based on WPF

Mathematics and Computer Science Department
　Major: Computer Science and Technology
118532006068　 Cai Chunsheng Instructor：Lin Wei-wei

【Abstract】Sudoku , the name suggests - each number can only appear once. Players must fill an n×n matrix, which contains some given entries, so that each row, columns, and the boxes contains each interger 1 through n exactly once. This game is fully challenge player’s observation and logic ability. Although games are played simple, the figure is ever-changing arrangement. Therefore, many educators think that Sudoku is a great way to train the brain. Therefore, some scientists and researchers have suggested that the number of independent games as a part of daily activities.
The game will be developed under .NET Framework 3.5. The main technology is WPF (Windows Presentation Foundation), which is Microsoft's next-generation graphics systems. Based on DirectX 9 / 10 technology, WPF has not only brought unprecedented 3D interface, and its vector graphics rendering engine is also greatly improved the traditional 2D interface. Through the WPF, .NET Framework 3.5 provides a more complete and consistent solution for problems of user interface. With WPF, programmers will be more effective work to develop comparable Mac program’s cool interface. This paper focuses on WPF technology, to develop a beautiful Windows games -Sudoku.
This paper describes the WPF technology and structural analysis of this program and the realization of specific functions.
【Key words】Sudoku; WPF; C #; XAML
，算法的大致流程图如图表 44数独递归算法流程图：

图表 44数独递归算法流程图

算法主要如下：
（1）建立一个数独棋盘结构的候选数列表里面包含了每个数格的候选数，对于已经有已知数的，列表里就只有一个已知数。对于待填数格，则将所有可能的候选数填入。
（2）然后，“有限递推”预处理算法查询候选数列表每一行、列和宫格查找已知数和候选数有冲突的项，并将其从列表移走。执行一次就可能确定下一些原来没有确定的数字，那么此时，原始的候选数列表的值必然改变。再在次执行此过程修订列表，而修订之后若还有数据改变，那么就在执行此过程了，直到候选数列表的值不再变化。如此循环下去，就能最大限度地确定下题目本身含义与规则而确定下的内容。
（3）接着，解题器查找包含有最少候选数的列表，并随机选取一个数作为正确的数进行猜想。
（4）在每一次可能的猜测过程中，解题器通过深拷贝并实现递归回到步骤（2）。通过这种方式，若当前情况无解的时候回溯，直到所有的候选数列表有唯一候选数。
（5）当所有的猜测都尝试之后如果没有解，则返回false。相反，如果棋盘都被填满之后，并且验证通过，则表示数独谜题有解。

图表 45解题器类的UML图

解题器的类如图表 45解题器类的UML图，该解题器类中包含了解题算法的入口点方法Solve()，外部可直接调用此公共方法进行解题。Solve()方法中则调用解题器类私有的递归解题方法RecursiveSolve()，在每次递归解题方法调用自己前，需要使用深度拷贝方法DeepCopy()将当前对象的所有字段进行执行逐位复制使其支持递归回溯。在把所有候选数都猜测完后，调用验证方法Validate()进行验证。

4.5 UI界面设计
游戏的用户交互界面主要在一个窗口中呈现，方便用户操作。
标题

游戏菜单

游戏棋盘

计时器
解题器插件
图表 46游戏界面布局

如图表 46游戏界面布局顶端显示标题，左边是游戏菜单，右边是游戏计时信息，底部是解题器插件，中间是游戏棋盘。当然，这些面板都应该与分辨率无关，以适应不同用户的显示器。
4.5.1 游戏棋盘设计
位于中间的游戏棋盘是本游戏的重点。游戏棋盘默认绘制的是9×9的标准棋盘，同时还提供了4×4和16×6规格的棋盘。棋盘主要通过自定义控件SudokuBoard来实现。SudokuBoard是通过一系列的嵌套的ItemsControl控件来绘制展现棋盘。这样就可以设置游戏规格，选择不同数目的数格来实现生成。
除了生成指定大小的棋盘，它至少应该具备以功能：
（1）迷局生成时候，棋盘的已知数是只读的，亦不可以填入数字的；
（2）在空白的数格上应该可以填入数字。
（3）验证填入数字合法性，可以根据当前所填数字的合法性将文字设为不同的颜色，如果填入的数字有冲突，则将有冲突的数字颜色设为红色。
4.5.2 游戏菜单设计
游戏菜单放在主窗口的左边，其中包括了游戏主菜单和游戏室设置，它们都被放置在Expander控件内，类似于Windows操作系统中窗口左边的任务栏，可以展开和收缩。
游戏主菜单中包含了新游戏按钮、读取游戏按钮、保存游戏按钮和退出按钮。
游戏设置菜单中则包含了游戏随机生成方法，通过单选按钮玩家可以选择游戏的生成方式，一种是快速生成游戏，一种是使用解题器的，后者可以保证生成的数独谜语有答案，不过生成速度慢。下面是时间难度设置，玩家可以通过单选按钮选择不计时的方式或简单、中等和困难的时间难度。再来是，游戏规格菜单通过下拉框实现，默认选项是9×9的标准游戏规格。同时还有4×4的入门级规格和挑战型的16×16规格。
4.5.3 计时器设计
右边面板放置的计时器，以一个时钟的方式实现。在玩家选择有时间难度的游戏后，计时器将在新游戏开始时候自动倒计时。游戏过程中，当被再次点击之后颜色变暗可以暂停时间，当再次点击时可以恢复倒计时。同时这里也提供了数字的电子码表，计算精度可达60分之1秒。
4.5.4 解题器插件设计
解题器位于主窗口的底部，它也是被放置于Expander控件内，默认情况下是收缩的。在其里面，左部是一个ListBox列出了所有的解题器，用户可以选择相应的解题器用于生成题目和解题。当选择了相应的解题器后，将在右边出现解题器的相关信息。ListBox下有一个AI对战按钮，按下之后，将在独立线程解题，解题完成后会将结果以槽的形式显示在其右边。由于是采用独立线程解题，所以在解题期间，玩家还可以继续做题。
4.5.5 其他界面设计
由于生成题目可能需要较长时间，因此设计了一个友好的对话框，当选择新游戏时候，将在生成游戏期间，弹出一个对话框提示玩家。
在游戏填充完成并且正确的情况下，将会弹出对话框，以告诉玩家填充正确。同时在指定时间内，如果玩家没有把题目解完，也将弹出时间结束的对话框以告诉玩家。
为了不使游戏界面单调，采用动画的效果让游戏的背景脉动起来，拥有类似水波荡漾的效果。
4.6 用户功能实现
用户功能模块是用户可以直接使用的模块，主要通过鼠标进行点击按钮，调用相应的事件来处理，这些功能的实现相对简单。复杂一些的如读取游戏、保存游戏功能，需要使用系统的文件服务来实现。这些实现都需要使用具体的代码来描述，将在第五章详细描述。

5. 系统实现
系统的实现主要是通过使用集成开发工具Visual Studio 2008进行编码，结合Expression Blend进行用户界面的设计。编码工作主要包括了一些游戏的数据结构的编写、游戏的解题器算法的编写，还有用户功能的编写。通过XAML语言实现了游戏的UI界面。最后通过数据绑定和依赖属性把后台数据呈现在UI界面上。

5.1 数独的数据结构实现
数独棋盘的数据都存放Cell类中，而Box类的成员GridRows是一个动态集合里面放的是Cell，Board类的成员GridRows则放置Box。
Cell类的实现，为了能让其数据成员实现与UI的数据绑定，在此声明属性以提供公共数据成员便利。通过使用 set访问器为数据成员赋值，使用get访问器检索数据成员的值。通过让Cell类实现INotifyPropertyChanged接口，在更改属性值时引发PropertyChanged事件，这样只要数据有改变，即可告知监视者，通过实现INotifyPropertyChanged接口从而实现了观察者模式。下面是以属性Value为例：
public int? Value{
get { return valueValue; }
set {
if (valueValue != value){
valueValue = value;
if (PropertyChanged != n