数独

一、游戏规则介绍：

数独是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复。

生成数独的算法思想：回溯法，递归实现深度优先搜索

函数简介：

void randomFirstRow(char a0[], int n) /*随机生成第一行*/
int Digit(char a[][COL], int i, int j)/*递归填充一个数字*/
void createSudoku(char a[][COL])/*封装后的数独生成函数*/
void createStartinggrid(const char a[][COL], char b[][COL], int numDigits)/*随机生成初盘*/
int checkSudoku(const char a[][COL])/*按规则检查函数*/
void printToFile(const char a[][COL], const char filename[])/*打印数独数组到文件*/
void createSudokuToFile(void)/*批量生成数独初盘到文件中*/

主要变量：

#define MAXNUM 1000 /*数独游戏个数*/

#define SEED 20171212 /*用于随机数生成的种子*/

解决数独问题的算法思想：与生成数独一致。

函数简介：

const char filename[])/*从一个文件中读取数独*/

int j)/*递归解决数独*/

char b[][COL])/*封装后的解数独函数*/

主函数负责遍历读取sudoku目录中的全部数独初盘，调用解数独函数，并计算时间，检查解的正确性，如果出错立刻输出错误提示并结束程序。最后输出求解全部数独问题花费的时间。

主要变量：

#define MAXNUM 1000 /*数独游戏个数，初始阶段可以设置成100，即只做前100道题*/

内容与模拟学生端程序基本一致，主要做了以下修改：

删除readFromFile函数的函数体，考察学生的文件读写能力；
删除Solve函数；
删除solveSudoku函数的函数体。其中：
1. 参数const char a[][COL]表示初盘二维数组；
2. 参数char b[][COL]表示解的二维数组。

老师利用sudokuGenerate.cpp生成包含1000道数独问题的sudoku文件夹；
将sudoku文件夹和sudokuStudentEnd_toBeSolved.cpp发布给学生（sudoku文件夹和sudokuStudentEnd_toBeSolved.cpp必须在同一目录下）；
学生需要补充readFromFile函数和Solve函数，完成1000道数独问题的求解。
并且，程序的运行时间必须低于模拟学生端程序的时间（200s以内）。

程序运行效果图

注：生成的数独会以TXT文件格式保存，解算数独的时候需要从txt文件中读取数据。

如果对您有帮助