摘要：花了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 ;
}