软工实践第二次作业

项目准备

vs的安装（参考了别人的安装教程）
重新熟悉了一下c++工程的设计过程（主要参照之前计算机的写法）

解题思路

1）随机数法

这个是我在网上查找找到的方法，主要是通过一个已知的完全的数独矩阵，进行多种多次的矩阵变换。但是这种写法不符合作业的要求，首先是作业要求第一个空为学号%9+1，这就使得矩阵变化情况减少了很多，而且作业要求数独的不同情况为100w种，我想到这个数量级就放弃了

2）暴力的dfs

我的第一个想法其实是采用dfs的方法，进行行，列，宫的比较来进行所谓的试根法。这个思想还是比较容易实现的，而且代码量也比较少

解题过程

第一次尝试很快写好了代码，但是我运行的时候一直死循环，最后把每次试根的矩阵打印出来，才发现每次的回溯没有记录之前填入的值。每次试根都是从头（1）、开始尝试，造成了一直是不能继续往下的那个根在那边一直重复。

下面是失败的代码：


void next(int row, int col){
	++col;
	if(col >= 10){
		col = 1;
		++row;
	}
	dfs(row, col);
}

void back(int row, int col){
	--col;
	if(col <= 0){
		--row;
		col = 9;
	}
	temp[array[row][col]] = true;
	dfs(row , col);
}


bool all_num = true;
for(int i = 1; i < 10; i++){
	if(flag[i] == false || temp[i] == true) continue;
	array[row][col] = i;
	temp[i] = true;
	all_num = false;
	for(int i = 1; i <= 9; ++i){
		for(int j = 1; j <= 9; ++j){
			cout << array[i][j];
		}
		cout << endl;
	}
	next(row, col);
	if(all_num){
		array[row][col] = 0;
		back(row, col);
	}
	cout << "The End" << endl;
}

死循环，无法继续

第二次看了一下网上的代码，采用的是三个数组分别判断是否符合，然后用1~9的循环来进行试根，避免一个根进行多次不必要的dfs
这里是判断（行，列，宫判断）


bool generator::CheckRowCol(int row, int col) {
	//  行比较 
	if (Row[row][sudoku[row][col]] == true) return false;

	//  列比较 
	if (Col[col][sudoku[row][col]] == true) return false;

	//  宫比较 
	if (Palace[getPalace[row][col]][sudoku[row][col]] == true) return false;

	return true;
}

主要的dfs


void generator::dfs(int row, int col) {
	if (row == 9 && col == 9) {
		++cnt;
		//ioscout << "No." << cnt << " output :" << endl;
		Print();
		if (cnt == n) {
			exit(0);
		}
		return;
	}

	if (row == 1 && col == 1) {
		sudoku[1][1] = (2 + 8) % 9 + 1;
		Row[1][sudoku[1][1]] = true;
		Col[1][sudoku[1][1]] = true;
		Palace[1][sudoku[1][1]] = true;
	}
	++col;
	if (col > 9) {
		++row;
		col = 1;
	}
	for (int i = 1; i<10; i++) {
		sudoku[row][col] = i;
		if (!CheckRowCol(row, col)) continue;
		Row[row][sudoku[row][col]] = true;
		Col[col][sudoku[row][col]] = true;
		Palace[getPalace[row][col]][sudoku[row][col]] = true;
		dfs(row, col);
		Row[row][sudoku[row][col]] = false;
		Col[col][sudoku[row][col]] = false;
		Palace[getPalace[row][col]][sudoku[row][col]] = false;
	}
	sudoku[row][col] = 0;

	return;
}

PSP表格

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

性能分析

下面是运行100w的性能分析

主要在dfs上花费了太多时间

代码覆盖率

代码覆盖率目前还找不到工具分析，之后会更新