生活記事簿: 6月 2026

2026年6月20日星期六

數獨求解 Java 實現三部曲 - 第三部 - 數獨求解器的 Java 實現

數獨求解 Java 實現三部曲：

經過上次兩篇文章後，我們知道了如何使用 AlgorithmX 來解 Exact cover 問題，並也知道了如何使用 DLX 的方式用程式實作解法後，今天我們要開始把學到的方法用來解數獨問題。

首先我們要把數獨問題轉成 Exact cover 問題，
只要得到了對應數獨的 Exact cover 矩陣後就可以用解 Exact cover 的方式來解數獨。

數獨的規則有四個約束 (constraint) 如下：

相同的格子 (cell) 只能有一個數字，例如一個 cell 如果是 1 就不能是 2~9 其他數字。
相同的 row 中相同的數字只能有一個，例如 row 1 上只能有一個 1、只能有一個 2 等。
相同的 column 中相同的數字只能有一個，例如 column 1 上只能有一個 1、只能有一個 2 等。
相同的宮 (box, 九宮格) 中相同的數字只能有一個，例如 box 1 上只能有一個 1、只能有一個 2 等。

為了簡化及方便討論，我們這裡先用 4x4 的數獨來討論，之後 9x9 的數獨原理也是一樣的。

4x4 的數獨如下所示，從左到右從上到下我們把各 cell 標上所在的 (row, column)：

(0, 0)	(0, 1)	(0, 2)	(0, 3)
(1, 0)	(1, 1)	(1, 2)	(1, 3)
(2, 0)	(2, 1)	(2, 2)	(2, 3)
(3, 0)	(3, 1)	(3, 2)	(3, 3)

我們把所有 cell 的可能 (可能是 1, 2, 3, 或 4) 和對應的約束關係寫成 exact cover 的矩陣如下，如果符合約束條件的話用 1 表示，不符合就不寫

	(0, 0) 有一個數字	(0, 1) 有一個數字	(0, 2) 有一個數字	(0, 3) 有一個數字	(1, 0) 有一個數字	(1, 1) 有一個數字	(1, 2) 有一個數字	(1, 3) 有一個數字	(2, 0) 有一個數字	(2, 1) 有一個數字	(2, 2) 有一個數字	(2, 3) 有一個數字	(3, 0) 有一個數字	(3, 1) 有一個數字	(3, 2) 有一個數字	(3, 3) 有一個數字	row 0 有數字 1	row 0 有數字 2	row 0 有數字 3	row 0 有數字 4	row 1 有數字 1	row 1 有數字 2	row 1 有數字 3	row 1 有數字 4	row 2 有數字 1	row 2 有數字 2	row 2 有數字 3	row 2 有數字 4	row 3 有數字 1	row 3 有數字 2	row 3 有數字 3	row 3 有數字 4	column 0 有數字 1	column 0 有數字 2	column 0 有數字 3	column 0 有數字 4	column 1 有數字 1	column 1 有數字 2	column 1 有數字 3	column 1 有數字 4	column 2 有數字 1	column 2 有數字 2	column 2 有數字 3	column 2 有數字 4	column 3 有數字 1	column 3 有數字 2	column 3 有數字 3	column 3 有數字 4	box 0 有數字 1	box 0 有數字 2	box 0 有數字 3	box 0 有數字 4	box 1 有數字 1	box 1 有數字 2	box 1 有數字 3	box 1 有數字 4	box 2 有數字 1	box 2 有數字 2	box 2 有數字 3	box 2 有數字 4	box 3 有數字 1	box 3 有數字 2	box 3 有數字 3	box 3 有數字 4
(0, 0) 填 1	1																1																1																1
(0, 0) 填 2	1																	1																1																1
(0, 0) 填 3	1																		1																1																1
(0, 0) 填 4	1																			1																1																1
(0, 1) 填 1		1															1																				1												1
(0, 1) 填 2		1																1																				1												1
(0, 1) 填 3		1																	1																				1												1
(0, 1) 填 4		1																		1																				1												1
(0, 2) 填 1			1														1																								1												1
(0, 2) 填 2			1															1																								1												1
(0, 2) 填 3			1																1																								1												1
(0, 2) 填 4			1																	1																								1												1
(0, 3) 填 1				1													1																												1								1
(0, 3) 填 2				1														1																												1								1
(0, 3) 填 3				1															1																												1								1
(0, 3) 填 4				1																1																												1								1
(1, 0) 填 1					1																1												1																1
(1, 0) 填 2					1																	1												1																1
(1, 0) 填 3					1																		1												1																1
(1, 0) 填 4					1																			1												1																1
(1, 1) 填 1						1															1																1												1
(1, 1) 填 2						1																1																1												1
(1, 1) 填 3						1																	1																1												1
(1, 1) 填 4						1																		1																1												1
(1, 2) 填 1							1														1																				1												1
(1, 2) 填 2							1															1																				1												1
(1, 2) 填 3							1																1																				1												1
(1, 2) 填 4							1																	1																				1												1
(1, 3) 填 1								1													1																								1								1
(1, 3) 填 2								1														1																								1								1
(1, 3) 填 3								1															1																								1								1
(1, 3) 填 4								1																1																								1								1
(2, 0) 填 1									1																1								1
(2, 0) 填 2									1																	1								1
(2, 0) 填 3									1																		1								1
(2, 0) 填 4									1																			1								1
(2, 1) 填 1										1															1												1
(2, 1) 填 2										1																1												1
(2, 1) 填 3										1																	1												1
(2, 1) 填 4										1																		1												1
(2, 2) 填 1											1														1																1
(2, 2) 填 2											1															1																1
(2, 2) 填 3											1																1																1
(2, 2) 填 4											1																	1																1
(2, 3) 填 1												1													1																				1
(2, 3) 填 2												1														1																				1
(2, 3) 填 3												1															1																				1
(2, 3) 填 4												1																1																				1
(3, 0) 填 1													1																1				1
(3, 0) 填 2													1																	1				1
(3, 0) 填 3													1																		1				1
(3, 0) 填 4													1																			1				1
(3, 1) 填 1														1															1								1
(3, 1) 填 2														1																1								1
(3, 1) 填 3														1																	1								1
(3, 1) 填 4														1																		1								1
(3, 2) 填 1															1														1												1
(3, 2) 填 2															1															1												1
(3, 2) 填 3															1																1												1
(3, 2) 填 4															1																	1												1
(3, 3) 填 1																1													1																1
(3, 3) 填 2																1														1																1
(3, 3) 填 3																1															1																1
(3, 3) 填 4																1																1																1

寫出數獨對應 Exact cover 的 Algorithm X 用矩陣後，
就可以套用之前講過的 Dancing Links 求解法求出數獨的答案，
際際上一則數獨會有一些格子已經有填好的數子，而一個已有填好數字的格子不可能會再是其他數字了，
所以上述的矩陣可以先拿掉某些不可能的 row，
例如 (1, 1) 如果已經填好是 1 了，那我們就不需要 (1, 1) 填 2、(1, 1) 填 3 等的 row。

如上所述，我們可以用一樣的方法推導出一個 9X9 的數獨，各個格字是什麼數字時，轉成 Algorithm X 矩陣的 row 的公式如下：

private int[] getDancingLinksRow(int row, int col, int number) {
	    int[] algorithmXRow = new int[9 * 9 * 4]; //4 個約束，各約束有 9 個 column

	    //一個格字 (cell) 需有一個數字
	    int cellConstraint = row * 9 + col;
	    
	    //一個 row 需有一個 1, 2, 3, 4, 5, 6, 7, 8, 9
	    int rowConstraint = 9 * 9 + row * 9 + (number - 1);
	    
	    //一個 column 需有一個 1, 2, 3, 4, 5, 6, 7, 8, 9
	    int colConstraint = 2 * 9 * 9 + col * 9 + (number - 1);
	    
	    //一個 box 需有一個 1, 2, 3, 4, 5, 6, 7, 8, 9
	    int boxConstraint = 3 * 9 * 9 + ((row / 3) * 3 + (col / 3)) * 9 + (number - 1);

	    algorithmXRow[cellConstraint] = 1;
	    algorithmXRow[rowConstraint] = 1;
	    algorithmXRow[colConstraint] = 1;
	    algorithmXRow[boxConstraint] = 1;

	    return algorithmXRow;
	}

有了 getDancingLinksRow() 後，我們就能把一個 9x9 的數獨盤面轉成完整的 Algorithm X 矩陣了，如下：

//將 int[][] board : 數獨的盤面 轉換成 Exact cover 問題的 Algorithm X 矩陣
	private int[][] buildSudokuDancingLinksMatrix(int[][] board) {
	    List<int[]> rows = new ArrayList<>();

	    for (int row = 0; row < board.length; row++) {
	        for (int col = 0; col < board[0].length; col++) {

	            if (board[row][col] != 0) {// 如果數獨的某一格已經有一個數字
	                int num = board[row][col];
	                rows.add(getDancingLinksRow(row, col, num));
	            } else {
	                	// 如果數獨的某一格還沒有數字，就產生對應 1~9 各種可能的 Algorithm X 矩陣 row
	                for (int num = 1; num <= 9; num++) {
	                    rows.add(getDancingLinksRow(row, col, num));
	                }
	            }
	        }
	    }

	    return rows.toArray(new int[0][0]);
	}

有了 Algorithm X 矩陣後，就可以用之前介紹的方式找出 Exact Cover 的解，
再把被選為答案的一組 Algorithm X 中的 row 子集
轉換成對應數獨的哪一個格子要填哪一個數字就可以了。

下面分享一下我的實作專案，裡面包括了三種數獨的求解實作，
分別是：

最簡單的 Backtracking 深度查詢遞迴演算法，效能最差，重試錯率很高。
用 Java 物件的方式實作 Dancing links，效能較差，且因為物件、鏈結等處理成本，有時花的時間會比 Backtracking 的時間還久。
用陣列 (pure int array) 的方式實作 Dancing links，效能較好，當數獨盤面的解很多時 (例如數獨一開始的已填好數字很少，存在很多個可能的解答盤面時)，效能比用物件方式實作快很多。

以以下數獨盤面為例，有 8008 個解答：

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

Backtracking ：耗時 20578 ms。
用 Java 物件的方式實作 Dancing links : 耗時 41717 ms。
用陣列 (pure int array) 的方式實作 Dancing links ：耗時 277 ms。

源碼分享：

數獨(Sudoku)解答器.zip

數獨求解 Java 實現三部曲 - 第二部 - 舞蹈鏈 (Dancing Links) (DLX) - 可用來解數獨、8皇后問題(8 Queens, Puzzle) 等問題

數獨求解 Java 實現三部曲：

上篇文章介紹了精確覆蓋問題 (Exact cover) 與 X演算法 (AlgorithmX) ，
在這篇文章中我要來介紹程式面的 X演算法實現方式之一的 舞蹈鏈 (Dancing Links) (DLX)。

Dancing Links 是一個實現 X演算法的一種資料結構，
因為我們常見的精確覆蓋問題，在使用 X演算法解題的時候，
碰到的矩陣通常為稀疏矩陣，
也就是集合 X 和 X 的若干子集的集合 S ，在用 X演算法解題時，
S 組成的矩陣是只有少數 1 的稀疏矩陣。

Dancing Links 在稀疏矩陣的情況下有不錯的效能表現，
其資料結構為：
只紀錄矩陣中為 1 的部份為結點 (node)，結點之間用雙向鏈結 (double links) 連結起來，
這樣就可以很方便的在各結點之間遊走，
也可以很方便的從矩陣中刪除或復原 row 和 column。

下面用一個 X 演算法的矩陣來舉例：

例如 X = {1, 2, 3, 4, 5}

S = {S1, S3, S3}

S1 = {1, 4, 5}

S2 = {2, 5}

S3 = {2, 3}

我們把 S1 ~ S3 組成一個 row, column index 從 1 開始的矩陣，
其中為 1 個組成了各 node，node 可用不重覆的 id 當編號來識別，
node 之間用雙向鍵接串接起來，同 row 中的第一個 node 和最後一個 node 也會接來組成雙向鍵接。
用 row 0 來表示 X 和指向各 column 的 column header，並且紀錄各 column 中 1 的個數，
在同一個 column 中的第一個 node 和最後一個 node 都會跟同 column 的 column header node 連接組成雙向鍵接。
並也紀錄一下各 row 指向的第一個 node。

以上資料結構可以使用單純的陣列 (Array) 來達成，
如果不考慮效能速度的話也可以用類似 Java Class 的方式達成，
雖然在程式可讀上會稍微好一點，但效能速度可能會比使用 Array 慢很多 (兩種實現方式我下面都會有 Java 程式碼做範例)，下面我都以 Java 的 Array 的實現方式來做說明。

資料結構如下所示，我們會有以下變數:

//每一個 node (包括 column header 上的 node) 都有 id，從 0 開始編號，currentMaxNodeId 不斷遞增int currentMaxNodeId = -1;

//紀錄每個 node 上下左右連到哪一個 node，例如 left[3] = 2 代表 nodeId = 3 的 node 的左鍵結連到 nodeId = 2 的 node，right, up, down 以此類推
int[] left, right, up, down;

//紀錄各 node 是屬於哪個 row, column，例如 col[3] = 5 代表 nodeId = 3 在 column 5 上
int[] col, row

//代表各 column 的 1 的 node 的數量，例如 colSize[3] = 2 代表 column 3 中 node 為 1 的數量是 2
int[] colSize;

//代表各 row 的第一個 node 的 id，例如 rowFirst[2] = 3 代表 row 2 的第一個 node 的 id 是 3
int[] rowFirst

畫出來的結構圖就會像是這樣

int[] left = {5, 0, 1, 2, 3, 4, 8, 6, 7, 10, 9, 12, 11};

int[] right = {1, 2, 3, 4, 5, 0, 7, 8, 6, 10, 9, 12, 11};

int[] up = {0, 6, 11, 12, 7, 10, 1, 4, 5, 2, 8, 9, 3};

int[] down = {0, 6, 9, 12, 7, 8, 1, 4, 10, 11, 5, 2, 3};

int[] row = {0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 3, 3};

int[] col = {0, 1, 2, 3, 4, 5, 1, 4, 5, 2, 5, 2, 3};

int[] colSize = {0, 1, 2, 1, 1, 2};

int[] rowFirst = {6, 9, 11};

有了基礎的鍵結結構以後，接下來我們要實作的是

build(int[][] matrix)
將輸入的 matrix 轉成上述的 Dancing Links 雙向鍵結結構。
cover(int colId) :
colId 指 column id，將選定的 column node 從 column header 中移除，並把該 column node 往下有 1 的 row 從矩陣中移除。
uncover(int colId)：
cover(int colId) 的反向操作，將 cover(int colId) 的作用消除，把被移除的 column 及 row 放回矩陣中。
searchSolutions()：
尋找精確覆問題的解。

4 個 function method。

build(int[][] matrix) :
將輸入的 matrix 轉成上述的 Dancing Links 雙向鍵結結構，
直接看程式碼，想關的說明注解已寫在程式碼中：

cprivate void build(int[][] matrix) {
		
		int rowCount = matrix.length;
		int colCount = matrix[0].length;
		
		//包含 column header node 的所有 node 的最大可能數量，
		//因為 matrix 可能是 1 很少的稀疏矩陣，所以實際 node 的數量可能遠小於 rowCount * colCount
		int possibleNodeMaxCount = rowCount * colCount + colCount + 1;
		left = new int[possibleNodeMaxCount];
		right = new int[possibleNodeMaxCount]; 
		up = new int[possibleNodeMaxCount]; 
		down = new int[possibleNodeMaxCount]; 
		col = new int[possibleNodeMaxCount]; 
		row = new int[possibleNodeMaxCount];
		
		//row 和 column 的 index 從 1 開始
		colSize = new int[colCount + 1];
		rowFirst = new int[rowCount + 1];
		
		// 建立 column header node
		do {
			int nodeId = ++currentMaxNodeId;
			
			right[nodeId] = nodeId + 1;
			left[nodeId] = nodeId - 1;
			up[nodeId] = nodeId;
			down[nodeId] = nodeId;
			
			col[nodeId] = nodeId;
			row[nodeId] = 0;
		} while(currentMaxNodeId < matrix[0].length);
		
		left[0] = currentMaxNodeId;
		right[currentMaxNodeId] = 0;
		
		for (int i = 1; i <= rowCount; i++) {
			for (int j = 1; j <= colCount; j++) {				
				//建立 column node 往上下的 node 垂直連結
				//忽略 matrix 中為 0 的 node，只對是 1 的建立 Dancing links node
				if (matrix[i - 1][j - 1] != 1) {
					continue;
				}
				
				int nodeId = ++currentMaxNodeId;
				
				//此時 colHeaderNode.up 就是 column 最下方的 node
				int lastNodeInColumn = up[j];

				row[nodeId] = i;
				col[nodeId] = j;
				
				up[nodeId] = lastNodeInColumn;
				down[lastNodeInColumn] = nodeId;
				
				down[nodeId] = j;				
				up[j] = nodeId;
				
				colSize[j]++;
				
				//建立各 row node 往左右的 node 水平連結
				if (rowFirst[i] == 0) {
					// 如果 node 是該 row 的第一個 node
					rowFirst[i] = nodeId;
					right[nodeId] = nodeId;
					left[nodeId] = nodeId;
					continue;
				}
				// 如果 node 不是該 row 的第一個 node
				int lastNodeInRow = left[rowFirst[i]];
				right[lastNodeInRow] = nodeId;
				left[nodeId] = lastNodeInRow;
				
				right[nodeId] = rowFirst[i];
				left[rowFirst[i]] = nodeId;
			}
		}
	}ode

cover(int colId) :
cover(int colId) 的作用是將選定的 column node 從 column header 中移除，並把該 column node 往下有 1 的 row 從矩陣中移除
，而 uncover(int colId) 是 cover() 的相反操作，會把 cover() 的操作結果復原。

因為我們要遍歷整個鍵結結構時都會先從 column header 開始，
並且為了之後 uncover 時方便，
column 的移除在這裡我們只要把對應 column 的 column node 從 column header 中移除即可，
方法就是把 column header 中的 column node 的左右 node 連結起來。

接下來再從要移除的 column node 往下找到有 1 的 row，把 row 從矩陣中移除，
移除的方法是把 row 為 1 的 node 的上下 node 連結起來，程式碼如下

//將選定的 column node 從 column header 中移除，並把該 column node 往下有 1 的 row 從矩陣中 cover 移除。
	private void cover(int colId) {
		
		//將對應 colId 的在 column header 上的 column node 的左右 column node 連結起來
		right[left[colId]] = right[colId];
		left[right[colId]] = left[colId];
		
		//將對應 colId 的 column node 往下有 1 的 row 從矩陣中 cover 移除
		for (int nodeInCol = down[colId]; nodeInCol != colId; nodeInCol = down[nodeInCol]) {
			for (int nodeInRow = right[nodeInCol]; nodeInRow != nodeInCol; nodeInRow = right[nodeInRow]) {
				down[up[nodeInRow]] = down[nodeInRow];
				up[down[nodeInRow]] = up[nodeInRow];
				colSize[col[nodeInRow]]--;
			}
		}
	}

例如如果我們要執行 cover(1) 的話，圖形表示就會如以下：

可以注意到：

我們並沒有修改 node 1 的左右連結，這樣之後要把 column 1 uncover 放回矩陣時就會可以很方便地把 node 1 的左右 node 跟 node 1 連起來即可。
即：
```
right[left[colId]] = colId;
left[right[colId]] = colId;
```
另一個是我們沒有必要修改 node 6 的上下連結，因為 node 6 位於的 column 1 在矩陣中已經是不可見的狀態了，
而且之後要把 cover(1) 的行為還原時 (即把因為 cover(1) 而從矩陣中移除的 row 放回去)，也可以很方便地從從 node 1 往下找到 node 6，再從 node 6 往右找到同一 row 上的 node，把 node 的上下 node 跟 node 連結起來即可。
即：
```
for (int nodeInCol = down[colId]; nodeInCol != colId; nodeInCol = down[nodeInCol]) {
			for (int nodeInRow = right[nodeInCol]; nodeInRow != nodeInCol; nodeInRow = right[nodeInRow]) {
				down[up[nodeInRow]] = nodeInRow;
				up[down[nodeInRow]] = nodeInRow;
				colSize[col[nodeInRow]]++;
			}
		}
```

於是我們也知道了 uncover(colId) 的實驗方式如下

uncover(int colId)：

//cover(colId) 的反向操作，
	//將因 cover(colId) 而被 cover 掉的 column node 往下的 node 往右的 node 都重新放回矩陣中，
	//並把 colId 的 column node 重新放回 column header 中。
	public void uncover(int colId) {

		right[left[colId]] = colId;
		left[right[colId]] = colId;
		
		for (int nodeInCol = down[colId]; nodeInCol != colId; nodeInCol = down[nodeInCol]) {
			for (int nodeInRow = right[nodeInCol]; nodeInRow != nodeInCol; nodeInRow = right[nodeInRow]) {
				down[up[nodeInRow]] = nodeInRow;
				up[down[nodeInRow]] = nodeInRow;
				colSize[col[nodeInRow]]++;
			}
		}
	}

searchSolutions()：
有了 build(int[][] matrix), cover(int colId), uncover(int colId) 後，
我們就可用程式碼實作尋找精確覆蓋問題的解，程式碼的部份如下所示，
說明也已直接注解在程式碼中，
執行完 searhSolutions() 後，我們會得到一個
List<List<Integer>> solutions = new ArrayList<>();
代表已找到的多組解，
solutions 裡面的其中一個解
List<Integer> solution
代表這組解中的已選 row。

// 搜尋精準覆蓋問題的解答
    private void searchSolutions() {
    	//如果 node 0 的 right 就是它自己，代表矩陣中已經沒有 column 的 "1" 情況未被已選為解的 row 覆蓋到了，即已找到了一組解答。
    	//可能還有其他解答，所以之後會經由 return 回到上一步繼續選取其他 row 看是不是解答。
    	if (right[0] == 0) {
    		solutions.add(new ArrayList<>(solution));
    		return;
        }
    	
    	//選擇一個我們想要求解覆蓋 "1" 情況的 column，
    	//選哪一個 column 不重要，因為如果有解的話，任何 column 的 "1" 情況都至少一定會有一個 row 可以覆蓋到它。
    	//所以 chooseMinSizeColumn() 不是必要，
    	//但它可以幫助我們減少搜尋的時間，因為鏈結往下為 1 的 node 至少有一個 row 是解，
    	//所以選擇鏈結往下最少 node 的 column 可以比較快找到是解的 row。
    	int chosenCol = chooseMinSizeColumn();
        cover(chosenCol);
        
        //照由上往下的順序選擇此 column 的其中一個 row 做為答案的一個 row，
    	//此 row 可覆蓋到此 column 的 "1" 情況。
        for (int nodeInChosenRow = down[chosenCol]; nodeInChosenRow != chosenCol; nodeInChosenRow = down[nodeInChosenRow]) {
        	//將選為解的 row 放入 solution 中，
        	//這裡的 row[nodeInChosenRow] 是從 1 開始的，所以要 -1 才對應一開始傳入的 matrix 的 row index，
        	//例如 rowId = 1 代表 matrix 的 row index 0
            solution.add(row[nodeInChosenRow] - 1);

            //cover 被選為解的 row 上各 node 所處的 column (不包括處於 chosenCol column 上的 node)，
            //代表被選為解的 row 上各 node 所處的 column 的 "1" 情況已經被覆蓋掉了
            for (int node = right[nodeInChosenRow]; node != nodeInChosenRow; node = right[node]) {
            	cover(col[node]);
            }

            //繼續選擇下一個 "1" 的情況還未被覆蓋到的 column，繼續尋找其他為解的 row。
            searchSolutions();

            //已經找到一組解答 或 沒有找到解答，之後經由 return 回到這裡。
            //將剛選為解的 row 從 solution 中移除
            solution.remove(solution.size() - 1);

            //還原上面的 cover(col[node]) 的操作。
            for (int node = left[nodeInChosenRow]; node != nodeInChosenRow; node = left[node]) {
                uncover(col[node]);
            }
            
            //在 for loop 中選擇下一個可覆蓋 column "1" 情況的 row 為解
        }
        
        //只有以下情況才會走到這裡：
        //1. 已經找到一組解答 或 沒有找到解答，之後經由 return 回到這裡。
        //2. 此被選擇的 column 無正確的 row 可以選擇覆蓋到此 column "1" 的情況，即沒有找到解答，上面的 for loop 等於沒有執行，直接到這裡。
        //在這復原 cover(chosenCol) 的操作，
        uncover(chosenCol);
    }

現在我們已經了解了運用 Dancing Links 求解精確覆蓋問題的 Algorithm X 和實作的程式了，
接下來就可以運用在數獨的求解上了，
在下一篇文中，我會介紹如何用 Dancing Links Algorithm X 求解數獨和程式實作，
程式碼會一起在下一篇文章中分享。

數獨求解 Java 實現三部曲 - 第一部 - 精確覆蓋問題 (Exact cover) 與 X演算法 (AlgorithmX)

最近在玩數獨 (Sodoku)，在找相關資料時讀到了跟數獨有關的數學問題：
精確覆蓋問題 (Exact cover) 和它的其中一個蠻不錯的解法：AlgorithmX
還有實現 ALogrithm X 的 Dancing Links (DLX) 程式解法，
可以用來解數獨、8皇后問題(8 Queens, Puzzle)等問題，
並且能夠以程式設計並執行 AlgorithmX, Dancing Links (DLX) 來求解，
這裡特別紀錄下我學習到的東西。

因內容比較多，所以我分成三篇：

數獨求解 Java 實現三部曲：

在這篇文中主要會先講精確覆蓋問題和 AlgorithmX，
如何用 Dancing Linkx (DLX) 來實現 Algorithm X 及求解數獨的部份會在下一篇及之後文章中介紹。

首先先了解什麼是精確覆蓋，
可以參考精確覆蓋問題 - 維基百科，自由的百科全書。
在一個 X 集合中，X 的若干子集的集合為 S，如果可以找到一個 S 的子集 S' (可能不只一個)，
滿足 X 的每一個元素都只在 S' 中出現一次，即為一個 X /的精確覆蓋解。

也可以換另一個說法，
滿足以下條件的集合為一個精確覆蓋：

S' 中任意兩個集合交集為空集合，所以 X 中的元素只會出現在 S' 中的某一個集合中並且只出現最多一次。
S' 中集合的全集為X，所以 X 中的元素在 S' 中會出現最少一次。
如上兩點，即 X 中的元素在 S' 中會出現恰好一次。

例如：

X = {1, 2, 3, 4, 5}

S = {S1, S2, S3, S4, S5} 為一個 X 的若干子集的集合，

其中 S1, S2, S3, S4, S5 各是 X 的子集

S1 = {1, 3, 5}

S2 = {2, 4}

S3 = {1, 2, 5}

S4 = {3, 4}

S5 = {}

如果忽略空集合 S5，我們可以找到兩個 X 的精確覆蓋解 S1' 和 S2'：

S1' = {S1, S2}

S2' = {S3, S4}

S1' 為解的原因為 S1 = {1, 3, 5} 和 S2 = {2, 4} 的併集為 X = {1, 2, 3, 4, 5}，且 X 中的各元素只在 S1 和 S2 中出現一次，S2' 同理也為另一個解。

精確覆蓋問題就是說：
我們現在有一組 X = {X1, X2, ...} 集合和 X 的若干子集合組成的集合 S = {S1, S2, ...}，
我們要如何找出 X 的精確覆蓋 S' = {Sx, Sy, ...} (Sx, Sy 為 S 中的集合可能不只一個，也有可能沒有)。

而 X演算法 (Algorithm X) 為一個精確問題求解的一個演算法，
可以參考 X演算法 - 維基百科，自由的百科全書。

AlgorithmX 也是一種深度優先算法，具體的步驟如下 (用實際例子舉例做一遍)：

假設 X = {1, 2, 3, 4, 5}

S = {S1, S2, S3, S4, S5}

S1 = {1, 3, 5}

S2 = {2}

S3 = {2, 5}

S4 = {2, 4}

S5 = {1, 3, 4}

用矩陣 A(r, c) 來表示可以表示如下 , r 是 row 編號，c 是 column 編號：

	1	2	3	4	5
S1	1	0	1	0	1
S2	0	1	0	0	0
S3	0	1	0	0	1
S4	0	1	0	1	0
S5	1	0	1	1	0

1. 如果沒有可選擇的 column，即為找到一個解，否則繼續。。

2. 選擇一個 column c (實務上通常會選擇 1 次數最少的 column，比較有可能更早找到解，例如範例是 column1 有 2 個 1、column 2 有 3 個 1，所以先選 column 1 )。

3. 從選定的 column 上選一個 A(r, c) = 1 的 row r 做為解中的一個集合，如果此時找不到可選的 row (即代表沒有 row 可以滿足此 column)，即代表無解，可能之前的 row 選擇有誤，這時就要把已作為解中的上一個選定的 row 從解中移掉，還原上次刪掉的 row 和 column 到 A 中並選擇其他 row 做為解中的一個集合繼續下一步驟。

4. 對於選定的 row 上的每一個 A(r, j) = 1 的 column j，從 A 中刪掉每一個 A(i, j) = 1 的 row i，最後再刪掉 column j。
用 sudo code 來寫如下：
For each column j such that A_r, j = 1,
for each row i such that A_i, j = 1,
delete row i from matrix A.
delete column j from matrix A.
5. 遞迴地執行此演算法。.

我們下面來實際做一次演算法，假設解是 S'：
1. 先選擇 column 1，把它標記起來。

2. 選擇 S1 row 作為解的一個集合，把做為解中之一的集合 S1 用標記起來，目前 S' = {S1}。

	1	2	3	4	5
S1	1	0	1	0	1
S2	0	1	0	0	0
S3	0	1	0	0	1
S4	0	1	0	1	0
S5	1	0	1	1	0

3. 對 S1 的所有是 1 的 column 標計起來 (即 column 1, column 3 和 column 5)，之後要把它們從 A 中移掉，代表我們已經找到符合 X 中 1, 3, 5 的解。

	1	2	3	4	5
S1	1	0	1	0	1
S2	0	1	0	0	0
S3	0	1	0	0	1
S4	0	1	0	1	0
S5	1	0	1	1	0

4. 被標記的 column 代表我們已找到的符合 X 子集合的 column，此列就是 column 1、 column 3 和 column 5，其他 row 如果第 column 1, 3, 5 是 1 的話我們就要把它們從可能的解侯選中排除掉，所以我們找出被標記的 column 上是 1 的 row 將它們標記起來，此列就是 S3 和 S5。

把 S1 和標計成紅色的 S3 (row 3), S5 (row 5), column 1, column3 和 column 5 移掉 (這裡不真得從畫面上移掉比較好看出變化，畫面上有標記的部份可看做已從 A 中移掉 )。

	1	2	3	4	5
S1	1	0	1	0	1
S2	0	1	0	0	0
S3	0	1	0	0	1
S4	0	1	0	1	0
S5	1	0	1	1	0

5. 用跟上述一樣的方法，這次為了演示選錯 row 的狀況，我們選 column 2 來找解 (通常我們會選 1 比較少的 column 4，因為 column 2 還有兩個 1，column 4 只有剩一個 1)，然後選擇 S2 為解中的集合，此時 S = {S1, S2}。

	1	2	3	4	5
S1	1	0	1	0	1
S2	0	1	0	0	0
S3	0	1	0	0	1
S4	0	1	0	1	0
S5	1	0	1	1	0

7. 把 S2 row 中的 1 對應到的 column 中為 1 的 row 刪掉，也就是 S4 row 4。

	1	2	3	4	5
S1	1	0	1	0	1
S2	0	1	0	0	0
S3	0	1	0	0	1
S4	0	1	0	1	0
S5	1	0	1	1	0

8. 此時可以發現能選的 column 只剩下 column 4 了，但此時已沒有可選的 row 了，
也就是沒有 row 可以滿足 column 4，代表此時無解，可能上一步驟選的 row (即 S2 row 2) 有錯，此時我們可以把 S2 中從已找到的解中移掉，讓 S' = {S1}，並把因選了 S2 移掉的 row 和 column 還原。

這次我們改選 S4 為解中的集合，此時 S' = {S1, S4}，用一樣的方法把 S4 上為 1 的 column 2, column 4 上的有 1 的 row (即 S2 row 2) 移掉。

	1	2	3	4	5
S1	1	0	1	0	1
S2	0	1	0	0	0
S3	0	1	0	0	1
S4	0	1	0	1	0
S5	1	0	1	1	0

9. 此時 A 中已經沒有可選的 column 了，即代表我們已經找到了一個解了，就是 S' = {S1, S4}。

10. 如果還想再找到其他解，我們可以再一路往回還原所選的 row, column 和因選了 row, column 而被移除的 row, column，我們一路回到第 3 步驟，不選 column 1，這次改選 column 2，這裡我們假設已經試過 S2 不是解的答案了，然後接下來選擇 S3，此時 S' = {S3}。

	1	2	3	4	5
S1	1	0	1	0	1
S2	0	1	0	0	0
S3	0	1	0	0	1
S4	0	1	0	1	0
S5	1	0	1	1	0

11. 一樣的我們把 S3 上的 1 對應到的 column 2, column 5 上，為 1 的 row S1, S2, S4 移掉。

	1	2	3	4	5
S1	1	0	1	0	1
S2	0	1	0	0	0
S3	0	1	0	0	1
S4	0	1	0	1	0
S5	1	0	1	1	0

12. 接下我們選擇 column 1，再選擇 column 1 上為 1 的 row S5 做為，此時 S' = {S3, S5}，接著把 S5 上為 1 的 column 1, column 3, column 4 移掉，此時我們發現已經沒有 column 可選了，代表 X 都已經被滿足了，即我們得到了第二個解： S' = {S3, S5}。

	1	2	3	4	5
S1	1	0	1	0	1
S2	0	1	0	0	0
S3	0	1	0	0	1
S4	0	1	0	1	0
S5	1	0	1	1	0

了解了如何用 Algorithm X 解決精確覆問題後，在下篇文章中，我會介紹如果用 Dancing Liks (DLX) 去實現及 Java 程式範例。

參考資料：

訂閱：文章 ( Atom )

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

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

2026年6月20日 星期六

數獨求解 Java 實現三部曲 - 第三部 - 數獨求解器的 Java 實現

數獨求解 Java 實現三部曲 - 第二部 - 舞蹈鏈 (Dancing Links) (DLX) - 可用來解數獨、8皇后問題(8 Queens, Puzzle) 等問題

數獨求解 Java 實現三部曲 - 第一部 - 精確覆蓋問題 (Exact cover) 與 X演算法 (AlgorithmX)

2026年6月20日星期六

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