九宫格数独游戏C语言解法在线九宫格数独游戏-爱华网

最近几天深圳一直下雨，一个人闷在屋里很是无聊，偶然打开一个小游戏网站看到了我的最爱——九宫格数独游戏。共有1-5五个难度级别，像我这种资深玩家其他难度就不用考虑了，冲着难度5的题目就去了，结果做地汗流浃背也知道过了多长时间还是没解出来，很是受伤啊！题目如下：

这道题靠一般的方法是很难解出来的，最有效也是最复杂的办法是假设-推断-假设......，但是仅凭人的记忆力和计算速度花费的时间是很长的，所以我打算用C语言编写一个程序以求解所有的九宫格数独游戏。下面分析下算法的结构：每个九宫格数独游戏包含了9个九宫格单元，编号如下：

每个九宫格单元有9个数字位，编号如下：

解题思路如下，第0个九宫格缺少数字1、2、6、7、8、9，空缺的数字位为1、2、3、5、6、9，首先看数字1，从数字位1开始查找可以插入的数字位，由于第一列有1，所以不能放在数字位1，再看数字位2可以放下，则将数字1插入九宫格单元0的数字位2，接着按照同样的方式将数字2、6、7、8插入相应的数字位，如下图所示：

下面该插入数字9，此时只剩一个数字位9，但是由于该列已经有数字9，所以数字9是不能插入数字位9的，则将数字8放入下一个数字位，如下图所示：

此时只剩数字位6，显然数字9仍然不能插入该数字位，同时数字8也没有其他的可变换数字位，则将数字8擦除，变化数字7到下一个数字位，同时插入数字8到第一个可以插入的数字位，如下：

可以发现数字9仍没有可以插入的数字位，接着擦除数字7和8，将7变换到下一个数字位....。重复以上步骤，直到将所有的数字填入，并且满足了九宫格的要求，结束并输出最终结果。

看到这里你应该也能看出，求解的过程其实就是一个栈结构。首先查找一个待插入的数字，如果该数字有可以插入的数字位，则将该数字、数字位以及在待插入矩阵的行与列位置压入栈；相反如果没有可插入的数字位，则将栈顶元素弹出，放入到待插入数据的首部，同时变化数字位到下一个位置，如此重复以上步骤直到满足结束条件。算法的流程图如下，其中省掉一些小部分，想了解更多可以参考最后给出的源文件。

下面是对应的C源代码，只是草稿，还没来得及优化，仅供参考。

#include "stdio.h"

//定义栈的最大长度
#define MAXSTACKLENGTH 81
//待求解的九宫格矩阵，空白位置用0表示
int jiuGongArray[][9]={{0,0,0,0,4,0,0,3,2},
{4,0,0,0,0,1,0,0,0},
{5,3,0,6,0,0,0,0,7},
{3,0,0,5,1,0,7,0,0},
{0,0,5,0,3,0,2,0,0},
{0,0,9,0,7,4,0,0,3},
{1,0,0,0,0,9,0,4,6},
{0,0,0,1,0,0,0,0,9},
{8,9,0,0,6,0,0,0,0}};
//空缺数据组成的矩阵，共有九个九宫格单元，从左到右，然后从上到下编号为0-8；
//例如：第一个九宫格单元空缺的数字为1,4,8，则矩阵dataNeedToBeInsert的第一行
//为{1,0,0,4,0,0,0,8,0}
int dataNeedToBeInsert[][9]={{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9}};
//定义栈单元的结构
typedef struct
{
int xPosition;
int yPosition;
int jiuGongGePosition;
int num;
}node;
//定义栈数组
node stack[MAXSTACKLENGTH];

//由给定的九宫格矩阵，查找空缺的数据
void FindDataToBeInsert(void)
{
int i,j;
intx,y;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
{
if(jiuGongArray[i][j]!=0)
{
x=(i/3)*3+j/3;
y=jiuGongArray[i][j]-1;
dataNeedToBeInsert[x][y]=0;
}
}
}
//输出m*n的矩阵
void PrintArray(int *ptr,int m,int n)
{
int i,j;
int data;
int temp;
temp = n-1;
for(i=0;i&l————t;m;i++)
for(j=0;j<n;j++)
{
data =*(ptr+i*n+j);
printf("%d",data);
if(j ==temp)
{
printf("n");
}
}
}
//核实是否满足结束条件
int CheckEnd(void)
{
int i,j,sum;
for(i=0;i<9;i++)
{
sum = 0;
for(j=0;j<9;j++)
{
sum +=jiuGongArray[i][j];
}
if(sum != 45)
{
return-1;
}
}
for(j=0;j<9;j++)
{
sum = 0;
for(i=0;i<9;i++)
{
sum +=jiuGongArray[i][j];
}
if(sum != 45)
{
return-1;
}
}
return 0;
}
//从矩阵dataNeedToBeInsert[][]中查找下一个数据
int FindNextData(int m,int n,int *xPosition,int *yPosition)
{
int state=0;
if(n>8)
{
n = 0;
m++;
}
if(m>8)
{
state = CheckEnd();
if(state != 0)
return-1;
else
return1;
}
while(dataNeedToBeInsert[m][n] == 0)
{
if(n<8)
n++;
else
{
n = 0;
m++;
if(m>8)
{
state= CheckEnd();
if(state!= 0)
return-1;
else
return1;
}
}
}
*xPosition = m;
*yPosition = n;
return 0;
}
//核实元素对应的行和列是否有相同的数字
int CheckLine(int m,int n,int num)
{
int i;
for(i=0;i<9;i++)
{
if(jiuGongArray[m][i] ==num)
return-1;
}
for(i=0;i<9;i++)
{
if(jiuGongArray[i][n] ==num)
return-1;
}
return 0;
}
//核实是否满足入栈条件
int CheckCanPush(int m,int n,int *position)
{
int start=*position;
int i,temp1,temp2,temp3,temp4;
int num;

temp1=(m/3)*3;
temp2=(m%3)*3;
num = dataNeedToBeInsert[m][n];

for(i=start;i<10;i++)
{
temp3 =temp1+(start-1)/3;
temp4 =temp2+(start-1)%3;

if(jiuGongArray[temp3][temp4]!=0)
{
start++;
continue;
}
if(CheckLine(temp3,temp4,num)!=0)
{
start++;
continue;
}
else
{
*position =start;
return0;
}
}

return -1;
}
//入栈
int Push(int *top,int xPosition,int yPosition,intjiuGongGePosition,int num)
{
if(*top >= MAXSTACKLENGTH)
{
printf("Reach stacktop!n");
return -1;
}
else
{
(*top)++;
stack[*top].xPosition =xPosition;
stack[*top].yPosition =yPosition;
stack[*top].jiuGongGePosition =jiuGongGePosition;
stack[*top].num = num;
return 0;
}
}
//出栈
int Pop(int *top,int *xPosition,int *yPosition,int*jiuGongGePosition,int *num)
{
if(*top == -1)
{
printf("Reach stackbottom!n");
return -1;
}
else
{
*xPosition = stack[*top].xPosition;
*yPosition = stack[*top].yPosition;
*jiuGongGePosition =stack[*top].jiuGongGePosition;
*num = stack[*top].num;
(*top)--;
return 0;
}
}

void main()
{
intend=0;
intline=0;
introw=0;
inttop=-1;
intpositionInUnitArray=1;
intstate=0;
intnum;

FindDataToBeInsert();

PrintArray(jiuGongArray,9,9);
while(end!=1)
{
state =FindNextData(line,row,&line,&row);
if(state == 0)
{
state =CheckCanPush(line,row,&positionInUnitArray);
if(state == 0)
{
state =Push(&top,line,row,positionInUnitArray,dataNeedToBeInsert[line][row]);
if(state==0)
{
jiuGongArray[(line/3)*3+(positionInUnitArray-1)/3][(line%3)*3+(positionInUnitArray-1)%3]=dataNeedToBeInsert[line][row];
row++;
positionInUnitArray= 1;
}
else
end= 1;
}
else
{
九宫格数独游戏C语言解法在线九宫格数独游戏
state =Pop(&top,&line,&row,&positionInUnitArray,&num);
if(state ==0)
{
jiuGongArray[(line/3)*3+(positionInUnitArray-1)/3][(line%3)*3+(positionInUnitArray-1)%3]= 0;
positionInUnitArray++;
}
else
end= 1;
}
}
else if(state == 1)
{
printf("n");
PrintArray(jiuGongArray,9,9);
end = 1;
}
else
{
printf("Some erroroccur!n");
end = 1;
}
}
}
由于编辑器不一致，粘贴后的程序结构有点乱，请原谅！