数据结构大型作业实验报告书
设计题目：“数独”游戏设计与求解
一．题目说明
数独的游戏规则：
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 中所有的值都确定下来（即题目完成），或者回退到了最初点的前一位置（说明题目有误）。
四．算法设计
程序可以考虑人工智能的算法。所谓人工智能的算法，应当是算法设计者对该游戏的特性有较为深入的了解，依据其内在联系设计出的和人类思维相似的解决算法。但这似乎太过复杂，所以这里决定采用“回溯”的方法解决数独问题。
基本框架如下：
五．数独程序代码：
#include"stdio.h" //标准输入输出头文件
#include"conio.h" //包含getch()的头文件
#include"stdlib.h" //包含rand()的头文件
#include"assert.h" //包含assert()的头文件
#include"time.h" //包含srand()的头文件
//五个全局变量数组
int a[10][10];//用来接收输入数据的数组
int sd[82];//处理题目以及保存最终结果
int fix[82];//记录哪些位置是确定的，确定为1，否则为0 int possible[82][10];//记录所有未确定数字的可能性
int stack[82];//用来放置填入的数的栈
void clssd()//初始化函数，所有位置设为0
{
int i,j,k;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
a[i][j]=0;
for(k=1;k<=81;k++)
sd[k]=0;
}
int line(int line,int value)//检验行
{
int i;
for(i=1;i<=9;i++)
{
if(a[line][i]==value) return 0;
}
return 1;
}
int row(int row,int value)//检验列
{
int i;
for(i=1;i<=9;i++)
{
if(a[i][row]==value) return 0;
}
return 1;
}
int square(int line,int row,int value)//检验3*3的九宫{
int L,R,i,j;
L=(line%3!=0)+line/3;//L表示所在九宫的行数
R=(row%3!=0)+row/3;//R表示所在九宫的列数
for(i=(L-1)*3+1;i<=L*3;i++)
{
for(j=(R-1)*3+1;j<=R*3;j++)
if(a[i][j]==value) return 0;
}
return 1;
}
//四个转换函数
int transform_to_line(int i)//实现sd[i]->a[line][row]之间的转换{
int line;
line=i/9+(i%9!=0);
return line;
}
int transform_to_row(int i)//实现sd[i]->a[line][row]之间的转换{
int row;
row=i%9+9*(i%9==0);
return row;
}
void transform_to_a(int i)//sd[i]->a[line][row]的转换
{
int l,r;
l=transform_to_line(i);
r=transform_to_row(i);
a[l][r]=sd[i];
}
void transform_to_sd()//实现a[line][row]->sd[i]的转换
