数独游戏的解法:
先将数独分为九个格子,用一个数组将每个小九宫格的候选数存放下来,将候选数挨个放进数独里的空位,如果这一行和这一列都没有这个数字,继续放入下一个,如果不能放入的话就回到上一步继续尝试,直到成功求出数独的解为止;
比如这个数独第一个九宫格的候选数就有1、2、7,8,9,我们需要从1开始放入第一个格子挨个尝试直到8的时候发现剩下的两个格子都不能放入
这个时候我们发现2不能放入剩下的两格,我们就继续撤回到1插入的时候,将2放入1号位置,然后挨个放入剩下的数
循环这一过程,直到数独求出解为止;
这个方法比较容易想到,操作也比较容易实现
下面是代码
代码大多数都写了备注便于理解
题目需要的1000道题放在下面了,将这1000个txt文件拷到EXE文件同一目录就可以了
题目链接:数独题目
# include & lt; stdio.h>
# include & lt; stdlib.h>
# include & lt; string.h>
#定义MAX 81
typedef struct asd {
int x;//待测试的值的x坐标
int y;//待测试的值的y坐标
int p;//待测试的值的位置(1道9代表在九宫格里的位置)
int n;//待测试的值
};
詹(MAX);//存放每个放进题目数组测试的数据
空白kongque (int queshi [9] [9], int aa[9][9]);//函数将候选数数组里去除题目中有的数字
空白shuchu (int aa [9] [9], int q);//输出整个数组到文件中
int结束(int aa [9] [9]);//判断是否结束
int next (int queshi [9] [9], int, int, int * x, int * y, int aa[9][9]);//查找下一个应该放进九宫格测试的数据
int chazhao (int aa [9] [9], int, int, int num);//查找同一行同一列是否有相同的值
int nfrz (int queshi [9] [9], int aa [9] [9], int, int, int * p);//判断是否满足入栈条件(就是当前值是否可以插入九宫格)
int rz (int * t, int x, int y, int, int num);//入栈操作
int cz (int * t, int * x, int * y, int * p, int * num);//出栈操作
空白aaaa级(char aa [10], int);//计算题目文件的文件名
空白bbbb (char aa [10], int);//计算答案文件的文件名
int main () {
int我;//记录该调用哪道题
(i=0; i<1000;我+ +){
int aa [9] [9], j, k;//aa数组存放的是题目数独
int queshi[9][9];//存放的是每个九宫格的待选数
int结束=0;//判断循环结束条件
int h=0, l=0, p=1;//h是候选数的行坐标,l是候选数的列坐标,p代表当前测试数属于小九宫格的位置
int t=1;//栈的长度
int s=0, num;
文件* u;
char qwe [10];
(j=0; j<9; j + +)//将数组置为每行都是(1到9)
(k=0; k<9 k + +)
queshi [j] [k]=k + 1;
aaaa级(qwe,我);
u=fopen (qwe,“r”);
(j=0; j<9; j + +){//读入题目
(k=0; k<9 k + +) {
fscanf (u,“% d”,和aa [j] [k]);
}
}
文件关闭(u);
詹詹memset (0 sizeof());//将栈的数据全部置为0
kongque (queshi aa);
而(结束!=1){//开始求解
s=next (queshi、h、l和h和l, aa);//查找下一个应该放进九宫格测试的数据
如果(s==0){//如果找到则进入下一层
s=nfrz (queshi、aa、h、l和p);//判断能否插入数独里
如果(s==0){//如果可以则将插入的数据存放到栈里(入栈)
s=rz(及t、h、l p, queshi [h] [l]);
如果(s==0){//如果入栈成功则写入数独
aa (h/3 * 3 + (p - 1)/3] [h % 3 * 3 + (p - 1) % 3]=queshi [h] [l];
l + +,//待选数跳到下一个
p=1;//重新从第一个小格子开始判断是否插入
}
其他{
结束=1;//循环结束
}
}
其他{
t s=cz (,,, h和l, p, num);
如果(s==0){//如果出栈成功则擦除插入的数据
aa (h/3 * 3 + (p - 1)/3] [h % 3 * 3 + (p - 1) % 3]=0;
p + +;
}
其他的
结束=1;
}
}
else if (s==1) {
shuchu (aa, i);//输出求解完毕的数独
结束=1;
}
其他{
printf("发生未知错误”);
结束=1;
}
}
}
返回0;
}//函数将候选数数组里去除题目中有的数字
空白kongque (int queshi [9] [9], int aa [9] [9]) {
int i, j, x, y;
(i=0; i
