项目地址：
https://github.com/zack-guo/Sudoku

PSP表格

解题思路

1. 首先该项目的目的为设计一个数独游戏，所以需要两个部分-创建初始数独盘&解数独。
2. 针对解数独的部分，首先我能想到的算法是回溯法，建立状态进行递归，到那时可以想象的是这样的方法效率有可能不是最大的。
3. 通过查找资料，发现求解数独大体分四种方法，也就是1）回溯法 2）随机搜索/优化算法 3）约束编程 4）完全覆盖。
4. 因为题目要求比较简单，所以先用回溯法作出整体的看看效果，我还学习了模拟退火的方法可以作为提升方法备用。
5. 创建数独
   经过查阅资料发现满足题目设置的条件创建数独的方法很简单，只需要经过初始终局的几种变化方法加上数字映射的方法就可以了。

设计思路

1. 创建终局
   1.1 创建一个最简单的数独终局，后面在它的基础上做变化。

最简单的数独终局生成

2. 求解数独
   2.1 回溯法
   2.2 模拟退火算法

/2019.1.5更新 设计文档

设计文档
系统需求
开发一个命令行程序，程序可以1.生成不重复的终局到一个文件当中2. 读取文件中的数独题目并将接替结果输出到文件当中。
流程：
输入命令行信息-》根据参数形成数独，输入到文件中
-〉根据参数解数独并输出到文件中

2.详细设计

2.1 生成树读
2.1.1 思路
建立变化列表（二维数组）
通过生成全排列的函数生成第一行数据
输出
根据变化列表平移，输出。

类：
sudoku类：
char[] sudo//数组保存棋盘
Int[] change_list //变化列表
Int Num//给生成的数独计数
——————————————
Void generator() //生成第一行
void output() // 输出到文件

Changelis类：
private:
int list[9];
public:
void change_list();
int get(int);
changelist();
—————————————-
-int list[9] //保存变化列表
—————————————-
+void change()//对列表进行分组全排列变化
+int get() //获得字符

generator流程：
进入循环
通过next_permutation()函数，生成下一个首行序列。
进入列表循环
调用output（）
num++；
if（num==要求数量 ）
Return；

/2019.1.9更新 设计文档

2.2 解数独

2.2.1 解题思路
首先想到的思路是从文件中读入数独盘，并初始化对象。用回溯法搜索整个数独盘，约束条件是在该行，该列以及所在的宫内没有重复的数字，边界条件即为棋盘是否已满。回溯完成后输入文件。
但是根据网上查阅到的相关资料，与同学讨论，我发现这一方法有点过于暴力，很有可能效率较差。所以我还是基于回溯这个基本方法，做了一点优化。在回溯时不是依次遍历整个数独棋盘，而是针对与每一个小的九宫格依次填入数字。次序采用数字的方法。在满足约束条件的情况下，依次针对每一个小的九宫格填入1，下一轮依次针对每一个小的九宫格填入2，以此类推，最终到填入了最后一个九宫格的9为止，生成终局。

2.2.2设计思路

类：

solve
————————————————————-
-int map[9][9]; //保存数独盘
-bool check_list[9][9];//每个宫的数字情况
-int i,j;//当前搜索的横纵坐标
-int current_map; //搜到的当前宫
-int current_num; //当前在搜的数字
-Int target_num;

———————————————————-
+backtrack(). //回溯法的递归函数
+bool check（）//在行，列，宫内是否满足条件
+bound（）还有没有剩余的空

/1.19日更新

经过设计实现后，我修改的类图如下：

image.png

v1版本

代码性能分析

image.png

改进

我主要针对代码中文件读写的部分进行改进。围绕fwrite（）函数的部分我过去都采用了一个字符一个字符的写入，这对代码的性能影响十分严重。因此我改变了数据结构，舍弃了c语言的文件读写，改用c++那一套方法。我新建了一个string类型的字符串superc，在过去的代码中有关于写入的部分我统统把他们接入了superc的尾巴，在所有数独终局生成完成以后，或者所有数独都解出来以后，我再将这个字符串一次行写入文件当中。

v2版

image.png

如上面的测试成果来看，我的改进效果显著，大约提升了70%的性能，总运行时间缩小到了54.584秒，是一个长足的进步。

代码说明

1. 回溯函数

int solve::backtrack(int n)
{
    if ((current_box == 9 && current_num == 9)||n>=target_num )
    {
        output();
        return 1;
    }
    //如果当前还没有填完
    while (1)
    {
        //正常循环
        if (current_box == 9)
        {
            current_box = 0;
            current_num++;
            if (current_num >= 10)
                return 0;
        }
        //当前的宫可以填数字
        if (check_list[current_box][current_num])
        {
            //对当前的宫进行循环
            for (int i = 0; i < 9; i++)
            {
                //if(current_box>9)
                //    printf("shit");
                int row = (current_box / 3) * 3 + i / 3;
                int column = (current_box % 3) * 3 + i % 3;
                if (map[row][column] == 0 && check(row, column) && check_list[current_box][current_num])
                {
                    map[row][column] = current_num;
                    check_list[current_box][current_num] = false;
                    current_box++;
                    //output();
                    if (backtrack(n + 1))
                        return 1;
                    current_num = map[row][column];
                    map[row][column] = 0;
                    current_box = (row / 3) * 3 + (column / 3);
                    check_list[current_box][current_num] = true;

                }
            }
            return 0;
        }
        else
        {
            current_box++;
            continue;
        }
    }
    return 0;
}

思路：如设计文档里描述的那样，首先一个完整数独盘读入map数组中，记录空格的数量。然后保存每一个宫的状态，记录哪些数字是可填的。然后依次由1-9，在按顺序的9个宫中尝试能否填入，如果可以就进入下一层解空间继续尝试，如果不行就回溯到上一层，尝试当前宫的下一格能否填写，
在这个函数中，我遇到了一点小坑，就是保存当前层的状态除了问题，导致回溯到原来的状态会出问题，修复这个bug花了不少时间。

2.改变序列

void changelist::change_list()//改变变化列表
{
    if (std::next_permutation(&list[1], &list[2]))
    {
        return;
    }
    if (std::next_permutation(&list[3], &list[5]))
    {
        return;
    }
    if (std::next_permutation(&list[6], &list[8]))
    {
        return;
    }
}

思路：这个函数被我放在changelist当中，如我在设计文档中描述的那样，生成数独实际上依靠的就是首行的全排列不断变化，我用几行代码解决了变化列表的变化方法，是整个程序中比较简洁，巧妙的部分。我充分利用了next_permutation()这个函数的返回机制，通过对{0，3，6，1，4，7，2，5，8}这个数列分三个部分吗的全排列，加上后续的输出部分，就可以达到要求数量的数独输出了。
3.输出数独函数

void sudoku::output(changelist l)
{
    //生成
    //list 样例 {0,3,6,1,4,7,2,5,8}
    //打开文件
    for (int i = 0; i < 9; ++i)
    {
        for (int j = l.get(i); j < 9; ++j)
        {
            if (j != l.get(i))
            {
                //fwrite(" ", sizeof(char), 1, fp);
                //strcat(superchar, " ");
                superc += " ";
            }
                
            //fwrite((first_line + j), sizeof(char), 1, fp);
            //strcat(superchar, (first_line + j));
            superc += first_line[j];
            //加入一个字符
        }
        for (int j = 0; j < l.get(i); ++j)
        {
            //fwrite(" ", sizeof(char), 1, fp);
            //strcat(superchar, " ");
            superc += " ";
            //fwrite((first_line + j), sizeof(char), 1, fp);
            //strcat(superchar, (first_line + j));
            superc += first_line[j];
            //加入字符
        }
        //回车
        //fwrite("\r\n", 2, 1, fp);
        //strcat(superchar, "\n");
        superc += "\n";

    }
    //关闭文件
}

思路：在这个函数中，我收到改变以后的序列后，按照序列模拟首行向左移动的过程按行输出数独到大字符串中，最后一起输出到文件。

项目感想

在该个人项目中，我所交出的答卷让我不是很满意，首先缺少了详尽的测试环节，其次解数独的算法效率不是很高，但是在以后的学习与实践当中，我相信我能够把回溯法应用的更好，因为这此项目让我深刻的记住了确保回溯的状态保存十分重要。
不仅如此，这个项目主要让我体会到一个完整的项目开发大体框架实践起来是什么样的一个流程，在以后的学习实践中，我会按照软件工程的标准，做的更好。