摘要：花了1周多时间学习了C语言，开始练手写解数独游戏的程序。

C语言学习 数独游戏

作者：乌龙哈里
时间：2015-11-22
平台：Window7 64bit,TCC 0.9.26(x86-64 Win64)

参考：

• 互动百科 数独

章节：

正文：

原来也用C#和Go语言写过，主要思路是暴力撞大运破解。思路什么的在程序了都注释了，不多说了。可能是没用什么先进的算法，感觉C解题速度和C#差不多（除了C#第一次运行之外），基本上出来一个数独表都不用1秒。

附完整程序：

 /***************************************************

 *数独表

 *作者：乌龙哈里

 *编写时间：2015-11-21

 *修改时间：2015-11-22

 *思路：

 1、每个表元素结构属性有：

    值Value，回溯标志IsBack，可选值数量Remain,可选值数组Selection[9];

 2、根据规则，把数独表看成27个，每个含有9个元素的行列块组；

    为了循环方便，分成：0-8:行组，9-17：列组，18-26：块组；

 3、找出最少要填空格的行列块组,开始填写。填完这个再找下个最少的；

 4、填写时先从行列块组中挑出剩下可填写的数字，从中随机找个值；

 5、没有可选的时候，开始从回溯表中回到上一步，

    回溯时如果可选值数量大于1时，则抛弃先前所填值，用另外的

    值来尝试。

 ****************************************************/

 #include <stdio.h>

 #include <stdlib.h>

 /*

 *把表看成27组，每组9个元素，

 *    0-8:行组，9-17：列组，18-26：块组

     行内序号：从左到右 012345678

     列内序号：从上到下 012345678

     块内序号：012

               345

               678

 *GetRcb():根据index计算出行列块

 *参数：index: 序号 0-81,flag:0-2,0-行,1-列，2-块

 *

 *GetNum():根据行列块组rcb和块内序号index计算出在数独表中的序号

 */

 int GetRcb(int index,int flag){

     int result=-;

     switch(flag){

         case :

             result=index / ;

             break;

         case :

             result=index % +;

             break;

         case :

             result=index//*+index%/+;

             break;

     }

     return result;

 }

 int GetNum(int rcb,int index){

     int result=-;

     int flag=rcb/;

     switch(flag){

         case :

             result=rcb*+index;

             break;

         case :

             result=rcb-+index*;

             break;

         case :

             result=(rcb-)/*+(rcb-)%*+index/*+index%;

             break;

     }

     return result;

 }

 //定义：数独表、表内元素结构、回溯表,回溯只记录30步

 typedef signed char byte;

 typedef char bool;

 #define true 1

 #define false 0

 byte SudokuTable[]={};

 #define STEP 30

 int RecallTable[STEP]={-};

 typedef struct element{

     byte Value;

     bool IsBack;

     byte Remain;

     byte Selection[];

 }Sudoku;

 Sudoku *sdk;

 /*

 初始化数独元素:

 */

 void InitSudoku(void){

     sdk=(Sudoku*)malloc(*sizeof(Sudoku));

     for(int i=;i<;i++){

         sdk[i].Value=SudokuTable[i];

         sdk[i].IsBack=false;

         sdk[i].Remain=;

     }

 }

 //查找最少空的行列块,用意：从这个开始填空

 int GetFirstRcb(void){

     int result=;

     int lessNum=;

     int n;

     for(int i=;i<;i++){

         n=;

         for (int j=;j<;j++){

             if(sdk[GetNum(i,j)].Value>){

                 n--;

             }

         }

         if(n> && n<lessNum){

             result=i;

             lessNum=n;

         }

     }

     return result;

 }

 //整理可选值数组，把0值丢后面，可选值放前面，返回可选数

 byte Arrange(int index){

     byte result=;

     for(int i=;i<;i++){

         if(sdk[index].Selection[i]>){

             sdk[index].Selection[result]=sdk[index].Selection[i];

             if(i!=result){sdk[index].Selection[i]=;}

             result++;

         }

     }

     return result;

 }

 /*

 *设置可填写数字数组：

 遍历元素所属的行列块中元素，在Selection数组中把用过的值设成0；

 */

 void SetSelection(int index){

     for(int i=;i<;i++){sdk[index].Selection[i]=i+;}

     int rcb;

     int n;

     for(int i=;i<;i++){

         rcb=GetRcb(index,i);

         for(int j=;j<;j++){

             n=GetNum(rcb,j);

             if(sdk[n].Value>){

                 sdk[index].Selection[sdk[n].Value-]=;

             }

         }

     }

     sdk[index].Remain=Arrange(index);

 }

 //随机选出可填写值

 byte GetValue(int index){

     byte result=;

     srand((unsigned int)time());

     int n=rand()%sdk[index].Remain;

     result=sdk[index].Selection[n];

     sdk[index].Selection[n]=;

     sdk[index].Remain=Arrange(index);

     return result;

 }

 /*

 回溯，如果回溯表内没有记录，返回-1

 如果可选值数量大于0的，则把回溯标记设成true

 */

 int Recall(void){

     int index;

     for(int i=;i<STEP;i++){

         if(RecallTable[i]>-){

             index=RecallTable[i];

             sdk[index].Value=;

             RecallTable[i]=-;

             if(sdk[index].Remain==){

                 sdk[index].IsBack=false;

             }

             else{

                 sdk[index].IsBack=true;

                 return index;

             }

         }

     }

     return -;

 }

 /*

 填写回溯表

 从后往前填写，满了就移动

 */

 void WriteRecallTable(int index){

     if(RecallTable[]>-){

         for(int i=STEP-;i>;i--){

             RecallTable[i]=RecallTable[i-];

         }

         RecallTable[]=index;

     }

     else{

         for(int i=;i<STEP;i++){

             if(RecallTable[i]>-){

                 RecallTable[i-]=index;

                 break;

             }

         }

     }

 }

 /*

 根据行列块分组来填写元素。

 如果是回溯回来的，则抛弃掉现有的值，即不SetSelection()，

 因为GetValue()选出值后会把所填写的值从可选值数组中除去，

 而SetSelection()是根据所有行列块组的元素值选出剩下的可填值，

 包括了上次行不通的值。

 */

 bool WriteRcb(int rcb){

     int index;

     for(int i=;i<;i++){

         index=GetNum(rcb,i);

         if(sdk[index].Value==){

             if(sdk[index].IsBack==false){

                 SetSelection(index);

             }

             if (sdk[index].Remain==){

                 return false;

             }

             sdk[index].Value=GetValue(index);

             sdk[index].IsBack=true;

             WriteRecallTable(index);

         }

     }

     return true;

 }

 //判断填完没有

 bool Completed(void){

     for(int i=;i>-;i--){

         if(sdk[i].Value==) {

             return false;

         }

     }

     return true;

 }

 //填写全表

 void FillTable(void){

     int loop=;

     int firstRcb=GetFirstRcb();

     while(loop> && Completed()==false){

         if(WriteRcb(firstRcb)==false){

             if(Recall()==-){

                 printf("Unlucky,cannot solve!\n");

                 break;

             }

         }

         firstRcb=GetFirstRcb();

         loop--;

     }

 }

 /*************************************

 *各种输出显示模块

 **************************************/

 // //按行列块分组显示元素序号

 // void DisplayRcb(void){

 //     for (int i = 0; i <27;i++){

 //         if(i%9==0){printf("\n");}

 //         printf("%2d: ", i%9);

 //         for (int j = 0; j <9; j++){

 //             printf("%2d ",GetNum(i,j));

 //         }

 //         printf("\n");

 //     }

 // }

 //显示所有数独表元素

 void Display(void){

     for(int i=;i<;i++){

         if(i== || i==){

             printf("------+------+------\n");

         }

         for(int j=;j<;j++){

             if(j== || j==){ printf("|");}

             printf("%2d",sdk[i*+j].Value);

         }

         printf("\n");

     }

 }

 // //显示元素可选数字

 // void DisplayRemain(int index){

 //     printf("element %d remain %d selecttion: ",index,sdk[index].Remain);

 //     for(int i=0;i<9;i++){

 //         printf("%d ",sdk[index].Selection[i]);

 //     }

 //     printf("\n");

 // }

 /********************************

 *Main

 *********************************/

 int main(void){

     InitSudoku();

     FillTable();

     Display();

     free(sdk);

     return ;

 }