数独游戏的解法：
先将数独分为九个格子，用一个数组将每个小九宫格的候选数存放下来，将候选数挨个放进数独里的空位，如果这一行和这一列都没有这个数字，继续放入下一个，如果不能放入的话就回到上一步继续尝试，直到成功求出数独的解为止；
比如这个数独第一个九宫格的候选数就有1,2,7,8,9，我们需要从1开始放入第一个格子挨个尝试直到8的时候发现剩下的两个格子都不能放入
这个时候我们就要撤回上一个插入的7，发现8仍然不能放入，就继续撤回2，发现8可以放入，就将8放入3号位置，然后将9插入
这个时候我们发现2不能放入剩下的两格，我们就继续撤回到1插入的时候，将2放入1号位置，然后挨个放入剩下的数
循环这一过程，直到数独求出解为止；
这个方法比较容易想到，操作也比较容易实现
下面是代码
代码大多数都写了备注便于理解
题目需要的1000道题放在下面了，将这1000个txt文件拷到EXE文件同一目录就可以了
题目链接：数独题目
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
|
#include <stdio.h>#include <stdlib.h>#include <string.h> #define MAX 81typedef struct asd{ int x;//待测试的值的x坐标 int y;//待测试的值的y坐标 int p;//待测试的值的位置（1道9代表在九宫格里的位置） int n;//待测试的值}A;A zhan[MAX];//存放每个放进题目数组测试的数据 void kongque(int queshi[9][9],int aa[9][9]);//函数将候选数数组里去除题目中有的数字 void shuchu(int aa[9][9],int q);//输出整个数组到文件中 int end(int aa[9][9]); //判断是否结束 int next(int queshi[9][9],int m,int n,int *x,int *y,int aa[9][9]);//查找下一个应该放进九宫格测试的数据 int chazhao(int aa[9][9],int m,int n,int num);//查找同一行同一列是否有相同的值 int nfrz(int queshi[9][9],int aa[9][9],int m,int n,int *p);//判断是否满足入栈条件（就是当前值是否可以插入九宫格） int rz(int *t,int x,int y,int p,int num);//入栈操作 int cz(int *t,int *x,int *y,int *p,int *num);//出栈操作 void aaaa(char aa[10],int a);//计算题目文件的文件名 void bbbb(char aa[10],int a);//计算答案文件的文件名int main(){ int i;//记录该调用哪道题 for(i=0;i<1000;i++){ int aa[9][9],j,k;//aa数组存放的是题目数独 int queshi[9][9];//存放的是每个九宫格的待选数 int end=0;//判断循环结束条件 int h=0,l=0,p=1;//h是候选数的行坐标，l是候选数的列坐标，p代表当前测试数属于小九宫格的位置 int t=-1;//栈的长度 int s=0,num; FILE *u; char qwe[10]; for(j=0;j<9;j++)//将数组置为每行都是（1到9） for(k=0;k<9;k++) queshi[j][k]=k+1; aaaa(qwe,i); u=fopen(qwe,"r"); for(j=0;j<9;j++){//读入题目 for(k=0;k<9;k++){ fscanf(u,"%d",&aa[j][k]); } } fclose(u); memset(zhan,0,sizeof(zhan));//将栈的数据全部置为0 kongque(queshi,aa); while(end!=1){//开始求解 s=next(queshi,h,l,&h,&l,aa);//查找下一个应该放进九宫格测试的数据 if(s==0){//如果找到则进入下一层 s=nfrz(queshi,aa,h,l,&p);//判断能否插入数独里 if(s==0){//如果可以则将插入的数据存放到栈里（入栈） s=rz(&t,h,l,p,queshi[h][l]); if(s==0){ //如果入栈成功则写入数独 aa[h/3*3+(p-1)/3][h%3*3+(p-1)%3]=queshi[h][l]; l++;//待选数跳到下一个 p=1;//重新从第一个小格子开始判断是否插入 } else{ end=1;//循环结束 } } else{ s=cz(&t,&h,&l,&p,&num); if(s==0){//如果出栈成功则擦除插入的数据 aa[h/3*3+(p-1)/3][h%3*3+(p-1)%3]=0; p++; } else end=1; } } else if(s==-1){ shuchu(aa,i);//输出求解完毕的数独 end=1; } else{ printf("发生未知错误"); end=1; } } } return 0;}//函数将候选数数组里去除题目中有的数字 void kongque(int queshi[9][9],int aa[9][9]){ int i,j,x,y; for(i=0;i<j;i++){ for(j=0;j<9;j++){ if(aa[i][j]){ x=i/3*3+j/3;//数独数组和候选数数组的坐标转换 y=aa[i][j]-1; queshi[x][y]=0; } } }}//输出整个数组到文件中void shuchu(int aa[9][9],int q){ int i,j; FILE *p; char qq[10]; bbbb(qq,q); p=fopen(qq,"w"); for(i=0;i<9;i++){ for(j=0;j<9;j++){ fprintf(p,"%d ",aa[i][j]); } fprintf(p,"\n"); } fclose(p);}//判断是否结束int end(int aa[9][9]){ int i,j,num=0; for(i=0;i<9;i++){ num=0; for(j=0;j<0;j++){ num+=aa[i][j];//检查每一行是否为1到9 } if(num!=45) return -1; } for(j=0;j<9;j++){//检查每一列是否为1到9 num=0; for(i=0;i<9;i++){ num+=aa[i][j]; } if(num!=45) return -1; } return 0;}//查找下一个应该放进九宫格测试的数据 int next(int queshi[9][9],int m,int n,int *x,int *y,int aa[9][9]){ int qqq=0; if(n>8){//如果当前小九宫格填写完毕则进入下一个九宫格 n=0; m++; } if(m>8){ qqq=end(aa);//判断是否结束 if(qqq!=0) return -1; else return 1; } while(queshi[m][n]==0){ if(n<8) n++; else{ n=0; m++; if(m>8){ qqq=end(aa); if(qqq!=0) return -1; else return 1; } } } *x=m;//重新获取测试的值的x坐标和y坐标 *y=n; return 0;}//查找同一行同一列是否有相同的值 int chazhao(int aa[9][9],int m,int n,int num){ int i; for(i=0;i<9;i++){//查找行 if(aa[m][i]==num) return -1; } for(i=0;i<9;i++){//查找列 if(aa[i][n]==num) return -1; } return 0;}//判断是否满足入栈条件（就是当前值是否可以插入九宫格） int nfrz(int queshi[9][9],int aa[9][9],int m,int n,int *p){ int s=*p; int i,t1,t2,num; num=queshi[m][n]; for(i=s;i<10;i++){ t1=(m/3)*3+(s-1)/3; t2=(m%3)*3+(s-1)%3; if(aa[t1][t2]!=0){ s++; continue; } if(chazhao(aa,t1,t2,num)!=0){ s++; continue; } else{ *p=s; return 0; } } return -1;}//入栈操作 int rz(int *t,int x,int y,int p,int num){ if(*t>=MAX){ return -1; } else{ (*t)++; zhan[*t].x=x; zhan[*t].y=y; zhan[*t].p=p; zhan[*t].n=num; return 0; }}//出栈操作 int cz(int *t,int *x,int *y,int *p,int *num){ if(*t==-1){ return -1; } else{ *x=zhan[*t].x; *y=zhan[*t].y; *p=zhan[*t].p; *num=zhan[*t].n; (*t)--; return 0; }}//计算题目文件的文件名 void aaaa(char aa[10],int a){ if(a>=0&&a<10){ aa[0]='0'; aa[1]='0'; aa[2]='0'; aa[3]=a+'0'; } else if(a<100){ aa[0]='0'; aa[1]='0'; aa[2]=a/10+'0'; aa[3]=a%10+'0'; } else if(a<1000){ aa[0]='0'; aa[1]=a/100+'0'; aa[2]=a/10%10+'0'; aa[3]=a%10+'0'; } aa[4]='.'; aa[5]='t'; aa[6]='x'; aa[7]='t'; aa[8]='\0';}//计算答案文件的文件名void bbbb(char aa[10],int a){ if(a>=0&&a<10){ aa[0]='a'; aa[1]='0'; aa[2]='0'; aa[3]=a+'0'; } else if(a<100){ aa[0]='a'; aa[1]='0'; aa[2]=a/10+'0'; aa[3]=a%10+'0'; } else if(a<1000){ aa[0]='a'; aa[1]=a/100+'0'; aa[2]=a/10%10+'0'; aa[3]=a%10+'0'; } aa[4]='.'; aa[5]='t'; aa[6]='x'; aa[7]='t'; aa[8]='\0';} |
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/zhha1779628196/article/details/77853418
