第二次作業————個人項目實戰

項目位址

https://github.com/raven031502225/one

項目需求

利用程式随機構造出N個已解答的數獨棋盤

輸入

數獨棋盤題目個數N（0<N<=1000000）

輸出

随機生成N個 不重複 的 已解答完畢的 數獨棋盤，并輸出到sudoku.txt中且左上角的第一個數為：（學号後兩位相加）% 9 + 1

遇到的困難及解決方法

困難描述：

僅産生随機數判斷是否能夠填入如不能則換個随機數，如還是不行，則從頭來，這種算法耗時太長

做過的嘗試：

填的位置為随機，填的位置為同一個宮内的随機，最後使用逐行填入并回溯而不是全部重來

是否解決

已解決

收獲

單純是想出來的方法大多是很粗糙的，而更好的方法往往是在各種優化之後得到的

解題思路

原來閑的時候做過數獨這種東西，當時是用來消磨時間的，覺得很熟悉，但是仔細思考之後才發現熟悉的僅僅是解數獨的方法而不是設計的方法，是以最開始覺得隻要是随機數，并且符合三種判斷條件的就肯定能夠填進去，是以最開始版本的代碼甚至不能跑出一個完整的數獨，最開始覺得是bug，輸出了每一步的走法後才發現數獨的生成并不是這麼簡單的東西，其實是非常容易出現沖突的，然後就想到原來做過的馬踏棋盤的題，于是就使用了回溯法來生成數獨。

關鍵代碼or設計說明

部分代碼

以下為判斷此格是否能夠填入此數的代碼部分

if (tright[y][x][anyway - 1] == 0) {						//判斷本格是否出現過此數并無法生成無沖突的數獨
		if (square[(x / 3) + 3 * (y / 3)][anyway - 1] == 0) {	//判斷本格所處的九宮格内是否存在此數
			if (upright[y][anyway - 1] == 0) {					//判斷本格所處的行内是否存在此數
				if (transverse[x][anyway - 1] == 0) {			//判斷本格所處的列内是否存在此數
					all[y][x] = anyway;							//将本數記錄入數獨内
					upright[y][anyway - 1] = 1;					//記錄：本行已存在此數
					transverse[x][anyway - 1] = 1;				//記錄：本列已存在此數
					square[(x / 3) + 3 * (y / 3)][anyway - 1] = 1;	//記錄：本宮已存在此數
					y = y + x / 8;								
					x = (x + 1) % 9;							//移至下一個需要寫入的位置
				}
				else tright[y][x][anyway - 1] = 1;				//本格不能填入此數
			}
			else tright[y][x][anyway - 1] = 1;					//同上
		}
		else tright[y][x][anyway - 1] = 1;						//同上上
	}
           

設計說明

第一個數是固定的，初始化則初始化時直接将其初始化，接下來逐行試圖填入數字，每次生成一個随機數，将其固定到0-5的範圍内，然後再判斷是否符合三個限制條件并是否已經在這個格子裡出現過并且無法生成正确的數獨終盤，如果均符合限制則填下此數并進行下一格的填充，如果此格九個數均不可填充，則回溯一格，若全部填充完畢之後，則将最後一個數标記為不可用并重新推導則可以得到不重複的數獨終盤。

測試運作

通過指令行運作程式：

運作程式所輸出檔案的部分截圖：

程式的改進

程式改進所消耗的時間零零散散加起來大概有8-9個小時，最開始時是随機出一個數如果本位9個都不能使用則全盤推倒重來，這樣就導緻程式運作時間非常的長，跑1000平均需要花費20s左右，這時想到了回溯，但是這時候的回溯并不是挨位來回溯，而是如果本位9個都不能使用則回溯一行，這樣有了一定的性能提高，1000基本上需要15s，但是這時候和同學們讨論題的時候他們提到了曾經打過的馬踏棋盤的題目，這時候才想起來逐位回溯......于是改為逐位回溯，這樣1000僅需要1-2s就可以跑出來了，而且還不需要擔心前面兩種方法所可能出現的重複問題。

性能分析圖：

執行力、泛泛而談的了解

泛泛而談

指膚淺的講出看法。浮于表面，沒有深入研究。

——引用自百度百科

泛泛而談其實就是沒有經過太多的思考而就說空話的結果，就像是我們打代碼，拿到題目時剛開始時腦子裡劃過的想法就大都是泛泛而談，就是沒有經過深思，通常是最暴力的解法，非常粗糙，沒有經過任何的推理過程，沒有經過任何的優化而想出的解法，甚至大多時候都是錯誤的解法，是以要經過深思才能下手去開始編碼，而不是想到什麼就些什麼，就是說不能泛泛而談

執行力

執行力是指有效利用資源、保質保量達成目标的能力，指的是貫徹戰略意圖，完成預定目标的操作能力。是把企業戰略、規劃、目标轉化成為效益、成果的關鍵。

執行力包含完成任務的意願，完成任務的能力，完成任務e的程度。對個人而言執行力就是辦事能力；對團隊而言執行力就是戰鬥力；對企業而言執行力就是經營能力。

簡單來說就是行動力。

對于我們來說，執行力的一種表現就是任務要在deadline之前完成，而且越早展現的執行力就越強，就像老師在評分中所提到的問題

• 個人認為大部分問題最終是歸為 “執行力” 問題

  - 你是否打算解決這個問題？

  - 你是打算 現在 開始解決這個問題，還是等等再說吧？

  - 你是否定下一個可衡量的目标，比如每天2小時泡圖書館，具體2小時要如何配置設定？是想想就算了，還是真的去做了？2小時太多？如果你有充分的理由，調整！沒問題！

  - 一件事情是否需要專門籌劃一天或者幾天來做，時間不到就無所謂？

  - 如果“專用”的時間被外界打斷，你要怎麼辦？

  - 如果時間預估錯誤，deadline完不成怎麼辦？

  - 是以能否有一點空閑時間我們就把事情往前推進哪怕隻有一點點？

——引用自【評分】軟體工程實踐2017第一次作業-準備

這些問題我在這裡當然能夠有回答：

• 當然打算解決執行力的問題
• 從現在開始解決這個問題
• 定下了可衡量的目标，雖然不是每天兩小時泡圖書館，而是每天至少會看3小時的書，每天會配置設定好看哪種書的時間（訂了鬧鐘（因為這個學期晚上都沒有選修課而導緻時間配置設定異常簡單粗暴
• 原先預計耗時較長的事情就常常會特意空出一天或者幾天的時間，而且會逼着自己必須要完成
• 如果“專用”的時間被外界打斷，這時候會心很慌，如果不補上的話總覺得心不安，必須要補上，通常會占用原來計劃的休息時間（例如熬夜
• 在老師規定deadline的時候其實自己就會給自己規定一個自己的deadline，在這個deadline之前必須要把任務完成到隻差送出的地步，就像這次作業，寫到這的時候是9月10日0:37，而我給自己的deadline就是9月10日睡覺之前，而且其實這部分是重寫的，最開始對題目的了解有誤，搞的準備睡覺了又從床上爬下來重寫=。=要不然心慌。
• 在有任務的時候就常常有一種壓迫感，在休息的時候也是休息不好的，是以隻要有空閑時間當然就會吧事情往前推進，而為了長期有這種壓迫感，我已經給自己訂了一些計劃并且訂了鬧鐘來提醒自己。

PSP:

||||||

|:--|:--|:--|:--|

|PSP2.1|Personal Software Process Stages|預估耗時（分鐘）|實際耗時（分鐘）|

|Planning|計劃|10|7|

|?Estimate|· 估計這個任務需要多少時間|10|7|

|Development|開發|370|430|

|?Analysis|· 需求分析 (包括學習新技術)|30|30|

|?Design Spec|· 生成設計文檔|20|10|

|?Design Review|· 設計複審 (和同僚稽核設計文檔)|10|10|

|?Coding Standard|· 代碼規範 (為目前的開發制定合适的規範)|20|20|

|?Design|· 具體設計|40|30|

|?Coding|· 具體編碼|120|200|

|?Code Review|· 代碼複審|10|10|

|?Test|· 測試（自我測試，修改代碼，送出修改）|120|120|

|Reporting|報告|80|90|

|?Test Report|· 測試報告|30|80|

|?Size Measurement|· 計算工作量|20|10|

|?Postmortem & Process Improvement Plan|· 事後總結, 并提出過程改進計劃|30|20|

|合計||460|527|

另：雖然沒選上實踐課但請老師不要放棄我QAQ

學習進度條

第N周	新增代碼（行）	累計代碼（行）	本周學習耗時(小時)	累計學習耗時（小時）	重要成長
200		12		從同學們那裡得到了很多的解題思路并學會了系統的優化代碼的方法