软件工程个人项目——数独

项目的源代码在Github上托管，可以在这里查看。

PSP表格

PSP2.1	Personal Software Process Stages	预估耗时（分钟）	实际耗时（分钟）
Planning	计划	40	60
Estimate	估计这个任务需要多少时间	--	1080
Development	开发	--	--
Analysis	需求分析（包括学习新技术）	150	180
Design Spec	生成设计文档	--	--
Design Review	设计复审（和同事审核设计文档）	--	--
Coding Standard	代码规范（为目前的开发制定合适的规范）	40	60
Design	具体设计	60	90
Coding	具体编码	260	240
Code Review	代码复审	30	90
Test	测试（自我测试，修改代码，提交修改）	120	120
Reporting	报告	240	180
Test Report	测试报告	30	60
Size Measurement	计算工作量	30	60
Postmortem & Process Improvement Plan	事后总结，并提出过程改进计划	60	60
	合计	1020	1140

思路

项目要求的程序主要需要实现两个功能：

1. 求解数独
2. 生成数独终局

在做这个项目之前本人也曾经痴迷于数独一段时间，因此对数独游戏本身不需要花时间再做更多的了解，就直接开始讲解决这个问题的思路了。

算法

求解数独

数独的求解过程中最重要的方法是排除法：由于每一行、每一列以及每一个九宫格中必须是不能重复的1到9的九个数字，因此对给出的任意一个数独局面，许多空方格中的可选数字都是有限的，而在求解一个实际的数独问题当中，许多空方格当中可以填入的数字在运用排除法之后往往只有两三个——甚至只有一个，这种情况下自然就可以直接填入对应的数字。

排除法

排除法的实现十分简单，只要对一个空方格检查其对应的行、列以及九宫格中其它已经填入的数字即可，当九个数字当中的八个数字均被填入时就可以确定该方格中应当填入的数字，对简单的数独题而言，只要不断地运用排除法就可以最终解决它。遗憾的是，大部分数独题都没有那么简单，需要运用许多更为复杂的技巧才能解决，如果要一一实现这些技巧不仅麻烦，而且并不能保证可以解决所有的数独题，因此在排除法之外还需要运用别的方法。

对数独这类在解空间中进行搜索的问题，回溯法是一个常用的方法，只要不停地试探每个空方格中可以填入的数字，并在发现矛盾时进行回溯，就可以保证能找出一个数独局面的所有解。问题是如果盲目地进行搜索，则回溯法的效率会极低，最差的实现对每个空方格试探所有可能的数字，将需要次搜索才能找到最终解，这是不可接受的，但只要结合排除法就可以简单地解决这个问题。

通过运用排除法，我们可以大大减少每个空方格中可能填入的数字，从而缩小了需要搜索的解空间，并且我们观察到每个新填入的数字都可能让其它方格中的可选数字减少，因此实际需要搜索的局面是很少的。同时，为了尽可能地减少填入错误数字的概率，在每一步需要在空方格中填入不确定的数字时，我们选取可选数字最少的空方格填入数字。

生成数独终局

在完成求解数独的程序之后，如何生成数独终局的答案就变得十分显然了，只要在空的数独局面上直接运行已经实现了的回溯法，则所返回的解都是有效的数独终局。由于不需要从头开始计算每一个终局，这个算法的效率十分高，且由于回溯法的一个特点就是可以找到所有的解，因此只要有足够的时间我们完全可以生成所有的数独终局，该算法的正确性也得到了保障。

使用语言

出于性能上的考虑，我们采用C++语言，并使用Visual Studio 2017进行项目的开发，并且我们会使用许多C++17标准的特性，以使代码更加现代、简洁。

项目要求最后给出可以运行的文件以及附带的dll库，因此在开发的过程中我们将尽可能只使用标准库，而不使用例如Boost的外部库进行开发。

附加题要求开发一个解数独的GUI程序，由于MFC、C++\CIR等Visual Studio自带支持的GUI库均需要运行时支持（安装附加程序），windows原生的图形API又十分难用，因此决定使用Qt开发所要求的GUI。在windows上Qt开发的程序可以使用专用工具进行deploy，不需要运行时支持，因此可以在任意电脑上运行，符合项目的要求。

设计实现

模块

程序中将主要包含四个模块：Main，Generator，Solver，State。每个模块的功能如下述：

Main

主要包含程序的业务逻辑，负责处理程序的输入，并调用相应的模块进行处理，最后对结果进行输出。

Main模块包含程序的main()函数，其中涉及的功能有处理用户的输入，尝试读取/写入相关的文件，调用相关的模块，在发生错误的时候结束程序并向用户提供反馈。

Main模块中大部分的代码都将与错误处理有关，因为用户的输入可以是任意的，且IO操作也有相当的不确定性，这需要我们的程序拥有鲁棒性，能正确地处理不同地输入，并在出现问题时正确地进行错误处理并退出程序，同时向用户提供有用地信息。

Generator

包含生成数独终局的算法，可以返回任意数量（不超过所有终局数量）的数独终局。

Generator的功能与实现都相对简单，它牵涉到的主要是调用Solver并返回对应数量的解（数独终局）。

Generator模块可以向Solver传递特定的参数以针对产生解的情况做出优化。

Solver

包含回溯法的算法，使用回溯法解决一个数独问题，并可以返回任意数量（不超过真值）的解。

Solver在从传递过来的Board转换为State之后就将只在State上进行操作。回溯法将在找到指定数量的解之后返回而非一直找到存在的所有解之后才返回（这个功能的必要性是因为我们需要用Solver产生不同的数独终局，这时提供的是一个空的局面，时间和空间都不允许我们找到所有的数独终局再返回）。

State

表示一个数独局面，可以在上面进行操作、提取状态。

一个State表示一个已经使用排除法（或实现了的其它方法）填入所有可以填入的数字的局面，而不能表示一个中间局面（即还存在可以使用排除法填入数字的局面）。这样设计是因为我们观察到在使用回溯法求解的过程中，这样的中间局面是没有作用的，只有在不能通过排除法（或实现了的其它方法）再填入数字时才需要使用回溯法进行操作，因此我们可以“跳过”中间的状态。这样做简化了程序的逻辑，使模块的责任更加明确。

State是immutable的，也就是说，不能从外部改变一个State，每个State只能从一个已经存在的State创建或者由构建函数创建。这样设计的目的是为了使算法更加清晰，并且我们的算法没有从外部改变一个State的必要。

测试

Visual Studio 2017 Community代码分析程序没有警告。

我们对程序编写了单元测试，单元测试使用的库为Googel Test，简称GTest。使用Visual Studio检查单元测试覆盖率为98%。使用了30个很难的数独题作为测试用例。

使用GTest的好处在于它提供了编写好的Macro来供我们使用，让我们能很方便地编写、组织对项目的单元测试，让我们能将精力集中在程序逻辑的编写上，而不是对这些测试的组织、维护。

GTest的一个好处在于，当测试失败的时候它会自动给出失败的地方的详细信息，使我们能够快速定位错误，而不至于还要一个一个去试，且这些几乎不需要编写额外的代码，只需要使用它自带的Macro编写测试就可以享受它的便利性。

最后我们对三个主要的模块分别编写了三个Test Suite，并在最后通过了所有测试。程序刚完成的时候是存在有Bug的，单元测试帮助我们及时发现了Bug并定位到了它的位置，如果没有单元测试的话在整个项目中寻找Bug将是一个十分困难的过程，而且也无法保证我们的模块的可靠性。

在完成单元测试之后，我们还使用了从网上找到的20个非常难的数独题来作为对性能的最终评定。最后程序在~140ms的时间内解决了这20个问题，可以说是比较满意的结果了。

性能分析

最终我们使用开启O2优化之后编译产生的程序进行测试。

经测试最初完成的程序要生成一百万个不同的终局所需时间大致为~34s，这个性能已经十分好了，主要得益于我们只用一个int表示一个格子中可以填入的数字，并在State类的实现中使用了十分高效的比特运算，且对回溯法做了许多优化，大大减少了错误回溯的次数。虽然已经做的很好了，但还有许多改进的余地。

使用Visual Studio 2017自带的性能探查器我们得到下列的结果：

性能分析一

可以看出，程序运行中在NumberOfSetBits函数上的运行时间是一个瓶颈，本来我们使用的是最简单的算法：

int NumberOfSetBits(int n) {
    int count = 0;
    while(n) {
        if (n & 1) count++;
        n >>= 1;
    }
    return count;
}

这个算法的效率是较低的，无论数值是1的比特位有多少个，都需要运行大约9个循环，因此我们采用改进的算法：

int NumberOfSetBits(int n) {
    int count = 0;
    while(n) {
        n = (n - 1) & n;
        count++;
    }
    return count;
}

改进后的算法每次循环的次数与1的个数相同，可以看出效率是大大提升了的。再次运行代码分析得到的结果如下：

性能分析二

在改进了NumberOfSetBits之后，再次运行测试，则发现现在生成一百万个不同的终局只需要~21s，这是一个很大的进步。

可能的进一步改进

同时我们还可以看到程序的瓶颈在_AddConstraint函数上，这是在我们的预料之中的，目前很难对函数本身再做优化了，因此主要优化的地方应该是让State更快地收敛，要做到这一点就需要在程序中运用更多的数独技巧。

目前我们只使用了最简单的对单个格子的排除法：当一个格子中只有一个能填入的数字时，将该数字填入它。而一个同样常用的排除法是：当某一行/某一列/某个九宫格中某个数字只在其中一个格子里可以填入时，将该数字填入该格子。实现该排除法可以使回溯法更快地收敛，并减少需要搜索的解，很可能可以改进算法。

还有一个可能的改进是对多线程的优化，利用多核CPU的性能，和算法无关。因为回溯法是从一个初局出发找到其所有的解，那么我们可以在多个线程上对不同的初局同时运行回溯法，并在最后将结果整合。这可以显著提高运行速度，在4核CPU上速度提高四倍、8核CPU上速度提高八倍，不过这个方法只是提高了对硬件的使用，没有真正提高运算效率。

代码说明

State

typedef std::array <std::array<int, 9>, 9> Board;
typedef std::array <std::array<int, 9>, 9> Grids;

class State
{
public:
    State(const std::optional<Board> board = {}, bool puzzle_mode = true);
    ~State();
    std::optional<State> AddConstraint(int row, int col, int n);
    void Print();
    bool IsComplete();
    Grids GetGrids();
private:
    Grids grids_;
    bool puzzle_mode_;
    void _AddConstraint(int row, int col, int n);
    bool TryAddMoreConstraint();
    bool valid();
};

State的关键代码主要是我们对一个State的存储形式与在其上面的操作，出于效率的考虑，我们使用一个9x9的int二维数组存储数独局面中每个格子的状态，一个int对应一个格子中可能填入的数字，最低的九个比特位代表九个数字是否可以填入。

比如说若一个格子中可能填入的数字为1、2、5，则相对应的int为0b10011。我们用typedef定义Grids为State内部表示状态的数据。

最关键的函数是AddConstraint，这表示将与行列对应的数字限制为一个数字，也可以理解为填入一个数字，对应的代码如下：

void State::_AddConstraint(int row, int col, int n) {
    assert(n >= 1 && n <= 9);
    int flag = 1 << (n - 1);
    assert(grids_[row][col] & flag);
    grids_[row][col] = flag;
    for (int i = 0; i < 9; i++) {
        if (i == row) continue;
        int prev = grids_[i][col];
        grids_[i][col] &= ~(flag);
        int after_bits = NumOfSetBits(grids_[i][col]);
        if (prev != grids_[i][col] && after_bits == 1) {
            _AddConstraint(i, col, MsgBitPos(grids_[i][col]));
        }
    }
    for (int i = 0; i < 9; i++) {
        if (i == col) continue;
        int prev = grids_[row][i];
        grids_[row][i] &= ~(flag);
        int after_bits = NumOfSetBits(grids_[row][i]);
        if (prev != grids_[row][i] && after_bits == 1) {
            _AddConstraint(row, i, MsgBitPos(grids_[row][i]));
        }
    }
    int row_start, col_start;
    row_start = row - row % 3;
    col_start = col - col % 3;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (row_start + i == row && col_start + j == col) continue;
            int prev = grids_[row_start + i][col_start + j];
            grids_[row_start + i][col_start + j] &= ~(flag);
            int after_bits = NumOfSetBits(grids_[row_start + i][col_start + i]);
            if (prev != grids_[row_start + i][col_start + j] && after_bits == 1) {
                _AddConstraint(row_start + i, col_start + i, MsgBitPos(grids_[row_start + i][col_start + i]));
            }
        }
    }
}

代码中依次将要填入数字的格子对应的行、列、九宫格中的其它格子中该数字的比特位置于零，要注意的是，在这个过程中可能产生新的可以确定数字的格子，当产生这样的格子时我们必须对其调用对应的AddConstraint_函数，以维持数据的一致性（所有只有一个可能数字的格子都是已经确定的）。

optional<State> State::AddConstraint(int row, int col, int n) {
    if (!(grids_[row][col] & (1 << (n - 1)))) return {};
    State new_state;
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            new_state.grids_[i][j] = grids_[i][j];
        }
    }
    new_state.puzzle_mode_ = puzzle_mode_;
    new_state._AddConstraint(row, col, n);
    if (puzzle_mode_) {
        while(new_state.TryAddMoreConstraint());
    }
    if (!new_state.valid()) return {};
    return new_state;
}

AddConstraint是AddConstraint_对应的外部接口，它会创建一个新的State并在上面调用AddConstraint_函数，注意的是当新产生的State不合法时我们将返回一个空值，这里利用了std::optional这个C++17提供的新特性。

Solver

class Solver
{
public:
    Solver(const std::optional<Board> board, int num = 1, bool puzzle_mode = true);
    std::vector<Board> GetSolutions();
    ~Solver();
private:
    std::vector<Board> solutions_;
    void BackTrack(State s);
    int target;
};

Solver的接口简单明了，只需要提供初始的Board、期望解的数量、解数独的模式，然后使用GetSolutions接受产生的数独解就可以了。

Solver中最关键的是实现回溯法的函数：

void Solver::BackTrack(State s) {
    Grids grids = s.GetGrids();
    if (s.IsComplete()) {
        Board board;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                board[i][j] = MsgBitPos(grids[i][j]);
            }
        }
        solutions_.push_back(board);
        return;
    }
    int min_pos = -1, min_count = 10;
    vector<int> a;
    for (int i = 0; i < 9 * 9; i++) {
        int count = NumOfSetBits(grids[i / 9][i % 9]);
        if (count == 1) continue;
        if (count < min_count) {
            min_count = count;
            min_pos = i;
        }
        if (count == 2) {
            break;
        }
    }
    for (int i = 0; i < 9; i++) {
        if (grids[min_pos / 9][min_pos % 9] & (1 << i)) {
            int row = min_pos / 9, col = min_pos % 9;
            optional<State> new_state = s.AddConstraint(row, col, i + 1);
            if (new_state.has_value()) {
                BackTrack(*new_state);
                if (solutions_.size() == target) {
                    return;
                }
            }
        }
    }
}

在BackTrack中我们首先判断当前的State是否已经是一个完整的解，若是的话则将它添加到解集当中并返回。然后我们寻找还没有确定数的可选数字的数量最少的格子，在上面递归运行回溯法。

找到格子之后我们在上面尝试所有可能的数并递归调用回溯法，这是算法的部分，就不再赘述了。一个需要注意的是若产生合法的State则我们继续尝试下一个数，而不需要回溯下去。

Generator

class Generator
{
public:
    Generator(int n);
    ~Generator();
    std::vector<Board> GetBoards();
private:
    int n;
};

由于Generator实质上只是Solver上的一层wrapper，因此接口与实现的代码均十分简单。

vector<Board> Generator::GetBoards() {
    Board b{};
    b[0][0] = (4 + 1) % 9 + 1;
    Solver s(b, n, false);
    return s.GetSolutions();
}

按照题目要求我们将初始Board的第一个数设置为学号最后两位进行运算的结果，将其传递给Solver并返回得到的解。

SudokuSolver

这是我们的主函数，其中大部分的代码都是输入输出与错误处理，main函数的内容如下：

int main(int argc, char *argv[]) {
    if (argc != 3) {
        PrintUsage();
        return 0;
    }
    string option(argv[1]);
    if (option == "-c") {
        int n;
        try {
            n = stoi(argv[2]);
        }
        catch (invalid_argument e) {
            cout << "'" << argv[2] << "' is not a valid number!";
            return 0;
        }
        ofstream fout("sudoku.txt", ios::out | ios::trunc);
        if (!fout) {
            cout << "Failed opening file 'sudoku.txt' !" << endl;
            return 0;
        }
        Generator g(n);
        vector<Board> boards = g.GetBoards();
        for (int i = 0; i < n; i++) {
            OutputBoard(fout, boards[i]);
        }
    }
    else if (option == "-s") {
        ifstream fin(argv[2]);
        if (!fin) {
            cout << "Failed opening file '" << argv[2] << "' !" << endl;
            return 0;
        }
        ofstream fout("sudoku.txt", ios::out | ios::trunc);
        if (!fout) {
            cout << "Failed opening file 'sudoku.txt' !" << endl;
            return 0;
        }
        while (true) {
            Board b;
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    fin >> b[i][j];
                    if (fin.eof()) {
                        cout << "Solved all puzzles" << endl;
                        return 0;
                    }
                    if (b[i][j] < 0 || b[i][j] > 9 || fin.fail()) {
                        cout << "Invalid Sudoku problem!" << endl;
                        return 0;
                    }
                }
            }
            Solver s(b);
            if (s.GetSolutions().empty()) {
                cout << "No solution exists!" << endl;
                return 0;
            }
            Board solution = s.GetSolutions()[0];
            OutputBoard(fout, solution);
        }
    }
    else {
        PrintUsage();
        return 0;
    }

}

可以看出来，我们需要检查的主要有三个地方：

1. 命令行参数
2. 读取/写入文件
3. 模块的返回值

在这三个地方我们都需要检查对应的值，并在需要的时候中止程序运行，并向用户提供错误信息，这对保证程序的鲁棒性十分重要。

总结

在本项目中我们使用C++实现了一个基于回溯法的可以生成数独终局和求解数独的程序，且在项目的过程中我们按照计划、设计、编码、测试、性能分析等一系列软件工程中的标准步骤完成了项目。

从这个项目中我收获了许多，也掌握了许多之前只了解概念但并没有实际接触到的工具，对软件工程有了更深的理解。