1.5 ms 解出數獨的簡易程式解法

 

朋友傳了一個數獨的題目給我, 這應該算是一個相當難的題目. 原題如下 :

6						4		5
		8	2
					6		1
4		7
			1				2
		6				7	8
				5	4
			9

 

很明顯的,超多的空格, 意味著會有一些需要猜測. 所以這一題會很難. 我不想花時間去手動解, 又很好奇, 空格這麼多, 是不是會有多數解 ? 所以, 我們會需要一個程式, 可以跑出所有的解法.

數獨的解法, 曾經是一個流行的題目. 主要的關鍵字, EXACT COVER Problem, DLX, Dancing Link, Algorithm X, 都可以找到許多有用的資料. 和這些解法來比, 這邊提出來的解法, 只能說是簡單,直覺,一個普通人的解法, 有興趣的可以參考.

一個直覺的解法

數獨的解決過程, 可以分成推論和猜測以及判斷三個部分. 以下簡單的說明：

推論：

根據數獨的規則, 我們要對每一格, 所對應到的列, 行, 區塊, 計算它的可以填入數字的集合. 而這個格子的可填入數字, 就是行,列,區塊, 的交集. 譬如說, 第 7 列, 第 4 行, 這一格, 所對應到的 第 7 列, 第 4 行, 第 8 個區塊, 他們的可填入數字, 分別是 第 7 列 { 1, 2, 3, 4, 5, 9}, 第 4 行 { 3, 4, 5, 6, 7, 8 }, 第 8 區塊 {  2, 3, 6, 7, 8 }, 這幾個集合的交集是 { 3 } , 所以 S[7][4] 這一格的答案是 3.

猜測：

6						4		5
		8	2
					6		1
4		7
			1				2
		6	3			7	8
				5	4
			9

 

這一個階段, 已經沒有前述可以推論得知的答案, 考量 S[1][4], 第 1 , 第 1 列的可行解是 { 1, 2, 3, 7, 8, 9 }, 第 4 行的可行解是 { 4, 5, 6, 7, 8 }, 第 2 區塊的可行解是 { 1, 3, 4, 5, 6, 7, 8, 9}, 所以 S[1][4] 這一格的可行解是 { 7, 8 }, 我們暫時沒有線索可以判斷應該是 7 還是 8. 所以這時就需要去猜測. 猜測的方式是把題目分成兩個子題. 既然是猜測, 就有可能是錯誤, 所以會需要判斷.

判斷：

6			7			4	3	5
		8	2				7
			4
			8		6		1
4		7	5				6
			1				2
		6	3			7	8
			6	5	4		9
			9

 

考量 S[3][8] 這一格, 第 3 列的可行解是 { 1, 2, 3, 5, 6, 7, 8, 9}, 第 8 行的 可行解是 { 4, 5}, 第 3 區塊的可行解是 { 1, 2, 6, 8, 9}, S[3][8] 這一格的可行解是沒有. 原因是我們在前面的猜測錯誤, 這一個子題不存在解決方案.

一般的數獨的解決過程, 就是重複推論, 猜測, 判斷的過程. 也是最直覺的解法.

資料表示 :

從以上的這三個部份, 我們可以發現, 解題的過程, 就是在列, 行, 區塊的可行解的操作運算, 為了避免重複無意義的計算, 我們要把這些資訊記錄下來. Row/Column/Block 分別用來表示列, 行, 區塊的可行解. 由於可行解是 1-9 的數字集合, 並且只有存在及不存在兩種狀況, 因此用一個 unsigned short.  另外每一格的解決進度, 也會記錄下來.  接下來說明如何用這個資料結構來進行操作.

typedef struct tagSUDOKU_BOARD
{
    char Pattern[CELL_COUNT + 1];                       // For displaying
    unsigned short CellSet[CELL_COUNT];              // For Cell status tracking

    unsigned short RowSet[DIGIT_COUNT];             // Row possible set
    unsigned short ColumnSet[DIGIT_COUNT];        // Column possible set
    unsigned short BlockSet[DIGIT_COUNT];           // Block possible set
}    SUDOKU_BOARD, *LPSUDOKU_BOARD;

啟始動作 :

1. 預期的輸入, 是一個 81 個字元的字串, 所以要先把字串轉換成前述的資料表示. 檢查相對應字串的位置, 1~9 的數字代表這個位置已指定, 否則即未指定, 是要解決的部分.
2. 對每一列, 每一行, 每一區塊, 計算它的可行解.

推論動作 :

1. 對每一個格子, 計算它的可行解. 計算方式是對前述列, 行, 區塊, 作位元 AND 運算.
2. 運算結果計算它的位元為 1 的數量. 程式中以查表得出. 數量為 1 , 即為得出的答案.
3. 更新格子的字元表示, 可行解設定為 0. 代表已解.
4. 更新此格子所對應到的列, 行, 區塊可行解.

猜測動作 :

1. 對無法找出推論的子題, 進行猜測.
2. 找出具有最小可行解的格子.
3. 分別指定此格為可行解的其中之一
4. 更新此格子所對應到的列, 行, 區塊可行解.
5. 將此區塊加入待解問題列.

判斷動作 :

1. 對每一個格子, 計算它的可行解. 計算方式是對前述列, 行, 區塊, 作位元 AND 運算.
2. 如果任一未指定格子, 它的可行解為空, 那麼這一個子題就不存在解法.

效率 :

1. 數獨的解出速度, 會大幅度的和題目相關, 這一個題目頗為複雜, 解出的速度應該很有代表性. 一般的題目所需消耗時間不會高於這個時間.
2. 在 NoteBook 上實測, 可以達到 1.54 ms 解完的速度.

下載程式:

https://github.com/lxnick/SudokuSolver