基于wpf的数独游戏的开发毕业设计(编辑修改稿)

基于wpf的数独游戏的开发毕业设计(编辑修改稿)内容摘要：

和 Expression Blend，这些工具将为程序员与设计人员节省更多的编码时间。 总而言之，通过 WPF， .NET Framework 提供了一种比较完整和一致的解决方案，以用于应对用户界面方面的难题。 数独的通解方法 数独解法全是由规则衍生出来的，基本解法分为两类思路，一类为基础摒除法，一类为 唯一法 [9]。 基础摒除法就是利用 1～ 9 的数字在每一行、每一列、每一宫都只能出现一次的规则进行解题的方法。 首先，根据横列、竖列和宫格的限制条件排除各个数格不可能出现的数字，并从 1－ 9 将各个可能的候选数用小字体逐个写进每个空白的格子。 寻找九宫格摒除解：找到了某候选数在某一个九宫格可填入的位置只余一个的情形 ， 亦即找到了该数在该九宫格中的填入位置。 寻找列摒除解：找到了某候选数在某列可填入的位置只余一个的情形 ， 亦即找到了该数在该列中的填入位置。 寻找行摒除解：找到了某候选数在某行可填入的位置只余一个的情形 ， 亦即找到 了该数在该行中的填入位置。 基础摒除法的提升方法是区块摒除法 ， 是直观法中使用频率最高的方法之一。 唯一解法如下：当某行已填数字的宫格达到 8 个 ， 那么该行剩余宫格能填的数字就只剩下那个还没出现过的数字了，成为行的唯一解。 当某列已填数字的宫格达到 8 个 ， 那么该列剩余宫格能填的数字就只剩下那个还没出现过的数字了，成为列的唯一解。 当某九宫格已填数字的宫格达到 8 个 ， 那么该九宫格剩余宫格能填的数字就只剩下那个还没出现过的数字了，成为九宫格的唯一解。 4 3. 可行性分析与需求分析 系统软件开发环境 系统环境： Windows Vista 或 Windows 7 以上版本或者 Windows XP 安装 .NET Framework 硬件环境：支持 DirectX9/10 的显卡支持 开发语言： C和 XAML IDE： Microsoft Visual Studio 20xx、 Expression Blend 系统任务的可行性分析 经济可行性 本游戏使用面向对象编程思想设计，易于编写和维护，总体开发成本低。 由于游戏规则简单，入门度低，人人都可以玩，而且容易入迷。 技术可行性 .NET Framework 提供了丰富的 公共语言运行库和基类库 ，对于本游戏的开发可以简化编码，避免不必要的错误。 同时使用的 WPF 技术提供了一种比较完整和一致的解决方案，以用于应对用户界面设计方面的难题。 AI 算法方面，将建立解题器插件，可以提供多种算法来解决数独谜题。 充分利用当今计算机的优越性能，使用成熟的算法 —— 递归算法，实现起来容易。 系统安全性分析 游戏使用到的解题器是经过 动态加载预编译 模块实现的， 为了帮助保护计算机系统防止受信任的代码有意或无意地危害安全 ，使用了 .NET Framework 提供了一种称为 “代码访问安全性 ”的安全机制。 根据代码请求的权限和安全策略 允许的操作，向加载的每个程序集授予权限 ，这将 最大限度地减少由于代码中的安全脆弱性而造成的损害。 .NET Framework 的 垃圾回收机制，通过 回收器管理应用程序的内存分配和释放 ，从而使内存得到优化。 垃圾回收器优化引擎根据正在进行的分配情况确定执行回收的最佳时间。 当垃圾回收器执行回收时，它检查托管堆中不再被应用程序使用的对象并执行必要的操作来回收它们占用的内存 [10]。 系统功能需求分析 按照用户需求，本系统大致分为三大功能：游戏界面（ UI）功能、数据处理功能和用户功能。 游戏界面（ UI）功能，向用户显 示游戏的信息，包括数独棋盘、计时器、游戏菜单等。 数据处理功能负责内部数据的处理，是该游戏的核心，包括数独迷局生成、数独填充完成的验证、数独的 AI 解题功能等。 下面介绍用户功能， 图表 31 用户功能用例图 为用户功能用例图，是用户直接使用的游戏功能，其功能主要通过鼠标操作完成。 每个用例的简要说明如下： 5 用 户数 独 游 戏新 游 戏读 取 游 戏保 存 游 戏游 戏 设 定电 脑 解 题 图表 31用户功能用例图 A. 新游戏：产生新的数独游戏。 B. 保存游戏： 保存当前游戏状态。 C. 读取游戏：读取保存的游戏状态。 D. 游戏设定：包括设定游戏生成方法、游戏时间难易程度和游戏规格等。 E. 电脑解题：通过电脑解决迷局。 6 4. 系统设计 系统模块划分 根据上一章的需求分析的结果采用模块化程序设计法，将系统分为三大模块：用户功能模块、用户界面 UI 模块和数据处理模块。 用 户 功 能 模 块新 游 戏游 戏 保 存 、 读 取 游 戏 计 时 电 脑 解 题游 戏 设 置数 据 处 理 模 块迷 局 生 成 解 题 填 充 数 字 验 证U I游 戏 菜 单 棋 盘 解 题 器 插 件 其 他 U I计 时 器图表 41 系统模块图 图表 41 系统模块图 ，实线连接的为用户可见模块，用户模块是用户可通过鼠标操作的模块； UI模块为呈现给用户的界面；虚线连接的为不可见模块（数据处理模块），即内部实现模块。 模块内部关系说明 模块内部关系说明模块之间的联系是通过内部数据实现的，下面介绍模块之间的联系。 绘 图A I数 据 绑 定数 据用 户 按 键 事 件触 发修 改内 部 数据 图表 42模块关系图 图表 42 模块关系图 所示模块设计相对独立，各个模块都是通过内部数据进行联系的。 游戏内核包括所有游戏信息，全部为类的成员数据，而它的各个模块则为类的方法（函数）用于 7 相应用户的按键事件。 绘图（ UI）功能，向用户显示游戏的信息，包括数独游戏迷局、计时器、游戏菜单等，这些主要由 XAML 来实现。 当用户按键时触发 UI 的绘图，同时后台的代码处理按键事件，从而使得绑定到前台的内部数据改变。 AI 功能负责内部数据的处理，是该游戏的核心，所有功能的实现几乎都与本模块有关，包括数独迷局游戏生成、数独填充完 成的验证、数独的 AI 解题等。 AI 模块由很多松散的方法组成，各个函数实现单一的功能，便于修改和移植。 数独的数据结构设计 由于数独游戏的特殊性和模块设计的独立性，各个模块间的通信必须依靠全局变量来实现。 在此，设计类用以封装所需要的字段和方法，这样就可以实现游戏的大部分功能。 对于这个类中的函数（方法），类的成员数据相当于全局变量，这样各个函数的通信就不会成为问题。 图表 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 标识棋盘是否填满。 逻辑处理设计 逻辑处理部分主要涉及到的是题目的生成方法，默认的题目生成方式采用随机生成的方法，速度较快，但生成的题目不一定有解。 在玩家选择相应的解题器后，可以通过解题器产生有解的题目。 快速随即生成数 独题目 一种创建数独迷局的方法是通过使用穷举法（ Brute Force），通过这种方法可以快速生成大量不同的题目。 在 20xx 年， 数学家贝米耳与罗思坦算出一共有 6670903752021072936960 种可能的数独谜题[11]。 通过用 19 的随机数填充一个数组，然后检查数组是否满足数独游戏的三个属性：即行、列和宫格不存在冲突的数字，但是并不是所有产生的游戏都有解。 8 好的数独题目要求要有唯一解而且已知数要越少越好。 目前 ，对于 9 9 的数独只要 18 个数字就可以产生出唯一解的数独谜题。 如果不要求 对称，给定的数字是 17 个 就可以产生有解的数独题目，通过使用 17 个已知数，数学家 Gordon Royle 发现了 35396 这样不同的难题 [12]。 到目前为止，少于 17 个已知数的数独题目都不能产生唯一解。 在此，本游戏采用使用至少 18 个已知数来产生数独题目。 本游戏采用的快速生成游戏的实现方法：随机生成一个数填充随机的还没有值的数格，并检测该数所在的行、列和宫格是否已经有此数。 如果没有 此数 则赋值，否则跳出。 接着， 继续前面的步骤，直到填充到指定数目的数格。 使用解题器生成数独题目 严格的说，数独题目要求要有唯一解，通过快速法产生的游戏不 一定有解，为此需要解题器的帮助以生成有唯一解的数独游戏。 实现方法如下：首先在将一个随机数填入空白棋盘里随机的一个数格，然后让解题器填充上剩下的所有数格，接下来就是再挖空一定的数格。 这种方法将花费比较长的时间，主要取决于解题器算法的效率。 数独解题算法的实现 本游戏开发使用了解题器插件，它可以提供多种的解题算法，玩家可以选择相应的解题器用于实现解题和生成题目。 解题器默认使用的是成熟的 算法 —— 递归回溯实现的。 虽然，理论上递归回溯算法需要多次的调用函数自己，需增加额外的系统堆栈，可能消耗大量空间，对执行效率有一 定的影响。 但由于处理的数独游戏数据量较小，同时现在计算机的高性能也减小了递归回溯对时间的影响。 因此，默认采用了代码清晰简洁，可读性很强的递归算法实现解题。 实践证明，成熟的递归回溯法解决数独问题，可以 有 着极快的效果。 在递归之前，可以通过一点小小的预处理，可以使递归算法时间缩短，这个处理可以称为“有限递推” [13]，算法的大致流程图如图表 44 数独递归算法流程图 ： 有 限 递 推 预 处 理候 选 数 列 表变 化结 束开 始从 有 最 少 候 选 数 列表 选 取 一 个 数 猜 想候 选 数 列 表 都 只剩 一 个 候 选 数否否是是 图表 44数独递归算法流程图 算法主要如下： （ 1）建立一个数独棋盘结构的候选数列表里面包含了每个数格的候选数，对于已经有已知数的，列表里就只有一个已知数。 对于待填数格，则将所有可能的候选数填入。 （ 2）然后，“有限递推”预处理算法查询候选数列表每一行、列和宫格查找已知数和候选数有冲突的项，并将其从列表移走。 执行一次就可能确定下一些原来没有确定的数字，那么此时，原始的候选数列表的值必然改变。 再在次执行此过程修订列表，而修订之后若还有数据改变，那么就 在执行此过程了，直到候选数列表的值不再变化。 如此循环下去，就能最大限度地确定下题目本身含义与规则而确定下的内容。 （ 3）接着，解题器查找包含有最少候选数的列表，并随机选取一个数作为正确的数进行猜想。 9 （ 4）在每一次可能的猜测过程中，解题器通过深拷贝并实现递归回到步骤（ 2）。 通过这种方式，若当前情况无解的时候回溯，直到所有的候选数列表有唯一候选数。 （ 5）当所有的猜测都尝试之后如果没有解，则返回 false。 相反，如果棋盘都被填满之后，并且验证通过，则表示数独谜题有解。 图表 45解题器类的 UML图 解题器的类如 图表 45 解题器类的 UML 图 ，该解题器类中包含了解题算法的入口点方法 Solve()，外部可直接调用此公共方法进行解题。 Solve()方法中则调用解题器类私有的递归解题方法RecursiveSolve()，在每次递归解题方法调用自己前，需要使用深度拷贝方法 DeepCopy()将当前对象的所有字段进行执行逐位复制使其支持递归回溯。 在把所有候选数都猜测完后，调用验 证方法 Validate()进行验证。 UI界面设计 游戏的用户交互界面主要在一个窗口中呈现，方便用户操作。 标题 游戏菜单 游戏棋盘 计时器 解题器插件 图表 46游戏界面布局 如 图表 46 游戏界面布局 顶端显示标题，左边是游戏菜单，右边是游戏计时信息，底部是解题器插件，中间是游戏棋盘。 当然，这些面板都应该与分辨率无关，以适应不同用户的显示器。 游戏棋盘设计 位于中间的游戏棋盘是本游戏的重点。 游戏棋盘默认绘制的是 9 9 的标准棋盘，同时还提供了 4 4 和 16 6 规格的棋盘。 棋盘主要通过自定义控件 SudokuBoard 来实现。 SudokuBoard 是通过一系列 10 的嵌套的 ItemsControl 控件来绘制展现棋盘。 这样就可以设置游戏规格，选择不同数目的数格来实现生成。 除了生成指。