软件工程基础课-个人项目-数独
- 一、項目地址
- 二、PSP
- 三、解題思路
- 四、設計實現過程
- 4.1 代碼風格規范
- 4.2 函數關系圖
- 五、程序性能分析及改進
- 六、代碼說明
- 七、單元測試與代碼覆蓋率分析
- 八、項目總結
- 8.1 個人的提升
- 8.2 不足
- 致謝
一、項目地址
代碼托管在了GitHub上，地址：https://github.com/InspAlgo/Personal_Suduku
各位看官大大們記得給我項目點star，我請你們擼代碼！
還有個人項目紀實忠實記錄個人項目開發過程，有很多細節！
二、PSP
| Planning | 計劃 | ||
| ·Estimate | ·估計這個任務需要多長時間 | 10 | 20 |
| Development | 開發 | ||
| ·Analysis | ·需求分析(包括學習新技術) | 60 | 120 |
| ·Design Spec | ·生成設計文檔 | 300 | 120 |
| ·Design Review | ·設計復審(和同事審核設計文檔) | / | / |
| ·Coding Standard | ·代碼規范(為目前的開發制定合適的規范) | 120 | 180 |
| ·Design | ·具體設計 | 120 | 180 |
| ·Coding | ·具體編碼 | 1080 | 1200 |
| ·Code Review | ·代碼復審 | 300 | 60 |
| ·Test | ·測試(自我測試，修改代碼，提交修改) | 300 | 960 |
| Reporting | 報告 | ||
| ·Test Report | ·測試報告 | 60 | 60 |
| ·Size Measurement | ·計算工作量 | 30 | 30 |
| ·Postmortem & Process Improvement Plan | ·事后總結，并提出過程改進計劃 | 180 | 120 |
| <script id="MathJax-Element-8" type="math/tex"> </script> | 合計 | 2560 | 3050 |
三、解題思路
看老師的要求文檔，數獨？用計算機解數獨問題~還要啥代碼分析、性能測試？還要托管在github上，還要用git進行版本控制，還有各種規范，還尼瑪各種數量巨多的要求。。。問題真是超級多啊！畢竟是個小工程項目。
不過總的來說有三個大塊：一是要搞定數獨求解算法，這個是核心；二是代碼測試、性能分析，與我們之前寫類似OJ的算法習題不同，這個是一個正式的軟件編程的必要部分；三是進行版本管理以及項目規范，這是從項目工程角度指導設計及編寫代碼進行軟件開發的，也是軟件工程學科的意義所在。在我看來這次個人項目考量的基本上是這三點了，接下來是具體步驟。
1. 首先有問題找搜索引擎，搜索數獨 計算機 算法等關鍵詞。這一步是要初步了解問題的樣子，先看看前人可有相關經驗可以借鑒，好讓心里有個譜，關鍵是了解是否有相關算法的存在。
在知乎上，我看這幾篇寫的很不錯：
數獨求解算法
暴力算法之美：如何在1毫秒內解決數獨問題？| 暴力枚舉法+深度優先搜索 POJ 2982
數獨求解算法Kotlin版
成為數獨高手有哪些好的訓練方法
推薦的：
Solving Every Sudoku Puzzle
Sudoku solving algorithms
在谷歌、必應上找的：
數獨高效完全解生成算法的研究和實現
算法實踐——舞蹈鏈（Dancing Links）算法求解數獨
跳躍的舞者，舞蹈鏈（Dancing Links）算法——求解精確覆蓋問題
[buaa-SE-2017]個人項目
算法：
2. 這里過程跳一下，在寫代碼前，我要先看看關于github和git的使用，因為要求文檔里說要看我們的commit情況，emmmm，這樣我就要先建倉庫啊，可這我也不會啊，于是又要找教程，這個也簡單，隨便搜索一下就有入門教程，我也按教程先創了倉庫，具體可以看我的個人項目紀實。
3. 應該講一講關于代碼測試與性能分析方面的了，不過考慮到這是項目后期問題，為了節省時間，我們先完成核心算法，先快速搞出項目原型，然后再來看這個問題，再一邊學一邊弄。
然后是關于具體算法的解題思路，看了那么多介紹數獨求解方法，感覺好多都看起來復雜度好高，還有隨機化方法的，不過個人感覺隨機化方法應該是不可取的，因為你無法判斷是否有重復的情況出現，難不成又弄個哈希再檢測一下？那樣挺占用內存的，畢竟壓力測試時可是有100萬的數據量；然后最直接的方法就是暴力回溯了，因為我們知道1~9這就九個數必定要出現，那么生成終局問題就變成了給數字排位置問題，首先給九個1排，再給2排，再給3排……依次類推，最后排到9。每給一個數排好位置我們就要進行遞歸，因為遞歸操作很方便我們回溯，我們在排數字時，肯定會遇到排不了的情況，這時候我們就要返回上一步重新排數字，再不行就再返回。求解數獨的算法也基本相同，只不過只需要生成一個終局即可，我們可以把返回條件改為是否有解，因為不是所有的數獨題都是有解的，也可能出現無解的情況，這個我現在無法確定所以不能忽略無解的情況。具體算法的偽代碼可參見我的個人項目紀實或者后面的代碼說明。
四、設計實現過程
4.1 代碼風格規范
由于本部分內容較多，故重新寫了篇博文，詳見軟件工程基礎課-個人項目-代碼風格規范。
里面的內容主要摘自Google C++風格指南，同時在個人項目中盡力以此為風格標準，可能個別地方不一致。
4.2 函數關系圖
程序基本流程圖為：
Created with Rapha?l 2.1.2 開始 輸入指令 分析指令 求解數獨 輸出 結束 生成終局 yes no函數關系圖由VS自動生成
五、程序性能分析及改進
通過性能分析圖可以看出來我的檢查函數占比較多，因為是暴力回溯所以每一步都要判斷是否有重復、不符合規則的數字出現，而每次判斷都要用循環遍歷，這個就很耗時了，我是已經作了優化的，將橫豎分別循環判斷改成了同時循環判斷，emm，沒想到還是比較耗時間。還有一種方法就是加個位置記錄，具體方法是這樣，比如num_row[num][i]代表數字num在第i行是否有出現，同理num_col[num][j]代表數字num在第j列是否有出現，num_box[[num][row][col]代表數字num是否在第[row][col]小九宮格上有出現。這樣就不需要用循環判斷了，填數字了就賦值為false，剛開始沒數字時是賦值為true的。
然后試驗了一下
如下圖可以看出C策略函數的檢查降到800的量級，之前還是4000的量級
這次改進還是有效果的，連檢查函數我都刪掉了，因為這種寫法的話判斷語句就太短了。不過需要注意的就是在合適的位置還原為true。
在基本完成程序后又重新進行了一下性能分析，結果見下。
其中消耗最大的函數為strategyC，其具體情況為：
與之前性能分析比較有一定的時間延長，在本機測試時發現會出現一定的時間波動。
六、代碼說明
我主要使用的是暴力回溯法生成數獨的，求解數獨同理。
我們看一下這個規則，會發現一個規律，就是第一行有數x后不能再有x，它一定會依次出現在后面的行，同理列也一樣，然后其他數也是這樣。那么我們如果按數字順序在第一個小方格內填入1，然后再在第二行某個格填入1，依次類推直到填完9種數，到這里有人會說這樣遲早會產生沖突，出現不符合規則的局面，沒錯，的確會這樣，那么我們就從試不了的地方開始回溯，換個數繼續試，直到滿足位置，這里有時候會回溯好幾步才能成功，不過計算機比較快，尤其是用遞歸實現起來還是相當快的了。
用偽代碼描述：
這個算法的出口就是你要生成多少終局。
七、單元測試與代碼覆蓋率分析
總共設計了13個測試，覆蓋率為88.33%，接近90%，已達個人預期的80%。
單元測試主要針對輸入的判斷作了較多的測試，因為程序首先要能分析命令行指令的正確性，設計了2組正確輸入也設計了3組錯誤輸入，對參數分析作了比較完備的測試，對類的構造函數也進行了測試以判斷初始化情況，對儲存數組、生成數獨、求解數獨、輸出數獨等核心模塊也都分別設計了測試。具體內容可以參見測試代碼，不過需要注意單元測試時要將sudoku.h文件中Sudoku類的private注釋掉，因為我的類數據成員原本全私有，且不少方法封裝的可能有點緊湊不好切入斷言，故為了單元測試方便，需要改成公有。注意、注意、注意使用我的單元測試時一定要將私有改公有！！！
八、項目總結
本次個人項目歷經十余天，遇到了許多奇奇怪怪的bug，感覺不再是對代碼能力的考驗了而是對意志力的磨練。
8.1 個人的提升
面向對象思想
第一次正式使用VS構建C++工程，使用多文件進行對項目分模塊化，而不再像之前是單文件模式，模塊化構建使自己的思路與邏輯更加清晰，并且配合C++類的封裝等面向對象的編程思想使得代碼結構也更加清晰。這也讓我感受到了面向對象編程的優秀之處，我們的世界本身就是物物的作用關系，而對象則是物物的代碼抽象化，而作用關系則是方法，我們的世界中有顯性的作用關系，也有隱性的，而宏觀物的內部也有更加具體的微觀物，這就是公有與私有、類與成員的關系。
工程能力
什么是工程？個人認為工程是綜合、是規范。綜合說明了實施的過程必然是繁瑣的，有一定量的，需要的知識也是多方面的，軟件工程亦是如此，在本項目中，要學習C++的一些特性，還要熟悉VS的一些使用技巧，尤其是編寫代碼時要思考該怎么使用算法？要思考應該如何具體實現。規范則說明了代碼不是隨便編寫的，例如首要的就是代碼風格規范，有一個良好的風格規范一方面是便于閱讀，另一方面則是使代碼邏輯更加嚴謹，減少了不必要的錯誤。規范還體現在單元測試，之前的程序練習要求能跑就好，沒有多少真正的測試，而軟件開發的單元測試也對應了一般意義上的工程開發，像建樓房，有各種驗收審查，各個部分的檢驗，而這就是代碼的各個模塊，單元測試是軟件的一質量測試，雖實現不同但意義是一樣的。
模仿與學習
在本項目中，很多東西都是自己以前沒有遇到過的，沒有任何經驗，只能模仿別人的方法，并通過模仿來學習自己未知的知識與經驗。在這里，非常感謝一位北航學長，他的項目給我很多啟發與靈感，在模仿他的一些方法的過程中學習到了很多，減少了很多彎路。模仿是學習的一種基礎，先模仿獲得初步的經驗，有了經驗我們才能更好的反思與改進，沒有天生就會的，而有了足夠的經驗我們才能夠創新與創造。
這次的個人項目對模仿與學習能力有極大的考驗，在此之前都沒有過比較深入的看官方文檔的經歷，學會如何看文檔、技術博客，從中獲取自己所需要的知識與經驗是一種屬于成長式的能力，這種能力將會伴隨我們終身并成為我們終身學習的關鍵一環。
8.2 不足
個人
英文水平有待提高，在看文檔的時候習慣性將網址的en-us改成zh-cn，要是沒有就會啟動網頁翻譯，博客也是中文博客，沒有養成在Stack Overflow上尋找解析的習慣。對待問題總是沒有徹徹底底解決的感覺，不過這個涉及的能力實在不知道該怎么說了。注意力目前還是放在了工具的使用上了，作為一名軟件開發人員，我們不光要會使用輪子，更要明白輪子的構建，以及軟件開發方法。
項目本身
例如程序本身的穩定性方面沒有做過較多的研究，像程序生成100萬數獨終局的時間就有一定的波動，沒有將其壓到一個較低的穩定值，也沒有做多平臺測試，只是在個人的Win10 x64上進行了測試。也沒有去完成項目的附加題——界面程序，這個是感覺很耽誤時間，這段時間要有許多科目的學習，不能將時間全砸在軟工的項目上，如果是小學期課程就會好很多，沒有其他課程的干擾，可以一心一意的撲在項目上。
課程設計
這個個人項目應該有討論群的，應該有多位助教幫忙答疑解惑。畢竟我們這是本科二年級的課程，縱然我們有一定的自學能力，但是有人指導和沒人的捉瞎的感覺是不一樣的。老師在課上也應該及時評閱同學的個人項目，例如中期點評啥的，這樣可以避免很多不必要的錯誤，或者舉一些實際的例子給我們演示一下，而不是照著課本講一些目前對我們來說的很宏觀的方法，工廠都有師傅帶徒弟進行實操練習，這個課也應如此，講結構設計就應該給個完整的實際例子，而不是像書上那樣的言簡意賅，非常抽象，講白盒測試、黑盒測試就應該給個具體例子、具體測試工具演示一下到底是怎么弄的，只講宏觀的東西是很難弄明白的。
致謝
[buaa-SE-2017]個人項目
感謝北航辛學長的項目給了我很多靈感與經驗，讓我少走了許多不必要的彎路。通過學長的代碼學習到了C++面向對象編程的基本方法，同時其簡潔優美的代碼風格與技巧讓人留戀與難忘！
Visual Studio 文檔
感謝微軟的官方文檔，讓我在面對各種奇奇怪怪的錯誤與警告提示時有了一些基本概念與策略，同時通過文檔也初步學習與掌握了單元測試方法等。其言簡意賅的描述讓人刻骨銘心！
【算法研究】數獨高效完全解生成算法的研究和實現、帶你玩轉Visual Studio——性能分析與優化、Git 中忽略某些文件或者文件夾······
這里無法一一列舉參考過的博客，感謝大佬們的經驗分享，讓我在痛苦與絕望時看見了希望的光火！其開源分享的精神讓人感動！
感謝老師與同學，這次的個人項目對個人確實有所歷練，大概能夠理解老師的用意！
總結
以上是生活随笔為你收集整理的软件工程基础课-个人项目-数独的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： vue3+Typescript---Co
- 下一篇： 第二次迭代总结