C语言学习 数独游戏

1 /***************************************************   2 *数独表   3 *作者：乌龙哈里     4 *编写时间：2015-11-21   5 *修改时间：2015-11-22   6 *思路：   7 1、每个表元素结构属性有：   8    值Value，回溯标志IsBack，可选值数量Remain,可选值数组Selection[9];   9 2、根据规则，把数独表看成27个，每个含有9个元素的行列块组；  10    为了循环方便，分成：0-8:行组，9-17：列组，18-26：块组；  11 3、找出最少要填空格的行列块组,开始填写。填完这个再找下个最少的；  12 4、填写时先从行列块组中挑出剩下可填写的数字，从中随机找个值；  13 5、没有可选的时候，开始从回溯表中回到上一步，  14    回溯时如果可选值数量大于1时，则抛弃先前所填值，用另外的  15    值来尝试。  16 ****************************************************/  17   18 #include <stdio.h>  19 #include <stdlib.h>  20   21 /*  22 *把表看成27组，每组9个元素，  23 *    0-8:行组，9-17：列组，18-26：块组  24     行内序号：从左到右 012345678  25     列内序号：从上到下 012345678  26     块内序号：012  27               345  28               678  29 *GetRcb():根据index计算出行列块  30 *参数：index: 序号 0-81,flag:0-2,0-行,1-列，2-块  31 *  32 *GetNum():根据行列块组rcb和块内序号index计算出在数独表中的序号  33 */  34 int GetRcb(int index,int flag){  35     int result=-1;  36     switch(flag){  37         case 0:  38             result=index / 9;  39             break;  40         case 1:  41             result=index % 9+9;  42             break;  43         case 2:  44             result=index/9/3*3+index%9/3+18;  45             break;  46     }  47     return result;  48 }  49   50 int GetNum(int rcb,int index){  51     int result=-1;  52     int flag=rcb/9;  53     switch(flag){  54         case 0:  55             result=rcb*9+index;  56             break;  57         case 1:  58             result=rcb-9+index*9;  59             break;  60         case 2:  61             result=(rcb-18)/3*27+(rcb-18)%3*3+index/3*9+index%3;  62             break;  63     }  64     return result;  65 }  66   67 //定义：数独表、表内元素结构、回溯表,回溯只记录30步  68 typedef signed char byte;  69 typedef char bool;  70   71 #define true 1  72 #define false 0  73   74 byte SudokuTable[81]={0};  75   76 #define STEP 30  77 int RecallTable[STEP]={-1};  78   79 typedef struct element{  80     byte Value;  81     bool IsBack;  82     byte Remain;  83     byte Selection[9];  84 }Sudoku;  85   86 Sudoku *sdk;  87   88 /*  89 初始化数独元素:  90 */  91 void InitSudoku(void){  92     sdk=(Sudoku*)malloc(81*sizeof(Sudoku));  93     for(int i=0;i<81;i++){  94         sdk[i].Value=SudokuTable[i];  95         sdk[i].IsBack=false;  96         sdk[i].Remain=9;  97     }  98 }  99  100 //查找最少空的行列块,用意：从这个开始填空 101 int GetFirstRcb(void){ 102     int result=0; 103     int lessNum=9; 104     int n; 105     for(int i=0;i<27;i++){ 106         n=9; 107         for (int j=0;j<9;j++){ 108             if(sdk[GetNum(i,j)].Value>0){ 109                 n--; 110             } 111         } 112         if(n>0 && n<lessNum){ 113             result=i; 114             lessNum=n; 115         } 116     } 117     return result; 118 } 119  120 //整理可选值数组，把0值丢后面，可选值放前面，返回可选数 121 byte Arrange(int index){ 122     byte result=0; 123     for(int i=0;i<9;i++){ 124         if(sdk[index].Selection[i]>0){ 125             sdk[index].Selection[result]=sdk[index].Selection[i]; 126             if(i!=result){sdk[index].Selection[i]=0;} 127             result++; 128         } 129     } 130     return result; 131 } 132 /* 133 *设置可填写数字数组： 134 遍历元素所属的行列块中元素，在Selection数组中把用过的值设成0； 135 */ 136 void SetSelection(int index){ 137     for(int i=0;i<9;i++){sdk[index].Selection[i]=i+1;} 138     int rcb; 139     int n; 140     for(int i=0;i<3;i++){ 141         rcb=GetRcb(index,i); 142         for(int j=0;j<9;j++){ 143             n=GetNum(rcb,j); 144             if(sdk[n].Value>0){ 145                 sdk[index].Selection[sdk[n].Value-1]=0; 146             } 147         } 148     } 149     sdk[index].Remain=Arrange(index); 150 } 151  152 //随机选出可填写值 153 byte GetValue(int index){ 154     byte result=0; 155     srand((unsigned int)time(0)); 156     int n=rand()%sdk[index].Remain; 157     result=sdk[index].Selection[n]; 158     sdk[index].Selection[n]=0; 159     sdk[index].Remain=Arrange(index); 160     return result; 161 } 162  163 /* 164 回溯，如果回溯表内没有记录，返回-1 165 如果可选值数量大于0的，则把回溯标记设成true 166 */ 167 int Recall(void){ 168     int index; 169     for(int i=0;i<STEP;i++){ 170         if(RecallTable[i]>-1){ 171             index=RecallTable[i]; 172             sdk[index].Value=0; 173             RecallTable[i]=-1; 174             if(sdk[index].Remain==0){ 175                 sdk[index].IsBack=false; 176             } 177             else{ 178                 sdk[index].IsBack=true; 179                 return index; 180             } 181         } 182     } 183     return -1; 184 } 185 /* 186 填写回溯表 187 从后往前填写，满了就移动 188 */ 189 void WriteRecallTable(int index){ 190     if(RecallTable[0]>-1){ 191         for(int i=STEP-1;i>0;i--){ 192             RecallTable[i]=RecallTable[i-1]; 193         } 194         RecallTable[0]=index; 195     } 196     else{ 197         for(int i=0;i<STEP;i++){ 198             if(RecallTable[i]>-1){ 199                 RecallTable[i-1]=index; 200                 break; 201             } 202         } 203     } 204 } 205 /* 206 根据行列块分组来填写元素。 207 如果是回溯回来的，则抛弃掉现有的值，即不SetSelection()， 208 因为GetValue()选出值后会把所填写的值从可选值数组中除去， 209 而SetSelection()是根据所有行列块组的元素值选出剩下的可填值， 210 包括了上次行不通的值。 211 */ 212 bool WriteRcb(int rcb){ 213     int index; 214     for(int i=0;i<9;i++){ 215         index=GetNum(rcb,i); 216         if(sdk[index].Value==0){ 217             if(sdk[index].IsBack==false){ 218                 SetSelection(index); 219             } 220             if (sdk[index].Remain==0){ 221                 return false; 222             } 223             sdk[index].Value=GetValue(index); 224             sdk[index].IsBack=true;     225             WriteRecallTable(index); 226         } 227     } 228     return true; 229 } 230 //判断填完没有 231 bool Completed(void){ 232     for(int i=80;i>-1;i--){ 233         if(sdk[i].Value==0) { 234             return false; 235         } 236     } 237     return true; 238 } 239 //填写全表 240 void FillTable(void){ 241     int loop=1000; 242     int firstRcb=GetFirstRcb(); 243  244     while(loop>0 && Completed()==false){ 245         if(WriteRcb(firstRcb)==false){ 246             if(Recall()==-1){ 247                 printf("Unlucky,cannot solve!/n"); 248                 break; 249             } 250         } 251         firstRcb=GetFirstRcb(); 252         loop--; 253     } 254 } 255  256 /************************************* 257 *各种输出显示模块 258 **************************************/ 259 // //按行列块分组显示元素序号 260 // void DisplayRcb(void){ 261 //     for (int i = 0; i <27;i++){ 262 //         if(i%9==0){printf("/n");} 263 //         printf("%2d: ", i%9); 264 //         for (int j = 0; j <9; j++){ 265 //             printf("%2d ",GetNum(i,j)); 266 //         } 267 //         printf("/n"); 268 //     } 269 // } 270 //显示所有数独表元素 271 void Display(void){ 272     for(int i=0;i<9;i++){ 273         if(i==3 || i==6){ 274             printf("------+------+------/n"); 275         } 276         for(int j=0;j<9;j++){ 277             if(j==3 || j==6){ printf("|");} 278             printf("%2d",sdk[i*9+j].Value); 279         } 280         printf("/n"); 281     } 282 } 283 // //显示元素可选数字 284 // void DisplayRemain(int index){ 285 //     printf("element %d remain %d selecttion: ",index,sdk[index].Remain); 286 //     for(int i=0;i<9;i++){ 287 //         printf("%d ",sdk[index].Selection[i]); 288 //     } 289 //     printf("/n"); 290 // } 291  292 /******************************** 293 *Main 294 *********************************/ 295 int main(void){ 296     InitSudoku(); 297     FillTable(); 298     Display(); 299     free(sdk); 300     return 0; 301 }