计算机专业VC++课程设计之数独游戏设计蛋碎版.doc

Visual C+课程设计题目名称：数独游戏设计班级：信安1101姓名：曹闯学号：1111290101指导教师：阎光伟完成时间：2013.1.181 题目描述利用Visual C+实现数独游戏的功能。该程序能够设置不同难度等级的游戏，实现数独游戏的多样化，采取有效的算法，保证答案的唯一解。2 功能分析系统主要功能包括：（1） 游戏的生成数独游戏的初始化，根据难度在格子里填上数量不同的数字，每种难度下的 数字数量相同。（2） 游戏难度的选择难度设置，从简单到困难，难度越大，生成游戏时数字数量越少。（3） 游戏的提示可选中任何没有填入数字的地方选择提示。提示会给出正确的解，一局游戏只能提示三次。（4） 游戏答案的显示可以直接显示答案，在游戏暂停时禁止使用该功能。（5） 游戏的暂停功能在计时器面板上有暂停按钮，按下暂停按钮后，游戏将进入不计时状态，同时界面将设置为不可操作。（6） 游戏的帮助功能通过帮助文档的使用来进行帮助说明。3 界面分析程序界面由棋盘和按钮组成，在棋盘内，通过单击鼠标选中方格时显示为问号，选中数字时显为蓝色数字。通过键盘在选中方格填入数字，若填入的数字符合游戏规则，显示为橙色，反之，显示为红色。按钮处于选中状态时会变成亮色或者周围加上边框。游戏光标在不同的游戏区域采用了不同的游戏光标。4 系统设计4.1 程序整体结构4.1.1 程序中的主要游戏类主对话框类按钮类游戏算法类对话框类主界面按钮类难度选择按钮类在本程序中，主要分为三大基本类：1、对话框类，2、游戏算法类，3、按钮类。对话框类包括游戏主对话框和选择难度对话框，自定义按钮类包括游戏主对话框的按钮类和难度选择对话框的按钮类。 图1游戏主要框架4.2 主要模块设计4.2.1 游戏基本类设计（1） 游戏主话框类的实现过程通过的按钮的响应函数来实现整个游戏的逻辑控制，当“新游戏”按钮被单击后，游戏界面将进行初始化，后续的操作才能继续进行，通过键盘响应函数来实现对输入数字的控制，通过鼠标移动函数OnMouseMove()来判断区域和加载不同的光标。通过单击鼠标函数OnLButtonDown()来判断单击的区域，实现整个节目的逻辑操作。通过计时函数来实现计时器的功能。（2） 按钮类CNewButton和CMyButton类的实现过程CNewButton类是难度选择对话框的按钮类，CMyButton是主对话框的按钮类。两个类的实现方式相同，都是通过继承CButton类实现按钮的重绘功能，在按钮类里面通过OnMouseHover()函数判断鼠标是否停留在按钮上，通过OnMouseLeave()判断鼠标是否离开按钮。当鼠标停在按钮上或者移开按钮，通过不同的返回值来调用DoGradientFill()函数，自定义的实现了绘制按钮边框的功能。然后再通过按钮重绘函数DrawItem()来实现整个按钮的重绘。（3） 难度对话框的实现定义CLevel类，通过四个单选按钮和两个控制按钮来构成难度选择对话框，通过重载CButton类来实现按钮的重绘。通过主对话框的难度按钮选择，调用CLevel类，实现难度选择对话框的调用。（4） 算法流程图计算函数calculate( )若格子填满退出计算预处理函数predo( )若格子没有填满将没有填满的格子入栈若为求解数独或已跳过了格子深度遍历若为生成数独时调用该计算函数退出起算所有格子填满，栈顶为0跳过该格子，该格子继续在栈里图2 算法流程图（5） 游戏算法的实现过程游戏算法类CSolvesoduku是数独游戏的核心算法，也是整个程序得以运行的中心。CSolvesoduku算法类predo()预处理Exist()判断一个数是否存在calculate()求数独的解isfull()判断是否数独完成setpub()初始化数据fixall()填入唯一解的数字candelete()是否可以挖去该数字图3游戏算法主要函数4.2.2 数据结构和函数的介绍（1） 数据结构最主要的数据结构是4 个整型数组, 其中3 个被设计成一维数组, 还有1 个二维数组。1) int sd82 该数组的用途是接收题目以及保存最终结果。所有的99 个数字被依次存储在该数组中, 空白处则初始化为0。之所以把数组范围设计成82 而不是81, 是为了程序的易读性, 使得数组元素的最大下标可达81, 下同。2) int fix82该数组的用途是: 若sd 数组中某位置的数字不为0, 则fix 数组相应位置的元素值记录为1, 否则记录为0。即fix 数组是用来记录哪些位置的数字是已经确定下来的。3) int possible8210该数组的用途是记录所有未确定数字的所有可能性。可能性的记录方法是: possible 数组各元素的值在初始化时被初始化为与其第二维的下标一致, 即0- 9( 其中0 是不会用的) ; 中间计算过程中, 若发现第一维某位置的某种可能性已不复存在, 则将第一维下标是该位置而第二维下标是该不再可能的数字的元素值改为- 1。4) int stack82该数组的用途类似于栈, 在核心回溯过程中起到至关重要的作用。回溯之前, 要把所有fix 数组中值为0 的位置依次存放进stack 数组; 回溯中, 由低到高依次逐渐确定这些位置数值, 无法确定者( 即1- 9 的数字都不适合者) 则应当回退到前一个位置, 修改其假设值, 以此类推, 直至stack 数组所存放的所有位置的值都能确定, 或回退到最初点的前一个位置。（2） 三个重要函数下面介绍几个在“有限递推”预处理和回溯过程中会用到的三个重要函数。1)void setPb();该函数是用来修订possible 数组的。其具体功能是: 对于fix数组中每一个值为0 的位置( 即对于每一个没有确定下数字的位置) , 考察其可能的数字是哪些, 记录下来 。考察的方法是: 在1- 9 这些数字中除去当前行、列、九宫中已有的数字。2)bool fixAll();该函数是用来修订fix 数组和possible 数组的, 其返回值表示了在此次运行该函数过程中是否执行了修订。其具体功能是: 对于fix 数组中每一个值为0 的位置( 即对于每一个没有确定下数字的位置) , 考察其可能的数字的个数, 若为1, 则将fix 数组该位置的值改为1 且sd 数组该位置的值改为该唯一可能的数字( 即该位置的值已确定下来) , 且返回真; 若没有只有一种可能性的位置, 则返回假。3)bool Exist(int i, int j);其用途是: 判断sd 数组中位置为i 的元素的值是否可能为j, 即判断的是: 位置i 所在的行、列以及九宫中是否已经存在数字j, 若存在则返回真, 否则返回假。（3） “有限递推”预处理在执行一次fixAll 函数之后, 就可能会确定下一些原来没有确定的数字, 那么此时,possible 数组的值必然也会变动! 因为确定下的数字越多, 某些位置的可能数字的数目就会减少。那么就应当再执行setPb 函数修订possible 数组, 而修订之后可能又会出现一些只有一种可能性的位置, 那么就应该再执行fixAll 函数了.于是, 只要如此循环往复下去, 就能最大限度地确定下由题目本身含义与规则而确定下的内容。确定的数字越多, 对于将来回溯也就越有利。那么, 有限递推的循环什么时候结束呢? 只有两种情况, 一是推出了全部结果; 二是fixAll 函数返回值为假, 即不存在只有一种可能性的位置。预处理的函数void preDo( ) setPb();FixAll();if(isFull()return;（4） 回溯算法1)按下标的由低到高扫描sd数组, 将值为0 的位置记录进stack 数组, 记录的顺序也由低到高。最后, 整型量max 记录下:sd数组中为0 位置的个数再加1。2)整型量top 初始化为0, 即把stack 看作栈( 虽然stack 数组的内容永远不会变, 但top 的增减仍代表了进栈和出栈的操作) , top 记录的是栈顶。3) bool 型变量flag 初始化为true。下面各步骤都将在一个条件始终为真的死循环中进行, 该循环由一条对flag 进行真假判断的if- else 语句分成两大部分。flag 所代表的意义是:若当前栈顶(top)是经过了回退操作而达到的, 则flag 会已被记录为假; 否则flag 为真。死循环结束的条件是top 与max 的值相等, 即解出最终结果, 或者是无解, 最终top 小于0( 无解的情况基本上在最初做题目的合法性检查时已经排除了) 。在死循环中: 若flag 为真, 进入步骤( 4) , 否则进入步骤( 5) 。4) flag 为真, 说明栈顶(top)是经过正常的假设而达到的, 并非由回退达到, 那么: 根据possible 数组以及Exist 函数,对栈顶所保存位置的可能出现的数字进行判断, 把遇到的第一个可能数字设置进sd 数组, 并判断top 和max 相等否, 若相等,退出死循环; 若发现1- 9 都不可能应用在栈顶所保存的位置, 则说明前面的假设有错误, 此时应当回退, 即: fix 数组和sd 数组的该位置重设为0, top 减1, 并将flag 置为假。本轮循环体结束, 继续下一轮的循环。5)flag 为假, 说明是经过了回退才达到现在这个栈顶的, 那么: 若仍然没有可能的数字可以应用在当前栈顶所保存的位置上, 那么继续执行出栈操作, 即: sd 数组的该位置重设为0, top 减1; 否则将遇到的第一个可能数字应用到该位置, 即:再设好sd 数组, 将top 加1, 并将flag 置为真。本轮循环体结束, 继续下一轮的循环。6)若start = 1 时，表示现在进行的是生成随机数独时求解，当start = 0时，代表此时验证是否有两解，函数不会直接退出循环。而是在遍历完所有情况或者找到第二个解的时候退出程序。（5） 数独生成算法通过该算法用以生成各种难度等级的数独题，通过对游戏规则的分析，首先从以下三个方面定义难度等级：已知格总数和穷举搜索复杂度该算法采用“挖洞”思想。经过以下两步生成数独题：1) 运用上面的算法生成一个终盘；2) “抹去”一部分数字来生成数独题：根据所需要的难度等级选取挖洞的个数；每次挖取改位置的数字时，首先检验挖去该数字后是否是唯一解，若挖去该数字后不是唯一解，则禁止此次操作。为了避免重复挖洞计算，对于一个不挖去的位置，用一个新数组保留下来，每次到高位置时及跳过，经过剪枝后的算法速度会大幅的提高。5 运行与测试结果5.1 程序主要运行界面1）游戏的初始化界面如图4所示图4游戏开始界面2）按下新游戏后的游戏界面，其中计时器开始计时，如图5所示。3）按下暂停后，界面将不可视，如图6所示。图5 游戏开始后运行界面图6 暂停后的界面4）按下难度选择后，出现难度选择界面，如图7所示：5）按下显示答案或者填入答案都正确，出现如图8所示界面： 图7 难度选择界面图8 答案正确的界面6） 填入的数字违反游戏规则时显示为红色，如图9所示： 图9 违反规则时数字界面7）点击右上角的帮助按钮，弹出帮助文档，界面如图10、11所示：图10 帮助文档 图11帮助文档5.2 系统测试5.2.1 界面操作测试通过鼠标单击不同的位置，看方格是否被选中，来测试游戏主界面。通过移动鼠标到不同的按钮上看按钮是否有变化，开检验按钮界面。通过单击按钮来检验按钮是否能执行相应的功能。5.2.2 数独唯一解测试通过解不同难度的数独来测试