数独游戏的设计与开发1毕业设计.doc

摘要
本论文介绍了利用C语言编写数独游戏的方法。系统的开发设计使用了turbo C作为开发工具，根据数独游戏特有的规则特点对游戏进行设计。本文首先对开发语言C语言进行了做简单的介绍，并列举了开发语言优于其他语言的特点，其次对游戏进行简单介绍，对游戏的计算机实现进行分析。最后通过部分系统截图和数据表格来介绍了系统的开发设计过程以及系统的基本操作。并根据软件工程的方法，从需求分析、概要设计、详细设计、编码实现等方面阐述了系统的开发流程，并通过系统界面的截图、数据表格等体现了我的设计思路，最后就系统，测试运行情况，测试运行结果和系统开发过程中的技术难点加以分析。
关 键 词 数独游戏 C语言
Abstract
This paper introduces the method of using C language to write sudoku game. The development of the system design using turbo C as a development tool, according to the rules of sudoku peculiar characteristics of game design. This article first to the development of language C language to do simple introduction, and lists the development language is better than that of other language features, a brief introduction to the second of the game, the game of computer implementation are analyzed. Finally, part of the system screenshots and data form to the development of the system design process are introduced and the basic operation system. And according to the method of software engineering, from the demand analysis, general design, detailed design, coding, implementation aspects elaborated the system development process, and through the system interface screenshots, data form reflected my design ideas, such as the final system, test run, test run results, and analyze the technical difficulties in the process of system development.
Keywords: Sudoku； C language

目录
1 引言 1
1.1 简介 1
1.2 数独的起源 1
1.2.1 拉丁方块 1
1.2.2 九宫图 2
1.3 数独的发展 2
1.3.1 Nikoli将其引入日本并命名为 Sudoku 2
1.3.2 Sudoku传入英国并速度流行风靡全球 3
1.3.3 数独游戏的流行及其与计算机的结合 3
2开发环境及开发工具 4
2.1 C语言简介 4
2.2 C语言优于其他语言的特点 4
3 系统的需求分析 6
3.1 技术可行性 6
3.2 操作可行性 6
3.2.1生成数独题目的方法 6
3.2.2 推导题目的方法 6
3.2.3 数独题目的变换 7
4 用C语言编写数独游戏程序 8
4.1设计思路 8
4.1.1 总体思路 8
4.1.2 过程分析： 8
4.2 具体步骤与代码 8
4.3 测试运行结果 15
结果： 15
总结及体会： 17
致 谢 17
参 考 文 献 1

1 引言
1.1 简介
数独（Sudoku）是一种源自18世纪末的瑞士后在美国发展，并在日本得以发扬光大的数学智力拼图游戏。游戏拼图有多种表现形式，现在流行的玩法主要以九宫格（即3格宽×3格高的正方形）为主，每一格又细分为一个九宫格。在每一个小九宫格中，分别填上1至9的数字，让整个大九宫格每一列、每一行的数字都不重复。

图1-1
1.2 数独的起源
1.2.1 拉丁方块
据说是大数学家欧拉(Euler)发明了数独的最初版本，这与我们现在所熟知的在世界范围内广为流传的数独游戏是一致的。但是在当时（18世纪末）瑞士大数学家莱昂哈德.欧拉发明的“拉丁方块”并没有受到人们的重视。

图1-2

1.2.2 九宫图
另一种关于数独游戏起源的说法是早在数千年前，中国人就发明了九宫图。九宫图又名洛书。其实在中国数独的渊源比“拉丁方块”更为久远，还记得金庸的《射雕英雄传》么? 黄蓉在破解瑛姑的九宫图时的“二四为肩，六八为足，左三右七，戴九履一，五居中央”，数独对于中国人来说已经不是什么新鲜事了。
相传大禹治水时龙龟载洛书而出，夏禹受其启发而成就一番伟业。我国关于数独的最早文献记载出现在汉朝，在流传下来的当时的书籍里就有就有“九宫格”在9个方格中，横行和竖行的数字总和是相同的记载。

图1-3

图1-4
1.3 数独的发展
1.3.1 Nikoli将其引入日本并命名为 Sudoku
数独游戏在1970年已经由美国的一家数学逻辑游戏杂志首先发表，当时名为Number Place。但在众多填字游戏中并未引起特别注意。直到1984年，日本的填字游戏出版商Nikoli公司的煅治真起从美国发现了这个游戏，决定引入日本并将其命名为Sudoku，意思是每个数字只能出现一次。这个游戏在日本开始流行，数独即为日语すうどく(Sudoku)的音译(意译其实也是)，也就是只有一个数字的意思。
1.3.2 Sudoku传入英国并速度流行风靡全球
数独成为大众的流行游戏，得归功于香港高等法院法官高乐德（Wayne Gould）。2004年，他在日本旅行的时候，发现杂志上介绍的这款游戏，便带回伦敦向《泰晤士报》推介并获得接纳。英国《每日邮报》也于三日后开始连载，使数独在英国正式掀起热潮。很快，其他国家和地区受其影响也开始风靡数独。
1.3.3 数独游戏的流行及其与计算机的结合
数独的玩法逻辑简单，数字或符号的排列方式千变万化，不少教育学者认为数独是锻炼逻辑思维能力的上佳办法。虽然数独长期以来一直是作为数学逻辑游戏在纸面上进行，但却可以用简单的程序编制出来，非常适合于移植到数码设备中。而且，玩家用简单的输入设备就可以轻松操作，无需翻译就能在全球各地进行流通。
除了英国《泰晤士报》发行的首款手机版数独游戏，一些游戏软件开发公司纷纷开发出不同计算机版本的数独游戏，以及在线网络数独游戏将其提供给广大玩家。 位于英国的S游戏软件公司表示，已经在全球卖出了7500套数独游戏，而且来自用户的兴趣还在增加。
2开发环境及开发工具
2.1 C语言简介
C语言是一种计算机程序设计语言。它既有高级语言的特点，又具有汇编语言的特点。它可以作为系统设计语言，编写工作系统应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。因此，它的应用范围广泛。
2.2 C语言优于其他语言的特点
1. 简洁紧凑、灵活方便
　　C语言一共只有32个关键字,9种控制语句，程序书写自由，主要用小写字母表示。它把高级语言的基本结构和语句与低级语言的实用性结合起来。 C 语言可以象汇编语言一样对位、字节和地址进行操作, 而这三者是计算机最基本的工作单元。
　　2. 运算符丰富
　　C的运算符包含的范围很广泛，共有种34个运算符。C语言把括号、赋值、强制类型转换等都作为运算符处理。从而使C的运算类型极其丰富表达式类型多样化，灵活使用各种运算符可以实现在其它高级语言中难以实现的运算。
　　3. 数据结构丰富
　　C的数据类型有：整型、实型、字符型、数组类型、指针类型、结构体类型、共用体类型等。能用来实现各种复杂的数据类型的运算。并引入了指针概念,使程序效率更高。另外C语言具有强大的图形功能, 支持多种显示器和驱动器。且计算功能、逻辑判断功能强大。
　　4. C是结构式语言
　　结构式语言的显著特点是代码及数据的分隔化,即程序的各个部分除了必要的信息交流外彼此独立。这种结构化方式可使程序层次清晰,便于使用、维护以及调试。C语言是以函数形式提供给用户的,这些函数可方便的调用,并具有多种循环、条件语句控制程序流向,从而使程序完全结构化。
　　5. C语法限制不太严格、程序设计自由度大
　　一般的高级语言语法检查比较严，能够检查出几乎所有的语法错误。而C语言允许程序编写者有较大的自由度。
　　6. C语言允许直接访问物理地址，可以直接对硬件进行操作
　　因此既具有高级语言的功能，又具有低级语言的许多功能，能够象汇编语言一样对位、字节和地址进行操作,而这三者是计算机最基本的工作单元，可以用来写系统软件。
　　7. C语言程序生成代码质量高，程序执行效率高
　　一般只比汇编程序生成的目标代码效率低10へ20%。
　　8. C语言适用范围大，可移植性好
　 C语言有一个突出的优点就是适合于多种操作系统, 如DOS、UNIX,也适用于多种机型。
　　当然，C语言也有自身的不足，比如：C语言的语法限制不太严格，对变量的类型约束不严格，影响程序的安全性，对数族下标越界不作检查等。从应用的角度，C语言比其他高级语言较难掌握。
　　总之，C语言既有高级语言的特点，又具有汇编语言的特点；既是一个成功的系统设计语言，又是一个使用的程序设计语言；既能用来编写不依赖计算机硬件的应用程序，又能用来编写各种系统程序；是一种受欢迎、应用广泛的程序设计语言C语言版本 。

3 系统的需求分析
“数独”，即“独立的数字”的省略，在一个9x9的方格中，有81个小方格组成，然后又分9个大块，每块由3x3的方格组成，就是九宫图，大九宫里面再套9个小九宫，共九九八十一个小格子，游戏开始前会有一些格子上写好了数，你需要在剩下的格子里填数，真到把所有格子填满，并且要求，任何一行或一列或者一个小九宫中没有相同的数字
3.1 技术可行性
利用C语言的逻辑性，用简洁的程序来描述复杂的变换。只要根据数独游戏的逻辑性来编写，先得到一个完整的数独，然后根据难度需要，随机地挖一些空格出来。便可以得到唯一解的数独。
3.2 操作可行性
3.2.1生成数独题目的方法
产生数独题目的方法是从答案反推题目。为了便于理解，可以先从2×2的4个四宫格（共16个宫格）开始思考、推论。
以2×2个四宫格的数独解为例，为了方便解说，把方阵内的数字位置分区块为A区、B区、C区、D区，如图所示

图3-1
3.2.2 推导题目的方法
任意选取一个空格，并将此空格内的数字挖掉。例如将（3，3）位置的数字4挖掉，如图3所示。
观察B区的四宫格可以发现，不管（2，2）位置的数字4是否存在，为了确定（4，1）位置挖掉的数字4，（3，1）位置的数字2必须存在，如图4所示。

图3-2 挖掉（3，3）位置的数字4 图3-3 保留（3，1）位置的数字2
观察A区的四宫格，由于（3，1）位置的数字2已存在，为了要找到（1，2）位置的数字2，则（2，2）位置的数字4必须存在，如图5所示。
观察C区的四宫格，由于（2，2）位置的数字4已存在，为了要找到（1，4）位置的数字4，则（1，3）位置的数字3必须存在，如图6所示。

图3-4 保留（2，2）位置的数字4 图3-5 保留（1，3）位置的数字3
观察D区的四宫格，由于（1，3）位置的数字3已存在，为了要找到（3，4）位置的数字3，则（4，4）位置的数字1必须存在，如图7所示。

3.2.3 数独题目的变换
经过这5个步骤可以发现：只需要提供这4个位置的数字就可以得出一个唯一解的数独谜题，如图8所示。另外，通过以下形式的变换方式，仍然可以得到唯一解的数独谜题。

图3-6 保留（4，4）位置的数字1 图3-7 最终谜题
（1）行列交换：将同一四宫格内的行列交换，例如，将第1、2列互调；第3、4列互调；第1、2行互调；第3、4行互调，如图9和图10所示。标准3×3个九宫格的数独谜题的推出原理与此相同，但过程比较复杂。
（2）数字替换：例如数字1换4；数字2换3，如图11所示。

图3-8 行变换 图3-9 列变换 图3-10 数字变换

4 用C语言编写数独游戏程序
4.1设计思路
4.1.1 总体思路
先得到一个完整的数独，然后根据难度需要，随机地挖一些空格出来，然后判断是否符合条件（游戏规则），循环再输出。
4.1.2 过程分析：
首先，确定一个9×9的正方形盘。
第一行：取1~9个数字，然后把数字打乱放好到每一行每个格子里面。
第二行开始：（因为有了第一行的限制，所以第二行开始就不能乱填了）。这时可以选择建立一个函数专门用来填数字，从第一列开始到第9列结束。
函数的实现过程基本是这样的：首先生成一个随机数，1到9，这时候判断跟同一行前面填了的有没有重复的，重复的重来，还要再判断跟同一列的填的有没有重复，重复的从来，总有一个会适合的。
数都生成好了，然后游戏的时候随机把一些数遮盖住（生成空格），判断填入对不对。
4.2 具体步骤与代码
#include < stdio.h >
#include < stdlib.h >

int sudoku[81] ; // 数独题目阵列
int tempNum[81] ; // 上一次填数位置
int tempSp= 0 ; // 上一次填数位置指标
int startH[81] ; // 列位置的起点
int startV[81] ; // 行位置的起点
int startB[81] ; // 九宫格位置的起点
int addH[9] ; // 列位置的加值
int addV[9] ; // 行位置的加值
int addB[9] ; // 九宫格位置的加值

int main(int argc, char *argv[]) {
int j ;
if(argc>1) for(j=0; j<81; j++) sudoku[j]= argv[1][j]-'0' ;
else exit(0) ;
printf( "----------\n");
printSudoku(sudoku) ;
init() ; // 参数设定
tryAns() ; // 测试求解
printf( "----------\n");
printSudoku(sudoku) ;
printf( "----------\n");
}

int init() {
// 参数设定(设定这些参数之后，无论检查行、列、九宫格都方便多了)
int i ;
for(i=0; i<81; i++) {
startH[i]= i/9* 9 ; // 列位置的起点
startV[i]= i% 9 ; // 行位置的起点
startB[i]= ((i/9)/3)*27+ ((i%9)/3)*3 ; // 九宫格位置的起点
}
for(i=0; i<9; i++) {
addH[i]= i ; // 列位置的加值
addV[i]= i*9 ; // 行位置的加值
addB[i]= (i/3)*9+ (i%3) ; // 九宫格位置的加值
}
}

int printSudoku(int *prn) {
// 印出数独题目(阵列内容)
int i ;
for(i=0; i<81; i++) {
printf( "%2d", prn[i]);
if(i%9==8) printf("\n");
}
}

int tryAns() {
// 测试求解
int sp=getNextBlank(-1) ; // 取得第一个空白的位置开始填入数字
do {
sudoku[sp]++ ; // 将本位置数字加 1
if(sudoku[sp]>9) { // 如果本位置的数字已大於 9 时则回到上一个位置继续测试
sudoku[sp]= 0 ;
sp= pop() ;
} else {
if(check(sp)==0) { // 如果同行、列、九宫格都没有相同的数字，则到下一个空白处继续
push(sp) ; // 当然，如果发现有相同的数字时，就需把原位置的数字加 1(所以本处什麼都不做)

sp= getNextBlank(sp) ;
}
}
} while(sp>=0 && sp<81) ;
}

int getNextBlank(int sp) {
// 取得下一个空白的位置
do {
sp++ ;
} while(sp<81 && sudoku[sp]>0) ;
return(sp) ;
}

int check(int sp) {
// 检查同行、列、九宫格有没有相同的数字，若有传回 1
int fg= 0 ;
if(!fg) fg= check1(sp, startH[sp], addH) ; // 检查同列有没有相同的数字
if(fg) fg= check1(sp, startV[sp], addV) ; // 检查同行有没有相同的数字
if(!fg) fg= check1(sp, startB[sp], addB) ; // 检查同九宫格有没有相同的数字
return(fg) ;
}

int check1(int sp, int start, int *addnum) {
// 检查指定的行、列、九宫格有没有相同的数字，若有传回 1
int fg= 0, i, sp1 ;
for(i=0; i<9; i++) {
sp1= start+ addnum[i] ;
if(sp!=sp1 && sudoku[sp]==sudoku[sp1]) fg++ ;
}
return(fg) ;
}

int push(int sp) {
// 将指定的位置放入堆叠中
tempNum[tempSp++]= sp ;
}

int pop() {
// 取出堆叠中的上一个位置
if(tempSp<0) return(-1) ;
else return(tempNum[--tempSp]) ;
}
public class ShuDu {
/**存储数字的数组*/
static int[][] n = new int[9][9];
/**生成随机数字的源数组，随机数字从该数组中产生*/
static int[] num = {1,2,3,4,5,6,7,8,9};
public static void main(String[] args) {
//生成数字
for(int i = 0;i < 9;i++){
//尝试填充的数字次数
int time = 0;
//填充数字
for(int j = 0;j < 9;j++){
//产生数字
n[i][j] = generateNum(time);
//如果返回值为0，则代表卡住，退回处理
//退回处理的原则是：如果不是第一列，则先倒退到前一列，否则倒退到前一行的最后一列
if(n[i][j] == 0){
//不是第一列，则倒退一列
if(j > 0){
j-=2;
continue;
}else{//是第一列，则倒退到上一行的最后一列
i--;
j = 8;
continue;
}
}
//填充成功
if(isCorret(i,j)){
//初始化time，为下一次填充做准备
time = 0;
}else{ //继续填充
//次数增加1
time++;
//继续填充当前格
j--;
}
}
}
//输出结果
for(int i = 0;i < 9;i++){
for(int j = 0;j < 9;j++){
System.out.print(n[i][j] + " ");
}
System.out.println();
}
}

/**
* 是否满足行、列和3X3区域不重复的要求
* @param row 行号
* @param col 列号
* @return true代表符合要求
*/
public static boolean isCorret(int row,int col){
return (checkRow(row) & checkLine(col) & checkNine(row,col));
}

/**
* 检查行是否符合要求
* @param row 检查的行号
* @return true代表符合要求
*/
public static boolean checkRow(int row){
for(int j = 0;j < 8;j++){
if(n[row][j] == 0){
continue;
}
for(int k =j + 1;k< 9;k++){
if(n[row][j] == n[row][k]){
return false;
}
}
}
return true;
}

/**
* 检查列是否符合要求
* @param col 检查的列号
* @return true代表符合要求
*/
public static boolean checkLine(int col){
for(int j = 0;j < 8;j++){
if(n[j][col] == 0){
continue;
}
for(int k =j + 1;k< 9;k++){
if(n[j][col] == n[k][col]){
return false;
}
}
}
return true;
}

/**
* 检查3X3区域是否符合要求
* @param row 检查的行号
* @param col 检查的列号
* @return true代表符合要求
*/
public static boolean checkNine(int row,int col){
//获得左上角的坐标
int j = row / 3 * 3;
int k = col /3 * 3;
//循环比较
for(int i = 0;i < 8;i++){
if(n[j + i/3][k + i % 3] == 0){
continue;
}
for(int m = i+ 1;m < 9;m++){
if(n[j + i/3][k + i % 3] == n[j + m/3][k + m % 3]){
return false;
}
}
}
return true;
}

/**
* 产生1-9之间的随机数字
* 规则：生成的随机数字放置在数组8-time下标的位置，随着time的增加，已经尝试过的数字将不会在取到
* 说明：即第一次次是从所有数字中随机，第二次时从前八个数字中随机，依次类推，
* 这样既保证随机，也不会再重复取已经不符合要求的数字，提高程序的效率
* 这个规则是本算法的核心
* @param time 填充的次数，0代表第一次填充
* @return
*/
public static int generateNum(int time){
//第一次尝试时，初始化随机数字源数组
if(time == 0){
for(int i = 0;i < 9;i++){
num[i] = i + 1;
}
}
//第10次填充，表明该位置已经卡住，则返回0，由主程序处理退回
if(time == 9){
return 0;
}
//不是第一次填充
//生成随机数字，该数字是数组的下标，取数组num中该下标对应的数字为随机数字
int ranNum = (int)(Math.random() * (9 - time));
//把数字放置在数组倒数第time个位置，
int temp = num[8 - time];
num[8 - time] = num[ranNum];
num[ranNum] = temp;
//返回数字
return num[8 - time];
}
}
4.3 测试运行结果
结果：
随机生成一个数独,输入空格数40
[ ] < 7 > < 8 > [ ] [ ] [ ] [ ] [ ] < 6 >
< 6 > < 3 > [ ] < 7 > [ ] < 2 > < 8 > [ ] < 5 >
< 2 > [ ] [ ] < 8 > [ ] [ ] [ ] [ ] < 9 >
< 3 > < 9 > [ ] < 1 > [ ] [ ] < 2 > < 5 > [ ]
[ ] [ ] [ ] < 2 > < 5 > < 4 > < 6 > [ ] < 3 >
< 4 > [ ] [ ] [ ] [ ] [ ] < 7 > < 1 > [ ]
[ ] [ ] [ ] < 4 > < 7 > [ ] [ ] < 3 > < 1 >
< 9 > < 4 > [ ] < 6 > < 2 > < 1 > < 5 > < 8 > [ ]
[ ] < 1 > < 7 > < 9 > < 3 > [ ] [ ] < 6 > < 2 >
开始解数独:
< 1 > < 7 > < 8 > < 5 > < 4 > < 9 > < 3 > < 2 > < 6 >
< 6 > < 3 > < 9 > < 7 > < 1 > < 2 > < 8 > < 4 > < 5 >
< 2 > < 5 > < 4 > < 8 > < 6 > < 3 > < 1 > < 7 > < 9 >
< 3 > < 9 > < 6 > < 1 > < 8 > < 7 > < 2 > < 5 > < 4 >
< 7 > < 8 > < 1 > < 2 > < 5 > < 4 > < 6 > < 9 > < 3 >
< 4 > < 2 > < 5 > < 3 > < 9 > < 6 > < 7 > < 1 > < 8 >
< 5 > < 6 > < 2 > < 4 > < 7 > < 8 > < 9 > < 3 > < 1 >
< 9 > < 4 > < 3 > < 6 > < 2 > < 1 > < 5 > < 8 > < 7 >
< 8 > < 1 > < 7 > < 9 > < 3 > < 5 > < 4 > < 6 > < 2 >

Press any key to continue

总结及体会：
毕业设计是对我们三年所学知识最后一次综合性检测和实际应用能力的考察。我们课程设计的题目是“基于C语言的数独程序设计”，该课题使我对所学的知识有了一个比较系统的认识和理解。涉及了软件工程、C语言、数据库等科目，综合能力有了进一步提高，同时使我学会了如何使用所学的知识去解决一些实际的问题，增强了我们的动手能力。
本次设计的数独游戏虽然设计简单，但综合了所学知识的理论与基础。通过对本次游戏的设计，将所学的知识运用到实际生活去了。从而知道自己对知识的掌握情况。经这次设计，让专业知识与实践结合，让专业知识得到了更好的消化和更牢固的掌握。而且我明白了知识不是单一的，它是互相联系的，学科与学科之间都有着内在联系。计算机是一门非常复杂、庞大的学科，一项课题往往需要多项技术才可以完成。在设计阶段，通过对课题的深层分析与研究，使我又对多门技术有了一定的了解。在遇到困难时，我懂得了该怎样去应对，如何去查找和分析相关资料。
在