数据结构大型作业实验报告书 设计题目：“数独”游戏设计与求解 一．题目说明 数独的游戏规则： 1、在9×9 的大九宫格内，已给定若干数字，其他宫位留白，玩 家需要自己按照逻辑推敲出剩下的空格里是什么数字。 2、必须满足的条件：每一行与每一列都有 1 到 9 的数字，每个小 九宫格里也有 1 到 9 的数字，并且一个数字在每行、每列及每 个小九宫格里只能出现一次，既不能重复也不能少。 3、每个数独游戏都可根据给定的数字为线索，推算解答出来。 按照数独的游戏规则，用计算机实现已知数独的求解和数独题目的出题。 二．数据结构说明 数据结构一维数组、二维数组以及类似于“栈”的数据结构。 主要操作有：进栈，出栈，栈顶元素的操作等等 三．抽象数据类型(Abstract Data Type 简称 ADT) 五个全局变量数组，其中两个二维数组，三个一维数组。 int a[10][10] 接受输入数据，空白处则初始化为0。之所以把数组范围设计为10*10，是为了程序的可读性。符合人的习惯思维。 int sd[82] 在实现“回溯”算法的时候，因为要用到栈的数据结构，所以把a[10][10]二维数组中的数据转换储存进 sd[82]一维数组。方便处理题目以及保存最后结果。 int fix[82] 对应于 sd[82]，记录哪些位置已经确定。确定则fix 值为1，未确定为0。 int possible[82][10] 第一维对应着 sd[82]中的每一个，第二维的下标为每个位置的可能值。有可能则为第二维的下标，不可能则为-1。 int stack[82] 类似于“栈”数据结构的数组，实现“回溯”算法的关键所在。回溯之前，把所有 fix 值为 0 的数据存如 stack 数组中，即进栈。回溯中逐渐确定这些位置的数值，无法确定者（即 1--9 都不适合的）则应回退到前一位置，修改其 fix 值，以此类推。直至 stack中所有的值都确定下来（即题目完成），或者回退到了最初点的前一位置（说明题目有误）。 四．算法设计 程序可以考虑人工智能的算法。所谓人工智能的算法，应当是算法设计者对该游戏的特性有较为深入的了解，依据其内在联系设计出的和人类思维相似的解决算法。但这似乎太过复杂，所以这里决定采用“回溯”的方法解决数独问题。 基本框架如下： 五．数独程序代码： #inclu de"stdio.h" //标准输入输出头文件 #inclu de"conio.h" //包含 getch()的头文件 从界面读取数据到将 a[10][10] 中数 据 转 存 入sd[82] 预处理，算出所 有 fix 和possible 值 ...
