天天看點
傳回

個人作業 數獨

Github位址

https://github.com/Donemeb/SudukuProject

ps:名字好像起錯了> <

PSP2.1 估計&實際

PSP2.1 Personal Software Process Stages 預估耗時（分鐘） 實際耗時（分鐘）
Planning 計劃 10 12
· Estimate · 估計這個任務需要多少時間
Development 開發 1610 2350
· Analysis · 需求分析 (包括學習新技術) 40 30
· Design Spec · 生成設計文檔 20 25
· Design Review · 設計複審 (和同僚稽核設計文檔) 5
· Coding Standard · 代碼規範 (為目前的開發制定合适的規範)
· Design · 具體設計 60
· Coding · 具體編碼 1440 2100
· Code Review · 代碼複審
· Test · 測試（自我測試，修改代碼，送出修改） 120
Reporting 報告 95 115
· Test Report · 測試報告 50
· Size Measurement · 計算工作量
· Postmortem & Process Improvement Plan · 事後總結, 并提出過程改進計劃
合計 1715 2477

有很大一部分時間花在調bug上了（捂臉）。一開始沒有仔細記錄好各個參數的具體含義和範圍，過一段時間修改時憑記憶去改那些參數，超容易産生各種小bug。

需求分析

  • 指令行形式
  • 9*9 數獨生成，首位為特定數字
  • 9-9 數獨求解

設計思路

先說說等價數獨。一個數獨終局通過各類變換可以生成超大量的等價數獨。但是，由于題目中提到了不重複原則，假使要求生成的數獨數量大于一個等價數獨組，那麼查重部分就會消耗大量的時間，反而得不償失。也沒有找到一個能識别不同等價數獨的特征。便放棄了這個想法。

不考慮等價數獨，數獨的生成和求解，在本質上都可歸為求解數獨的過程，隻不過生成相對于全0的數獨求解，且不會因得出一個解答停止。

第一個想到的方法，大約也是最簡單粗暴的方法，就是無腦遞歸周遊，輸出可行解。通過每次檢查插入是否可行來決定往下一層or繼續嘗試，但同時想到，檢查插入的可行性本身是一個極占運作比重的部分，即使可以一次計算出一個遞歸過程中的所有可填入值，單純通過數獨局來周遊仍會占去大量運作時間。于是開始考慮如何存儲每次遞歸過程沖突資訊，以快速檢查插入的可行性。

由于也是一個回溯算法，加之判斷沖突，便聯想到了N皇後問題。在查找資料的過程中，這篇部落格給了我很大啟發。通過劃分沖突種類，以0|1方式表示沖突與否，很大程度上減少了建立、回溯沖突表本身，以及沖突表使用所花費的時間。同時這個方法特别适合在一次填完一個數字的回溯方法中使用。這也就是我之後程式的基本思路。

最終的設計思路：一次填完一個數字，每個數字按第一行往第九行的順序填入，沖突表有三個：列沖突表[每個數字]，九宮格沖突表[每個數字]，整體的數獨沖突表

具體實作

建立一個suduku類，提供生成、解數獨方法。

  • sudu_generation 生成的入口方法
    • sudu_gene_init 初始化開局（決定回溯順序、确定首位為5）
    • sudu_gene_loop 遞歸函數
      • sudu_insert_0 沖突表插入
      • sudu_delete_0 沖突表回退
  • sudu_solve 解答的入口方法
    • sudu_solve_new
    • sudu_solve_init初始化開局
    • sudu_solve_loop 遞歸函數
  • sudu_to_file 數獨寫入檔案

單元測試

有很多是private方法，難以從外部調用。測試函數采用調用入口函數，檢查數獨終局的正确性的方式來進行測試。另有指令行輸入的數字的合法性的檢測。

個人作業 數獨

代碼優化

生成部分的代碼寫完後，迫不及待的試了一試——1s、10s、100s...當我終于忍不下去了強制結束程式時，不過輸出了20w個數獨。問題很快就發現了：檔案IO。當時采用的是一個數字一個數字輸出到檔案的方式，極其拖慢性能。之後我為其申請了一個輸出到檔案的buf，每次調用sudu_to_file時先将輸出暫存在buf中，等buf快滿了，一次性輸出到檔案。在程式結束前再調一次sudu_to_file_flush來将還在buf中的資料輸出到檔案。

接下來做了一些小優化。删去了代碼中的一些多餘的計算等。

  • 代碼性能圖

    數獨生成

    個人作業 數獨
    數獨求解
    個人作業 數獨

可以發現函數消耗的比例很相似，因為解答時基本使用的是同一個算法。

  • 100w生成測試

    在我的電腦上，release版本，生成100w數獨的時間在6s上下。

  • 消耗最大的函數

    即回溯過程

void sudu_gene_loop(int order, int & now_num, int target_num) {
		int canset = 0;
		int depth = order % 9;
		int order_num = order / 9;
		int num = rand_num_order[order_num];//ATTENTION 是否可以直接除
		int i;
		if (order == 0) {
			sudu[0] = num + 1;
			gene_row[num] = gene_row[num] | 0400;
			gene_hasput[depth] = gene_hasput[depth] | 0400;
			gene_33[0] = 0700;
			sudu_gene_loop(order + 1, now_num, target_num);
		}
		else {
			if (now_num == target_num) return;
			canset = gene_row[num] | gene_hasput[depth] | gene_33[order_num * 9 + depth / 3];
			for (int i1 = 1; i1 < 10; i1++) {
				i = rand_posi_order[order * 9 + i1 - 1];	//change the name of i
				if (!(canset & x1[i])) {
					//放入資料表
					if (order == 80) {
						sudu[depth * 9 + i] = num + 1;
						sudu_to_file();
						sudu[depth * 9 + i] = 0;
						now_num++;
						return;
						//	sudu_out << now_num;
						//輸出到檔案 //ATTENTION 考慮緩存、效率 
					}
					//更新沖突表 
					sudu_insert_0(i, num, depth, order_num);

					sudu_gene_loop(order + 1, now_num, target_num);

					if (now_num == target_num) return;

					sudu_delete_0(i, num, depth, order_num);
				}
			}
		}
	}
  • 代碼覆寫率
    個人作業 數獨

代碼說明

回溯中判斷可行操作的關鍵代碼（即沖突表的使用）：

canset = gene_row[num] | gene_hasput[depth] | gene_33[order_num * 9 + depth / 3];
	for (int i1 = 1; i1 < 10; i1++) {
		i = rand_posi_order[order * 9 + i1 - 1];	//change the name of i
		if (!(canset & x1[i])) {
			//放入資料表
			…………

沖突表的插入：

num是目前插入的數字(0-8)，i是列數，depth是行數，order_num是總回溯中的順序(0-80)

ps:由于在一開始随機了各種順序參數（下面的其他會說到，是以記錄了回溯順序）

void sudu_insert_0(int i, int num, int depth, int order_num) { 
		sudu[depth * 9 + i] = num + 1;
		gene_row[num] = gene_row[num] | x1[i];
		gene_hasput[depth] = gene_hasput[depth] | x1[i];
		if (depth < 3) {
			if (i <= 2) {
				gene_33[order_num * 9 + 0] |= 0700;
			}
			else if (i <= 5) {
				gene_33[order_num * 9 + 0] |= 0070;
			}
			else if (i <= 8) {
				gene_33[order_num * 9 + 0] |= 0007;
			}
		}
		else if (depth < 6) {
			if (i <= 2) {
				gene_33[order_num * 9 + 1] |= 0700;
			}
			else if (i <= 5) {
				gene_33[order_num * 9 + 1] |= 0070;
			}
			else if (i <= 8) {
				gene_33[order_num * 9 + 1] |= 0007;
			}
		}
		else if (depth < 8) {
			if (i <= 2) {
				gene_33[order_num * 9 + 2] |= 0700;
			}
			else if (i <= 5) {
				gene_33[order_num * 9 + 2] |= 0070;
			}
			else if (i <= 8) {
				gene_33[order_num * 9 + 2] |= 0007;
			}
		}
	}

沖突表的回退：

插入的逆過程

void sudu_delete_0(int i, int num, int depth, int order_num) {
		//ATTENTION 是否考慮回退模式？棧存儲？ 而不是再計算一遍 
		sudu[depth * 9 + i] = 0;//放入資料表
								//更新沖突表 
		gene_row[num] = gene_row[num] & (~x1[i]);
		gene_hasput[depth] = gene_hasput[depth] & (~x1[i]);
		if (depth < 3) {
			if (i <= 2) {
				gene_33[order_num * 9 + 0] &= 0077;
			}
			else if (i <= 5) {
				gene_33[order_num * 9 + 0] &= 0707;
			}
			else if (i <= 8) {
				gene_33[order_num * 9 + 0] &= 0770;
			}
		}
		else if (depth < 6) {
			if (i <= 2) {
				gene_33[order_num * 9 + 1] &= 0077;
			}
			else if (i <= 5) {
				gene_33[order_num * 9 + 1] &= 0707;
			}
			else if (i <= 8) {
				gene_33[order_num * 9 + 1] &= 0770;
			}
		}

		else if (depth < 9) {
			if (i <= 2) {
				gene_33[order_num * 9 + 2] &= 0077;
			}
			else if (i <= 5) {
				gene_33[order_num * 9 + 2] &= 0707;
			}
			else if (i <= 8) {
				gene_33[order_num * 9 + 2] &= 0770;
			}
		}

		sudu[depth * 9 + i] = 0; 
	}

數獨、沖突表的初始化：

void sudu_solve_init() {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				if (sudu[i * 9 + j] != 0) {
					sudu_insert_0(j, sudu[i * 9 + j] - 1, i, sudu[i * 9 + j] - 1);
				}
			}
		}
	}

其他

  • 一個無聊的功能。因為之前以為要生成随機數獨，是以給寫了些rand函數随機了一下回溯順序。後來發現沒必要，它也隻是在開始時運作一次，并不耗什麼時間，也就一直留了下來。是以每次生成數獨時得到的數獨基本是不一樣的（同次的數獨仍是由一個回溯順序生成）
  • 一開始時求解數獨時使用了最簡單的回溯法，後來改成類似生成的算法後，在測試中卻發現仍是最開始的方法性能較優。暫時未找到原因。
上一篇: 個人項目作業-數獨生成與求解
下一篇: [2017BUAA軟工]結對項目