Github项目地址

https://github.com/JackManTvO/sudoku

PSP表格

解题思路

生成数独终局

  数独的要求是在9×9的格子内，每一行和每一列和每一宫内都包含不重复的九个元素，但数独终局的个数共有6,670,903,752,021,072,936,960（6.67×10²¹）种组合，尽管终局要求左上角第一个数字为固定值，其终局的种数也是巨大的。而程序设计对终局数量的需求仅在1,000,000个以内，因此，没有必要穷举找到前1,000,000种终局，而没有合适的生成策略随机生成则可能造成终局的重复。因此需制定合适的生成终局策略，而我的生成终局策略为对固定的终局模板进行数字交换以及行交换。这种策略共可以生成8!（除首数字外8个数字两两交换）×2（23行交换）×6（4～6行两两交换）×6（7～9行两两交换）=2,903,040种终局，大于要求的终局数。根据要求生成的终局个数对变换方式进行深度优先搜索，第一层为数字交换，第二层为23行交换，第三层为4～6行交换，第四层为7～9行交换，以快速地遍历第四层的叶子，以生成多个不重复的终局。
  具体步骤如下：

1. 生成一固定的有效终局作为模板。
2. 对模板进行数字交换。
3. 对进行数字交换后的终局进行行交换（2～3行交换、4～6行交换、7～9行交换）保证宫内不重复。
4. 若生成终局数满足程序要求个数即返回，若不满足，重复进行步骤2、步骤3。

求解数独谜题

  对于给定的数独谜题，按要求补充数独的空缺，以完成数独。因为填入的数需要满足数独的要求，所以每个固定位置的数值是有限制的，在剩余的可行值中选择一个填入空白，接着填入下一个空白。若发现无可行解，则父节点选择错误，采用回溯法，返回上一节点，填入另一可行解。直到生成树的层数等于空缺数，则生成一可行的数独终局，求解数独谜题成功。
  具体步骤如下：

1. 扫描题目，将空白值坐标取出存入数组A。
2. 在数组A中选择下一个坐标。
3. 查询其所在行、列、宫的数值，填入可行解数组，在可行解数组中选取下一可行解填入。
4. 若填入成功，则返回步骤2，若无可行解，则在数组A中返回上一坐标，返回步骤3填入另一可行解。若A中无剩余，则返回，求解数独成功。

设计实现过程

类

  我设计了三个类，分别为向量类、点类和数独类（改进前）

Seed类（改进前）

Point类（改进前）

Sudoku类（改进前）

类图（改进后）

Class Diagram.png

关键函数

元素交换函数

permutate.png

行交换函数

generate.png

解数独函数

dfs.png

单元测试设计

  使用了代码走读，并对三个关键函数使用路径测试法进行了单元测试：

元素交换函数

行交换函数

解数独函数

改进

终局生成

  设置参数需要的棋盘数量为1,000,000，对该改进前代码进行了10次性能分析，平均时间为138.251秒，最接近平均时间的一次为138.708秒。

性能1.png

  由性能分析可见，消耗最大的函数是Sudoku类的写文件函数中的fputc函数，为了方便添加空格，我采用的是fputc函数逐个添加字符，且运行write函数后就关闭文件。这样在1,000,000个终局生成中，会发生反复调用fputc函数和打开、关闭文件函数。因此我改动为在开始生成终局时打开文件，在写入完成后关闭文件，将字符连接为字符串后，将一整个数独终局以字符串写入文件。且Point类的封装性不强，我加强了Point类的封装性（见类图）。改进前在行交换时，回溯时需要置为交换前，浪费大量时间，我在行变换前，将数独终局作为新变量保存以作为模板，方便进行二次行交换。
  改进后10次性能分析的平均时间为5.137秒，最接近平均时间的一次为5.368秒。

性能2.png

数独求解

  为了方便进行数独求解，我添加了Pset类已保存空白点（见类图），且封装性良好。为了优化性能，我采用了随机的策略选取下一空白点的解，并记录空白点处理的顺序以方便回溯。这个算法的时间复杂度明显优于全图遍历。且为了减少数据的冗余，在读入数独时完成空白点集的添加。

代码说明

元素交换函数

void Sudoku::permutate (int level) {
    if (level == side - 2) {        //全排列结束
        mod ();     //生成模板
        generate ();        //行交换
        return;
    }
    for (int i = level; i < side; i++) {
        if (i != level)
            seed.swapi (level, i);      //交换元素
        permutate (level + 1);      //递归
        if (nsudoku == 0)
            return;
        if (i != level)
            seed.swapi (level, i);
    }
    return;
}

行交换函数

void Sudoku::generate () {      //生成终局
        /*行变换*/
    Sudoku ans;
    for (int i = 0; i < 2 && nsudoku>0; i++)        //第一阶段
        for (int j = 0; j < 6 && nsudoku>0; j++)        //第二阶段
            for (int k = 0; k < 6 && nsudoku>0; k++) {      //第三阶段
                ans.cpy(this);
                switch (i) {
                case 0:
                    break;
                case 1:
                    ans.swapRow (1, 2); break;
                }
                switch (j) {
                case 0:
                    break;
                case 1:
                    ans.swapRow (4, 5); break;
                case 2:
                    ans.swapRow (3, 4); break;
                case 3:
                    ans.swapRow (3, 5); ans.swapRow (3, 4); break;
                case 4:
                    ans.swapRow (3, 4); ans.swapRow (3, 5); break;
                case 5:
                    ans.swapRow (3, 5); break;
                }
                switch (k) {
                case 0:
                    break;
                case 1:
                    ans.swapRow (7, 8); break;
                case 2:
                    ans.swapRow (6, 7); break;
                case 3:
                    ans.swapRow (6, 8); ans.swapRow (6, 7); break;
                case 4:
                    ans.swapRow (6, 7); ans.swapRow (6, 8); break;
                case 5:
                    ans.swapRow (6, 8); break;
                }
                ans.write (fpw);
                nsudoku--;      //生成数+1
                if (nsudoku == 0) {
                    if (fpw != NULL)
                        fclose (fpw);
                    return;
                }
                if (fpw != NULL)
                    fprintf (fpw, "\n\n");
            }
    return;
}

解数独函数

int Sudoku::dfs () {
    int iz = pset.geti();
    Point p (this->pset.getVal(iz));
    /*初始化占有标识数组*/
    for (int i = 0; i < 9; i++) {
        if (val[p.getx ()][i] != 0 && p.getpos (val[p.getx ()][i]) == 0)
            p.setpos (val[p.getx ()][i], 1);
        if (val[i][p.gety ()] != 0 && p.getpos (val[p.getx ()][i]) == 0)
            p.setpos (val[i][p.gety ()], 1);
    }
    for (int i = (p.getx () / 3) * 3; i < (p.getx () / 3) * 3 + 3; i++)
        for (int j = (p.gety () / 3) * 3; j < (p.gety () / 3) * 3 + 3; j++)
            if (val[i][j] != 0 && p.getpos (val[p.getx ()][i]) == 0)
                p.setpos (val[i][j], 1);
    /*寻找可行解*/
    int found = 0;
    for (int i = 1; i < 10; i++)
        if (p.getpos(i) == 0) {     //找到一可行解
            found = 1;
            val[p.getx ()][p.gety ()] = i;
            p.setpos (i, 1);
            pset.del (iz);
            if (pset.isEmpty()) {
                write (fpw);
                return 1;
            }
            if (dfs ())     //找下一个空位的可行解
                return 1;
            p.setpos (i, 0);
        }
    return 0;
}

附加题