[2017BUAA軟工]個人項目

軟工個人項目

一、Github項目位址

https://github.com/Lydia-yang/2017BUAA-SoftwareEngineering

二、解題思路

在剛開始拿到題目的時候，關于生成數獨終局，我的思路是可以随機生成數然後選擇适合的數填滿即可得到，後來通過上網查找一些數獨生成算法，發現可以通過一定的順序來減少工作量，比如将1到9個數字依次随機填入3*3的宮格裡，或者記錄每次每次嘗試的數避免重複，還有初始化對角線的3個3*3的宮格，或者依次填入1到9等。最後標明了将1到9個數值依次填入3*3的宮格裡這種算法，也就是這篇部落格的算法。

将數獨分為9小塊，将1-9按照一定序列填寫1-9小塊，比如先将1填入1号小塊，再填入2号小塊，知道填完9号小塊，再填2與1一樣，周遊所有數即可得到一個生成數獨。

至于解數獨，思路與生成數獨差不多，也是回溯，但是是對于每一個沒有填的位置試所有可能的數字。

## 三、設計實作過程

實作我的算法，首先，要有一個存儲九宮格的二位數組，出于考慮，我建立了一個數獨類，這個類裡有相應的行列及3*3小塊的重複檢查，以及插入和删除，由于我解決數獨和生産數獨用的是不同的方法來插入數字的（一個是确定數字選位置，一個确定位置選數字），是以有兩種插入的方法，然後就是列印數獨的方法。

在處理指令行中，有判斷-c後面接的是否是正整數的函數，同樣，生成數獨和解數獨都有各自的函數，解數獨是通過檔案讀入的，是以也設定了一個處理檔案讀入函數，在後面優化的過程中，又新增了輸出到檔案的函數，單元測試主要是将produce和solve這兩個函數測試了一遍。下圖是函數類之間的關系：

## 四、性能改進

一開始生成數獨時，幾分鐘都沒出結果，後來經過性能分析，如下圖:


發現是輸出占了大多數時間，後來做了優化，将輸出結果先輸出到一個字元數組裡，再全部一起輸出，最後的性能分析如下:

## 五、代碼說明

下面這段代碼是用來解數獨的，其中輸入代表的含義為：

• sudoku sudo, 存儲待解的數獨
• int x[], 所有為空位置的x值
• int y[], 所有為空位置的y值
• int total, 空位子的總數
• int & count, 用來記錄目前已經填了多少空位子
• char *str, 字元數組用來儲存需要列印的數獨
• int &count_s， 用來标記字元數組的元素個數

對于每一次執行，将這個空位子插入數字，并标記已經試過的數字，最後完成時輸出，每次回溯時都清空目前位置。

void solve(sudoku sudo, int x[], int y[],int total, int & count, char *str, int &count_s) {
	int marked[9] = { 0 };//用來标記數字是否已經選過
	int new_count = count;
	while (true) {

		int now = sudo.insert(1, x[new_count], y[new_count], marked);//在空位子插入數字

		if (now < 0) return;
		else marked[now-1] = 1;

		if (new_count == total - 1) {//最後一個
			sudo.printsudoku(str, count_s);//列印數獨
			return;
		}
		count = new_count + 1;
		solve(sudo, x, y, total, count, str, count_s);//下一個
		if (count == total - 1) return;
		sudo.del(1, x[new_count], y[new_count]);
	}
	
}
           

下面這段代碼是用來生成數獨的，其中輸入代表的含義為：

- int total, 最終需要生成數獨的總個數

- int nums[], 1-9的序列用來規定周遊數的順序

- int block_num, 标記目前的3\*3的塊号

- int & count_total, 用來标記目前已經生成的數獨個數

- int count_nums, 用來标記目前對于nums的元素位置

- sudoku s, 目前已經填好一些空的數獨

- char *str, 字元數組用來儲存需要列印的數獨

- int &count_s， 用來标記字元數組的元素個數

對于每一次執行，将這個數字插入目前3*3小塊空的位置，并标記已經試過的位置，最後完成時輸出，每次回溯時都清空目前位置。

void produce(int total, int nums[], int block_num, int & count_total, int count_nums, sudoku s, char *str, int &count_s) {
	int marked[9] = { 0 };//标記已經試過的位置
	int new_block_num, new_count_nums;
	
	while (true) {
		new_block_num = block_num + 1;
		new_count_nums = count_nums;
	
		int now = s.insert(nums[new_count_nums], new_block_num, marked);
	
		if (now <0) return;
		else marked[now] = 1;

		if (new_block_num == 9) {
			if (new_count_nums < 8) {
				new_count_nums=count_nums+1;
				new_block_num = 0;
			}
			else {//填寫至最後一個
				count_total++;
				s.printsudoku(str, count_s);//列印數獨
				s.del(0, new_block_num, now);
				return;
			}
		}
		produce(total, nums, new_block_num, count_total, new_count_nums, s, str, count_s);
		if (count_total == total) return;
		s.del(0, new_block_num, now);
	}
}

           

## 六、PSP

Psp	personal software progress stages	預估耗時	實際耗時
planning	計劃	20	30
estimate	估計這個任務需要多少時間	10
development	開發	480	600
analysis	需求分析
design spec	生成設計文檔		35
design review	設計複審
coding standard	代碼規範		15
design	具體設計	60	70
coding	具體編碼	240	300
code review	代碼複審	120	130
test	測試
reporting	報告		18
test report	測試報告
size measuring	計算工作量	5	3
postmortem & process improvement plan	事後總結，提出過程改進計劃
合計	1285	1551