问题描述：数独是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个九宫格内的数字均含1-9，不重复

要求：设计算法随机生成不同难度的数独游戏，阐述如何评价所生成数独的难度。

数独简介:数独(Sudoku)是一种当前非常流行的填数游戏，但与数字的运算毫无关系，主要考察人们的逻辑推理能力和观察能力。数独起源于拉丁方阵，由单元格(Cell)、行(Row)、列(Column)、宫(Box、Block)等元素组成，规则是在每行、每列、每宫的九个单元格中填入数字1-9，不重复。给定一定数量提示数的盘面作为初始条件，称为初盘。根据规则将所有单元格填满得到的盘面称为终盘，也就是数独的解。标准的数独初盘只能对应一个终盘。

设计思路：

对于数独程序，主要需要解决两个问题：数独生成、数独求解。目前影响比较大，功能比较完善的数独程序有：Hodoku、Sudoku Explainer。

要实现数独的生成，就要先理清每一个位置的约束条件，经我们小组讨论发现，每个位置的数需要满足四个约束条件：

首先，这个格子里不能有数字，即为空

其次，同一行不能有相同数字

再次，同一列不能有相同数字

最后，同一个九宫格不能有相同数字

用算法的形式把这四个约束条件表现出来，就是数独的生成。

采用随机方式生成数独，即从空白的数独盘面开始随机填数，填入的数字不能违背数独的基本规则，并且要保证解的唯一性。在随机填入过程中，判断某个位置是否可以填入一个随机的数是根据这一位置所处行列宫区域中是否已有此数来决定。当填入这一数之后，修改它所处区域的标记信息。当生成一个完整的数独时，在按照下标随机将数独里面的数进行置零操作，就生成了一个数独的问题，然后再进行数独求解，发现是多解数独时，随机选取两个解，在他们的差异位置处随机选择一个填入，再进行求解，这样可以快速定位到当前搜索路径的某个有效分枝，这样反复进行，可根据当前搜索路径，快速定位到最后一个分枝，找到解是唯一的初盘。

计算机程序求解数独，一般采用回溯法，对于任意数独初盘，好的算法都可以在一秒内得到解。目前，非常有效的算法，是舞蹈链(Dancing Links)算法。它实际上也是一种回溯算法，巧妙地运用了双向十字链表的数据结构，用空间换取时间，将数独求解转化为一个精确覆盖问题，用C语言实现的算法，在普通的微机上，能够在0.1ms左右对任意标准数独进行求解。

算法设计：

数独求解：

首先，要先确定该数独中空格的数量以及位置，用count记录空格的数量即所需填的数量，用blank数组记录所有需要填的空格的坐标。

int count = 0; //count用于记录需要填的空格数量，初始为0int blank[81][2]; //blank数组用于记录所有需要填的空格的坐标 for(int i = 0;i < 9;i++) for(int j = 0;j < 9;j++) if(sd[i][j] == 0) {//将整个数独扫描一遍，blank[count][0]=i; blank[count][1]=j;count++; //统计其中的空格数量}

然后根据blank数组记录的sd数组里面空格的下标位置来进行试填，试填时要满足同行、同列以及同块不出现相同的数字，利用一个循环，将sd里面原来的空格里面的数字先进行加一然后进行循环，如果满足了条件，就将该数字填入sd数组里面，作为改下标的一个解，并且将top加一。但是因为第一次填数的时候不一定就是正确的数，所以当出现错误是，就会运用top进行回溯到上一步的操作。直到完全将整个数独游戏解决。但是如果数独问题没有正确的答案的话，top会小于0，最后输出“您的数独问题有错误，请输入正确的数度问题。”

int a = blank[top][0]; //如果执行到这里，说明还有空格要填， int b = blank[top][1]; //用a，b记录下top指向的元素作为当前试填空格的坐标int n = sd[a][b]; //用n记录当前空格中的数字，这个数字作为试填的“进度”，从这个数字加1往下试填for(n++;n <= 9;n++)//将n加1后，一直循环到9进行试填{int ok = 1; //ok=1标志当前数字可行for(int k = 0;k < 9;k++) //检测同行，同列，同块的数字是否有相同的{if(sd[a][k] == n || sd[k][b]== n || sd[(a / 3) * 3 + k / 3][(b/ 3) * 3 + k % 3] == n ) //同行，同列，同块的数字一起检测{ok = 0; //如果同行，同列，同块某一处有相同数字，则ok=0，表示当前数字不可行break; //不再往下检测，跳出此层循环，继续试下一个数字}}if(ok) break; //如果ok保持为1，说明当前数字可行（否则肯定会被修改为0），跳出循环，不再往下试}if(n <= 9) // 如果有一个数字可行，n<=9。否则，n=10 {sd[a][b] = n; //将这个数字填入空格中top++; //top加1，处理下一个空格}if(n > 9) //如果试到9都不行的话，循环结束后n的值为10，此时要回退 {sd[a][b] = 0; //回退时先将当前空格中数字改为0，相当于清零top--; //回退1步}}printf("\n您的数独问题具有错误，请输入正确的数独问题\n");}

第三步，因为每填一个数，top就会进行加一的操作，然后一共有count个数需要填，所以当top等于count时，输出最终的结果。

if(top == count) //因为每填完一个空格后top加1，填最后一个空格时top==count-1，填完后top加1即等于count{printf("最终结果为：\n");for(int s = 0;s < 9;s++) {for(int t=0;t<9;t++){ printf("%d ",sd[s][t]); // 输出一个解}printf("\n"); }}

最后，将一个不完整的数独代入进行测验。

int main(void){int sd[9][9] = { // “世界最难数独”信息 8,0,0,0,0,0,0,0,0,0,0,3,6,0,0,0,7,0,0,7,0,0,9,0,2,0,0,0,5,0,0,0,7,0,0,0,0,0,0,0,4,5,7,0,0,0,0,0,1,0,0,0,3,0,0,0,1,0,0,0,0,6,8,0,0,8,5,0,0,0,1,0,0,9,0,0,0,0,4,0,0,};fill(sd); //调用函数求解return 0;}