2017軟件工程實踐第二次作業

1、 項目地址：https://github.com/one-piece-zero/sudoku

2、PSP表格記錄的估計耗時

3、解題思路：

• 在拿到這個題目的時候，我最早想到的是大一下學期做的程序語言綜合設計實踐中的N皇后問題，這兩個題目之間有許多的類似之處，行列不能重復，對于這次的題目來說，宮內的數字不能重復，對于N皇后問題來說，斜線部分不能重復。于是我拿起了大一時的解題報告來與這個題目一起分析。首先，對于左上角數字是固定的，那么就可以初始化左上角的數字，然后從第一行的后八位，運用srand函數產生的隨機數，運用random_shuffle函數隨機排列，第一行的數字分好之后，就從第二行的第一個數開始，隨機產生，通過標記flag的值來判斷是否與上下左右有所重復，若有所重復，則跳出循環，另取數重新開始，而宮內的數字則通過與前后左右還有3這個倍數的關系來進行檢測，這個題目中，我用到了回溯法，當遇到沖突時，就返回上一個步驟，去新數來填，直到整個數獨矩陣完成，N皇后問題當初也是用的回溯法解決的，在這次實踐中又用到了，還是有所收獲的。

4、設計實現過程：

• 在開始的時候，拿到這個題目，想到了當初的N皇后問題，所以理所當然的想到了回溯法，在這次的代碼中，我只寫了一個函數，這個函數是用來完成整個數獨的，我在主函數中先將數獨矩陣的第一行完成，接著調用函數，在函數中采用回溯法一步一步完成整個數獨矩陣。

5、代碼說明

主要思路在注釋中有體現

6、運行測試

7、性能分析圖

• 從圖中可以看出，在這次代碼中有兩個函數，main主函數和find函數，而明顯的主函數占用的CPU要遠遠高于find函數，而此次使用了回溯算法，所以時間復雜度會較搞一些，對于較大的數字會處理的較慢些。

8、PSP表格記錄的實際耗時