在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
一、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: }
三、将输出转向到文件
这个程序默认是输出到屏幕上,我想直接输出成文件。首先要定位到xcode项目中的可执行文件,如图,右键Show In Finder,找到所在的目录。接着打开Terminal,cd到那个目录,输入“./sudokuG > sudokuR.plist”终端会在该目录下生成一个新的 sudokuR.plist文件。拷贝到桌面,以供后续使用。注:如果等待时间太长请减小267行的那个条件。Terminal执行过程中按Ctrl+C可以中途终止。 |
请发表评论