iOS开发 Swift开发数独游戏（二）数独题目的生成
浏览数：24 /
时间：2015年06月11日
一、Plist文件结构设计
由于要预先生成数独题目的文件，我自然而然想到用plist存取。
我用Xcode建了几个plist文件来熟悉这种文件使用的结构后设计了如下结构：
为区分难度（后来了解到挖空数与难度其实不一定相对应），我笼统的以挖空数分类，每一个分类下存储这一挖空数对应的数独题目与解。
具体来说，root使用Dictionary类型，下面的关键字以“D”开头，后面为挖空的数目，每个“DXX”为Array类型，内容为不同的数独题目与解，每个数独题是Dictionary类型，关键字“p”代表题目，“s”表示这个题目的多种解。题目与答案都是String，“0”代表这是一个空，否则代表一个数字
如图“D51”表示挖空51个，“Item0”为挖空51个下的第一个数独题，p为数独题目，s下为多个解。
二、设计生成数度题目与解法的算法
作为一个懂得合理偷懒的人（其实是个算法渣），我参考了这篇文章：
http://www.cnblogs.com/gkfeng/archive/2012/09/15/2686452.html
该算法貌似是DFS+剪枝的思想，还能生成多解，于是我拿来改了改，使之直接生成plist文件。注意plist文件一点要符合apple的格式，一旦不符合就不能读取。
第267行 while (blanks<61) { “<61”代表挖空挖到60
1: #include <fstream>
2: #include <unistd.h>
3: #include "stdio.h"
4: #include "stdlib.h"
5: #include "time.h"
6: //#include "fstream.h"
7: #include <iostream>
8: #include <sstream>
9: #include <string>
10: using namespace std;
11: ostringstream oss;
12: ostringstream coutt;
13: class CSudoku
14: {
15: int map[9][9],lastmap[9][9];
16: int smod;
17: int solves;
18: int check(int,int,int*);
19: void dfs();
20: public:
21: enum{ANY=0,ALL=1};
22: CSudoku(int n=40);// 随机生成数独,n越大越难
23: CSudoku(int *data);// 人工指定数独
24: virtual ~CSudoku();
25: void display();// 显示数独
26: void Sdisplay();// 显示数独
27: int resolve(int mod=ALL);// 解数独
28: };
29: long sand=0;
30:
31:
32: CSudoku::CSudoku(int n)
33: {
34: int i,j;
35: sand++;
36: srand(time(&sand));
37: do
38: {
39: for(i=0;i<9;++i)
40: {
41: for(j=0;j<9;++j)
42: map[i][j]=0;
43: j=rand()%9;
44: map[i][j]=i+1;
45: }
46: }
47: while(!resolve(ANY));
48:
49: // 挖窟窿
50: for(int k=0;k<n;)
51: {
52: i=rand()%81;
53: j=i%9;
54: i=i/9;
55: if(map[i][j]>0)
56: {
57: map[i][j]=0;
58: ++k;
59: }
60:
61: }
62: //printf("(randomized sudoku created with %d blanks.)\n",blanks);
63: }
64: CSudoku::CSudoku(int *data)
65: {
66: int *pm=(int*)map;
67: for(int i=0;i<81;++i)
68: pm[i]=data[i];
69: }
70: CSudoku::~CSudoku()
71: {
72: return;
73: }
74: void CSudoku::display()
75: {
76: ostringstream osst;
77: osst.str("");
78: osst<<"<string>";
79: for(int i=0;i<9;++i)
80: {
81: for(int j=0;j<9;++j)
82: {
83: // if(map[i][j]>0)
84: // printf("< %d > ",map[i][j]);
85: // else
86: // printf("[ ] ");
87:
88: osst<<map[i][j];
89: }
90: // printf("\n");
91: }
92: osst<<"</string>\n";
93: oss<<osst.str();
94: }
95: int same = 1;
96: void CSudoku::Sdisplay()
97: {
98: ostringstream osst;
99: osst.str("");
100: osst<<"<string>";
101: for(int i=0;i<9;++i)
102: {
103: for(int j=0;j<9;++j)
104: {
105: if (map[i][j]!=lastmap[i][j]) {
106: same = 0;
107: // oss<<"err!!!-------------------------------"<<same;
108: // return;
109: }
110: }
111: }
112: if (same) {
113: return;
114: }
115: for(int i=0;i<9;++i)
116: {
117: for(int j=0;j<9;++j)
118: {
119: // if(map[i][j]>0)
120: // printf("< %d > ",map[i][j]);
121: // else
122: // printf("[ ] ");
123: lastmap[i][j] = map[i][j];
124: osst<<map[i][j];
125:
126: }
127: // printf("\n");
128: }
129: osst<<"</string>\n";
130: oss<<osst.str();
131: }
132: int CSudoku::resolve(int mod)
133: {
134: smod=mod;
135: if(mod==ALL)
136: {
137: solves=0;
138: dfs();
139: return solves;
140: }
141: else if(mod==ANY)
142: {
143: try
144: {
145: dfs();
146: return 0;
147: }
148: catch(int)
149: {
150: return 1;
151: }
152: }
153: return 0;
154: }
155: int CSudoku::check(int y,int x,int *mark)
156: {
157: int i,j,is,js,count=0;
158: for(i=1;i<=9;++i)
159: mark[i]=0;
160: for(i=0;i<9;++i)
161: mark[map[y][i]]=1;
162: for(i=0;i<9;++i)
163: mark[map[i][x]]=1;
164: is=y/3*3;
165: js=x/3*3;
166: for(i=0;i<3;++i)
167: {
168: for(j=0;j<3;++j)
169: mark[map[is+i][js+j]]=1;
170: }
171: for(i=1;i<=9;++i)
172: if(mark[i]==0)
173: count++;
174: return count;
175: }
176: int toomanys = 0; int blanks = 40;
177: void CSudoku::dfs()
178: {
179: int i,j,im=-1,jm,min=10;
180: int mark[10];
181: for(i=0;i<9;++i)
182: {
183: for(j=0;j<9;++j)
184: {
185: if(map[i][j])
186: continue;
187: int c=check(i,j,mark);
188: if(c==0)
189: return;
190: if(c<min)
191: {
192: im=i;
193: jm=j;
194: min=c;
195: }
196: }
197: }
198: if(im==-1)
199: {
200: if(smod==ALL)
201: {
202: ++solves;
203: // printf("No. %d:\n",++solves);
204: if (solves>(2)) {
205: toomanys = 1;
206: return;
207: }
208: Sdisplay();
209: return;
210: }
211: else if(smod==ANY)
212: {
213: throw(1);
214: }
215: }
216: check(im,jm,mark);
217: for(i=1;i<=9;++i)
218: {
219: if(mark[i]==0)
220: {
221: map[im][jm]=i;
222: dfs();
223: }
224: }
225: map[im][jm]=0;
226: }
227:
228: int main()
229: {
230: int data1[]=
231: {4,9,0,0,0,6,0,2,7,
232: 5,0,0,0,1,0,0,0,4,
233: 6,0,0,0,0,8,0,0,3,
234: 1,0,4,0,0,0,0,0,0,
235: 0,6,0,0,0,0,0,5,0,
236: 0,0,0,0,0,0,2,0,8,
237: 7,0,0,2,0,0,0,0,5,
238: 8,0,0,0,9,0,0,0,1,
239: 3,4,0,5,0,0,0,6,2
240: };
241: int data2[]=
242: {7,4,0,0,8,0,0,1,6,
243: 9,0,0,0,3,5,0,0,4,
244: 0,0,0,7,0,0,0,0,0,
245: 0,7,0,0,0,9,5,0,0,
246: 6,1,0,0,5,0,0,8,7,
247: 0,0,2,6,0,0,0,4,0,
248: 0,0,0,0,0,4,0,0,0,
249: 3,0,0,5,6,0,0,0,2,
250: 5,6,0,0,1,0,0,3,9
251: };
252: // cout<<"begin";
253: // std::ofstream logFile("out.plist");
254: // std::streambuf *outbuf = std::cout.rdbuf(logFile.rdbuf());
255: //<dict>
256: //<key>p</key>
257: //<string></string>
258: //<key>s</key>
259: //<array>
260: //<string>12</string>
261: //<string>32</string>
262: //</array>
263: //</dict>
264: cout<<"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<!DOCTYPE plist PUBLIC \"-//Apple//DTD PLIST 1.0//EN\"\"http://www.apple.com/DTDs/PropertyList-1.0.dtd\">\n<plist version=\"1.0\">\n<dict>";
265: int num = 0;
266: // int normalEnd = 1;
267: while (blanks<60) {
268: // <key>D20</key>
269: // <array>
270: coutt<<"<key>D"<<blanks<<"</key>"<<endl<<"<array>"<<endl;
271: // result =
272: int inNum = 0;
273:
274: for (int ii = 0; ii<100; ++ii) {
275: // cout<<num<<"d"<<blanks<<endl;
276: // normalEnd = 1;
277: same = 1;toomanys = 0;
278: oss<<"<dict>"<<endl<<"<key>p</key>"<<endl;
279: // cin>>blanks;
280:
281: CSudoku s(blanks);
282: s.display();
283: // cout<<"开始解数独:"<<endl;
284: oss<<"<key>s</key>"<<endl<<"<array>"<<endl;
285: //
286: s.resolve();
287: oss<<"</array>"<<endl<<"</dict>"<<endl;
288: // sleep(1);
289: // usleep(15000);
290: if (same){//||toomanys) {
291: // cout<<"err!!!!====------";
292: oss.str("");
293: // normalEnd = 0;
294: continue;
295: }else{
296: coutt<<oss.str();
297: oss.str("");
298: ++num;++inNum;
299: // normalEnd = 1;
300: }
301: if (inNum>20) {
302: break;
303: }
304: }
305:
306:
307:
308: // </array>
309: // if (normalEnd == 1) {
310: coutt<<"</array>"<<endl;
311: if (inNum ) {
312: cout<<coutt.str();
313: }
314: coutt.str("");
315: // cout<<oss.str();
316: oss.str("");
317: // }
318:
319:
320: blanks+=1;
321: // ++num;
322:
323:
324: // if (num>5000) {
325: // break;
326: // }
327:
328:
329:
330: }
331:
332:
333:
334: cout<<"</dict>\n</plist>\n";
335: // std::cout.rdbuf(outbuf);
336:
337: // cout<<"done";
338: return 0;
339: }
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
