iOS开发 Swift开发数独游戏(二)数独题目的生成

一、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:  }

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。