2020软件工程作业03

这个作业属于哪个课程	https://edu.cnblogs.com/campus/zswxy/software-engineering-2017-1/
这个作业要求在哪里	https://edu.cnblogs.com/campus/zswxy/software-engineering-2017-1/homework/10494
这个作业的目标	Sudoku
作业正文	↓
其他参考文献	giyf

1、Github项目地址

https://github.com/iriszero48/20177713

2、PSP表格

PSP2.1	Personal Software Process Stages	预估耗时（分钟）	实际耗时（分钟）
Planning	计划	5	5
Estimate	估计这个任务需要多少时间	5	5
Development	开发	950	1780
Analysis	需求分析 (包括学习新技术)	10	10
Design Spec	生成设计文档	60	30
Design Review	设计复审	5	5
Coding Standard	代码规范 (为目前的开发制定合适的规范)	0	0
Design	具体设计	30	10
Coding	具体编码	720	1560
Code Review	代码复审	5	5
Test	测试（自我测试，修改代码，提交修改）	120	160
Reporting	报告	80	570
Test Repor	测试报告	20	30
Size Measurement	计算工作量	0	0
Postmortem & Process Improvement Plan	事后总结, 并提出过程改进计划	60	540
合计		1035	2355

3、思路描述

知道的方法有几种

回溯(蛮力搜索)
随机搜索(模拟退火算法/遗传算法/禁忌搜索算法/爬山算法/蚁群算法/霍普菲尔德神经网络)
amb
精确覆盖问题(舞蹈链算法)
线性规划

为了偷懒选择线性规划实现数独求解

4、设计实现过程

建立三个项目

Sudoku

数独的实现

类图

Sudoku类图

代码图

Sudoku代码图

InitializeWithFilePath用于从文件初始化
InitializeWithArray用于从array初始化
Solve用于求解

根据m,n添加约束关系然后塞进Microsoft.Solver.Foundation线性规划库中求解
ToString用于将array转换成string

Sudoku类使用流程

构造函数 Sudoku
初始化 InitializeWithFilePath/InitializeWithArray
求解 Solve
转成string ToString

Launcher

整个程序的入口，见输入的参数转化成键值对进行解析并调用数独

UnitTest

使用Microsoft.VisualStudio.QualityTools.UnitTestFramework进行单元测试

5、性能改进

使用参数-m 9 -n 20 -i Z:input.txt -o Z:o.txt

vs性能探察器

vs性能探察器调用树

dotTrace allcall

dotTrace overview

ConcurrencyVisualizer使用率

ConcurrencyVisualizer线程

绝大部分的时间花在了Microsoft.Solver.Foundation的Solver上，无法优化

可以考虑对每个棋盘进行并行求解

使用OpenMP2.0对for进行并行，每次调度两个线程

#pragma omp parallel for schedule(dynamic, 2)
for (auto i = 0; i < maps->Length; ++i)
{
    ...
}

在20个棋盘时会增加100~200ms的开销

ConcurrencyVisualizer使用率20个多线程

ConcurrencyVisualizer线程20个多线程

在100个棋盘时单线程 2015ms

ConcurrencyVisualizer使用率100个单线程

ConcurrencyVisualizer线程100个单线程

在100个棋盘时多线程 988ms

ConcurrencyVisualizer使用率100个多线程

ConcurrencyVisualizer线程100个多线程

在100个棋盘时多线程内存分析

dotMemory

6、静态分析、单元测试、运行

静态分析

数独9x9测试

[TestMethod]
void Sudoku9x9()
{
    const Maps_ mp
    {
        {
            { 0,0,5, 3,0,0, 0,0,0 },
            { 8,0,0, 0,0,0, 0,2,0 },
            { 0,7,0, 0,1,0, 5,0,0 },

            { 4,0,0, 0,0,5, 3,0,0 },
            { 0,1,0, 0,7,0, 0,0,6 },
            { 0,0,3, 2,0,0, 0,8,0 },

            { 0,6,0, 5,0,0, 0,0,9 },
            { 0,0,4, 0,0,0, 0,3,0 },
            { 0,0,0, 0,0,9, 7,0,0 }
        },
            {
            { 0,0,0, 0,0,0, 0,0,0 },
            { 0,0,0, 0,0,3, 0,8,5 },
            { 0,0,1, 0,2,0, 0,0,0 },

            { 0,0,0, 5,0,7, 0,0,0 },
            { 0,0,4, 0,0,0, 1,0,0 },
            { 0,9,0, 0,0,0, 0,0,0 },

            { 5,0,0, 0,0,0, 0,7,3 },
            { 0,0,2, 0,1,0, 0,0,0 },
            { 0,0,0, 0,4,0, 0,0,9 }
        },
        {
            { 1,1,0, 0,0,0, 0,0,0 },
            { 0,0,0, 0,0,0, 0,0,0 },
            { 0,0,0, 0,0,0, 0,0,0 },

            { 0,0,0, 0,0,0, 0,0,0 },
            { 0,0,0, 0,0,0, 0,0,0 },
            { 0,0,0, 0,0,0, 0,0,0 },

            { 0,0,0, 0,0,0, 0,0,0 },
            { 0,0,0, 0,0,0, 0,0,0 },
            { 0,0,0, 0,0,0, 0,0,0 }
        }
    };

    auto s = gcnew Sudoku(9, 3);
    s->InitializeWithArray(ToMaps(mp));
    Assert::AreEqual(R"(1 4 5 3 2 7 6 9 8
8 3 9 6 5 4 1 2 7
6 7 2 9 1 8 5 4 3
4 9 6 1 8 5 3 7 2
2 1 8 4 7 3 9 5 6
7 5 3 2 9 6 4 8 1
3 6 7 5 4 2 8 1 9
9 8 4 7 6 1 2 3 5
5 2 1 8 3 9 7 6 4

9 8 7 6 5 4 3 2 1
2 4 6 1 7 3 9 8 5
3 5 1 9 2 8 7 4 6
1 2 8 5 3 7 6 9 4
6 3 4 8 9 2 1 5 7
7 9 5 4 6 1 8 3 2
5 1 9 2 8 6 4 7 3
4 7 2 3 1 9 5 6 8
8 6 3 7 4 5 2 1 9

Unsolvable!

)", Sudoku::ToString(s->Solve()));
}

从程序基本的运行和非法值方面设计单元测试

数独3x3
数独4x4
数独5x5
数独6x6
数独7x7
数独8x8
数独9x9
从文件输入数据
M在[3,9]外
N小于0
N的大小与输入的数据不匹配
M的大小与输入的数据不匹配

测试结果

单元测试

运行结果

数独3x3

数独3x3

数独4x4

数独4x4

数独5x5

数独5x5

数独6x6

数独6x6

数独7x7

数独7x7

数独8x8

数独8x8

数独9x9

数独9x9

6、异常处理

数独有什么异常应该是无法继续跑，所以直接在main使用try...catch

try
{
    ...
}
catch (System::Exception^ exception)
{
    fprintf(stderr, "Usage:
  %s -m 宫格阶级 -n 待解答盘面数目 -i 指定输入文件 -o 指定程序的输出文件
", argv[0]);
    System::Console::Error->WriteLine(exception->ToString());
    return EXIT_FAILURE;
}

参数不足8个

if (argc != 9)
{
    throw gcnew System::Exception("parameter error");
}

初始化数独,检查mn是否有效

if (m < 3 || m > 9)
{
    throw gcnew System::Exception("M must be 3 to 9");
}
if (n < 0)
{
    throw gcnew System::Exception("N must be greater than -1");
}

对应单元测试，M应该是[3,9]，这里初始化为2，所以抛出异常"M must be 3 to 9"

[TestMethod]
void MOutOfRange()
{
    try
    {
        gcnew Sudoku(10, 1);
    }
    catch (System::Exception^ exception)
    {
        Assert::IsTrue(exception->ToString()->Contains("M must be 3 to 9"));
    }
    try
    {
        gcnew Sudoku(2, 1);
    }
    catch (System::Exception^ exception)
    {
        Assert::IsTrue(exception->ToString()->Contains("M must be 3 to 9"));
    }
}

检查mn是否与数据大小相匹配

if (maps->Length != n)
{
    throw gcnew System::Exception("N size no matches");
}
for (auto i = 0; i < maps->Length; ++i)
{
    if (maps[i]->Length != m)
    {
        throw gcnew System::Exception("M size no matches");
    }
    for (auto j = 0; j < m; ++j)
    {
        if (maps[i][j]->Length != m)
        {
            throw gcnew System::Exception("M size no matches");
        }
    }
}

对应单元测试，mp为9x9的数独，保存时使用Substring去掉了第一个数字，变成了不规则数组，不满足每行每列都是M个的要求，所以抛出异常"M size no matches"

[TestMethod]
void MSizeNoMatch()
{
    const Maps_ mp
    {
        {
            { 0,0,5, 3,0,0, 0,0,0 },
            { 8,0,0, 0,0,0, 0,2,0 },
            { 0,7,0, 0,1,0, 5,0,0 },

            { 4,0,0, 0,0,5, 3,0,0 },
            { 0,1,0, 0,7,0, 0,0,6 },
            { 0,0,3, 2,0,0, 0,8,0 },

            { 0,6,0, 5,0,0, 0,0,9 },
            { 0,0,4, 0,0,0, 0,3,0 },
            { 0,0,0, 0,0,9, 7,0,0 }
        }
    };
    const auto filename = gcnew System::String("FileInput.txt");
    System::IO::File::WriteAllText(filename, Sudoku::ToString(ToMaps(mp))->Substring(2));
    auto sudokuFile = gcnew Sudoku(9, 1);
    try
    {
        sudokuFile->InitializeWithFilePath(filename);
    }
    catch (System::Exception^ exception)
    {
        Assert::IsTrue(exception->ToString()->Contains("M size no matches"));
    }

    System::IO::File::Delete(filename);
}

7、代码说明

数独的核心是Sudoku::Maps^ Sudoku::Solve()函数

流程图

代码

Sudoku::Maps^ Sudoku::Solve()
{
    using namespace Microsoft::SolverFoundation::Solvers;

    // 创建一个三维数组存放结果
    auto res = gcnew Maps(maps->Length);
    for (auto i = 0; i < maps->Length; ++i)
    {
        res[i] = gcnew Map(maps[i]->Length);
        for (auto j = 0; j < maps[i]->Length; ++j)
        {
            res[i][j] = gcnew array<int>(maps[i][j]->Length);
        }
    }

    // 并行遍历每个盘面，同时调度两个线程
    #pragma omp parallel for schedule(dynamic, 2)
    for (auto i = 0; i < maps->Length; ++i)
    {
        // 初始化
        auto map = maps[i];
        auto s = ConstraintSystem::CreateSolver();
        const auto z = s->CreateIntegerInterval(1, maps[i]->Length);
        auto lp = s->CreateVariableArray(z, "n", maps[i]->Length, maps[i]->Length);

        // 为每行和已知条件添加约束
        for (auto row = 0; row < maps[i]->Length; ++row)
        {
            for (auto col = 0; col < maps[i]->Length; ++col)
            {
                if (map[row][col] > 0)
                {
                    s->AddConstraints(s->Equal(map[row][col], lp[row][col]));
                }
            }
            s->AddConstraints(s->Unequal(GetSlice(lp, maps[i]->Length, row, row, 0, maps[i]->Length - 1)));
        }

        // 为每列添加约束
        for (auto col = 0; col < maps[i]->Length; ++col)
        {
            s->AddConstraints(s->Unequal(GetSlice(lp, maps[i]->Length, 0, maps[i]->Length - 1, col, col)));
        }

        // 为不同盘面阶数设置宫格大小
        auto stepRow = 0;
        auto stepCol = 0;
        switch (maps[i]->Length)
        {
        case 4:
            stepRow = 2;
            stepCol = 2;
            break;
        case 6:
            stepRow = 2;
            stepCol = 3;
            break;
        case 8:
            stepRow = 4;
            stepCol = 2;
            break;
        case 9:
            stepRow = 3;
            stepCol = 3;
            break;
        default:;
        }

        // 如果当前盘面阶数存在宫格，则为每个宫格添加约束
        if (stepRow != 0 && stepCol != 0)
        {
            for (auto row = 0; row < maps[i]->Length; row += stepRow)
            {
                for (auto col = 0; col < maps[i]->Length; col += stepCol)
                {
                    s->AddConstraints(
                        s->Unequal(
                            GetSlice(lp, stepCol * stepRow, row, row + stepRow - 1, col, col + stepCol - 1)));
                }
            }
        }

        // 求解
        auto sol = s->Solve();
        try
        {
            for (auto row = 0; row < maps[i]->Length; ++row)
            {
                for (auto col = 0; col < maps[i]->Length; ++col)
                {
                    res[i][row][col] = sol->GetIntegerValue(lp[row][col]);
                }
            }
        }
        catch (System::Exception^) // 无解情况返回nullptr
        {
            res[i] = nullptr;
        }
    }
    return res;
}

8、心路历程与收获

刚开始要求写数独想着用微软的Microsoft.Solver.Foundation线性规划库偷懒，然后看见要求“使用C++或者Java语言实现”，就决定使用C++/CLI方言，因为Microsoft.Solver.Foundation是基于.NET Framework的(后面老师说不限定语言，但是已经开工了，就继续C++/CLI了)，C++/CLI能直接用.NET Framework的库，顺便还能把FSharp的核心库也拿来用用，写着写着，发现C++/CLI和F#交互太麻烦了，把函数作为参数传递给F#折腾了几个小时，最后决定写个FSharpFuncUtil来解决这个问题，FSharpFuncUtil将System.Func<'a,'b>转换成FSharpFunc<'a,'b>，System.Func可以gcnew出来，自定义函数也能定义个ref class塞个静态函数gcnew解决问题，原本还想整个类似于std::Bind1st一样的函数用于FSharpFunc/System.Func，想到万一是个大坑就没整了，最后放上这个程序真正的一行核心代码（x

maps = ArrayModule::Take(n, ArrayModule::Map(FSharpFuncUtil::FSharpFuncUtil::ToFSharpFunc(gcnew System::Func<array<int>^, array<array<int>^>^>(Func::ChunkBySize)), ArrayModule::ChunkBySize(m * m, ArrayModule::Map(FSharpFuncUtil::FSharpFuncUtil::ToFSharpFunc(gcnew System::Func<System::String^, int>(System::Int32::Parse)),System::IO::File::ReadAllText(path)->Replace("
", " ")->Replace("
", " ")->Split(mapSp, System::StringSplitOptions::RemoveEmptyEntries)))));