Sudoku 小項目

數獨相關的一個小項目。

Sudoku 小項目 - 軟工第二次作業

Part 1 · 項目相關

• Github 位址: https://github.com/TheSkyFucker/Sudoku
• 項目的更多資訊以及所有開發文檔見 README.md
• 整體過程，Todolist工具: Teambition

• 部分動态

• 撰寫該文時 SourceTree 結構如下：

Part 2 · PSP 表格

Statu	Stages	預估耗時	實際耗時
Accept	【計劃】 Planning	60	100
	—— 估計時間 Estimate
	【開發】 Development	345	1550
	—— 需求分析 Analysis	20	15
	—— 設計文檔 Design Spec		130
	—— 設計複審 Design Review
	—— 代碼規範 Coding Standard		25
	—— 具體設計 Design	30	300
	—— 具體編碼 Coding	180	1000
	—— 代碼複審 Code Review
	—— 測試 Test
	【記錄用時】 Record Time Spent	10
	【測試報告】 Test Report	40
	【算工作量】 Size Measurement
	【總結改進】 Postmortem		45
	【合計】 Summary	585	1735

Part 3 · 解題思路

• 先按做acm題的心态思考了1~2小時，沒想到什麼比較優秀的做法；
• 然後瘋狂搜尋，因為一開始打算做附加題是以搜了不少附加題相關的内容。
• 先是搜到了：矩陣交換法的做法，覺得很機智很快，但是因為所有生成矩陣是等價矩陣是以不想采用這個做法
• 然後搜到了搜尋法，這個比較直覺，除了拉斯維加斯比較有心意，但是普遍效率都不是很好，基本都存在簡單回溯的話确實本來随機性的意義。
• 然後搜到了一個不斷随機每一行的做法，覺得很棒，部落客也測試說很高效，結果實作了一下發現根本做不了，冷靜下來分析了一下才發現是個假算法。。浪費了好多時間。
• 最後還是采取了矩陣交換法，雖然也在項目中實作了所有終盤随機品質很好的回溯法，但是沒有在指令<-c>中實裝，因為測試發現除非隻有幾k的資料要求量，不然時間要好幾十秒乃至若幹分鐘。
• 當時想做附加題是以繼續思考怎麼做終盤，搜到的資料多是在挖空的位置上做文章。

Part 4 · 設計實作

（一）類之間的關系：

（二）代碼組織

• 類：Sudoku、SudokuGenerator、SudokuChecker 在項目 Sudoku 裡
• 類：SudokuTest、SudokuGeneratorTest、SudokuCheckerTest 在單元測試項目 SudokuTest 裡
• 類：ParamChecker、CommandWorker 在項目 Command 裡
• 類：ParamCheckerTest 在單元測試項目 CommandTest 裡
• 主程式 main.cpp 在項目 Main 裡
• 項目 Sudoku，Command 均設為靜态

Part 5 · 代碼說明

（一）内部函數：快速生成

• 主代碼
• 主要思路：通過重編碼數字、行、列從已有的終盤快速生成其它終盤。
• 注釋：邏輯比較簡單，就是找下一個行編碼，列編碼，數字編碼，代碼中有簡單的英文短語注釋。

（二）内部函數：高品質生成

• 主要思路：通過深搜，每次随機能目前格子合法的數字集合中随機一個數字放到目前行、列。
• 注釋：傳統深搜，短語注釋了幾個邏輯塊。

（三）外部架構：指令系統

• 指令系統分為兩個類，一個類是封裝所有指令的參數校驗，另一個類是實作所有指令的功能
• 進而做到能 高效的拓展指令，筆者搭建好架構後在添加指令<-check>以及<-help>途中感覺非常暢通，其它的代碼都被隔開，那種仿佛在一張白紙上工作的感覺相當的棒。
• 整個架構：
• 主程式 根據

  argv[1]

  判斷指令，調用 主程式中相關指令函數段，并負責整個過程中抛出的 exception

• 相關指令函數段：調用 參數校驗，接着調用 指令執行。

• 參數校驗 架構：

• 指令執行 架構：

（四）程式運作

• 基本上所有的不合法輸入都被 單元測試 和 指令系統架構的參數校驗代碼 ban掉了，是以隻展示成功的界面。

• <-help> 指令

• <-c> 指令

  ：測試100w的資料量，筆者本地運作時間大概 1s，CPU為 I7-4720HQ。

• <-check> 指令

  ：檢驗100w的資料量是否有重複，筆者本地運作時間大概6s，CPU為 I7-4720HQ。

（五）改進性能過程

生成改進一

• 最原本的判法是暴力判合法性，但是效率太低了。
• 編寫的複雜的 Sudoku 類是主要為品質最好的 回溯法（SudokuGenerator::BestGenerate） 準備的，内部采用了維護每行、每列、每宮的狀态來維護整個棋盤；
• 可以做到動态維護數獨棋盤是否合法，每次修改格子都隻要花幾個常數的時間，O(1)查詢目前終盤是否有沖突、是否合法等等。

生成改進二

• 一開始 矩陣轉換法 習慣性的用了sudoku 存生成的方案，生成100w資料大概要60秒。
• 性能分析工具分析出Sudoku維護函數調用太多。
• 但是矩陣轉換法由于是直接重編碼，是以不需要維護合法性，換了一下生成100w大概要10秒，提速6倍左右。

生成改進三

• 輸出一開始采取一個個輸出，效率太低。
• 後面把每個棋盤弄成一個字元串然後puts輸出，改進完後生成100w資料大概在 1 秒左右。

校驗改進一

• 把每個棋盤壓成一個string，然後扔進set來判重複。
• 改進後判定100w個棋盤速度大概在 6s左右。

（六）性能分析圖

• 由于設計時就不打算提供非指令行運作，是以性能分析時采用輸入資訊嵌入主代碼的方式。
• 性能分析圖

• 分析資料量 1w，測試結果較理想。
• 按調用數排序，核心函數 std::next_permutation 調用次數 1w 多次，理論上生成1w的資料調用次數無法低于 1w

• 次數最高的函數為系統函數，其次是輸出函數，函數如下：

（六）總結

• 偏工程方面的總結在 README.md 的文檔裡。
• 感覺幾天内學到了好多東西吧，搜了不少東西，從一開始的把自己弄得手忙腳亂，commit的時候一堆東西揉在一起，代碼習慣性的會往打acm題目的風格靠，git裡還有100m+的輸出檔案就commit最後push崩潰才察覺到這個問題，設計了改改了再設計，時常寫不出單元測試偷偷先去寫主代碼最後砸了自己的腳。
• 到後來慢慢熟悉了整個過程，回檔fix bug，先寫單元測試再寫代碼，檢驗檔案無異常再commit和merge，每個功能新開一條git 分支編寫然後merge回dev分支，VS又報錯了也淡定了，exe崩潰了也知道自己可能有野指針或者記憶體洩漏，慢慢感覺到了一絲絲的秩序，雖然這一切還是按照自己臨時搜的一堆資料建構出來的自以為的軟體開發應有的流程Orz..但還是覺得學到了很多吧，也研究了一下怎麼處理異常好一點，最後學了下try throw的那一套邏輯，但是可能姿勢不太對還是搜的資訊還不夠是以也是按照自己的了解建構了目前項目的整個異常系統，函數聲明也會留意要不要const 和throw等等。
• 然後突然發現不會打題了。

End。