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

數獨求解 Java 實現三部曲：

1. 數獨求解 Java 實現三部曲 - 第一部 - 精確覆蓋問題 (Exact cover) 與 X演算法 (AlgorithmX)
2. 數獨求解 Java 實現三部曲 - 第二部 -  舞蹈鏈 (Dancing Links) (DLX)  - 可用來解數獨、8皇后問題(8 Queens, Puzzle) 等問題
3. 數獨求解 Java 實現三部曲 - 第三部 -  數獨求解器的 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};

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

1. build(int[][] matrix)
   將輸入的 matrix 轉成上述的 Dancing Links 雙向鍵結結構。
2. cover(int colId) : 
   colId 指 column id，將選定的 column node 從 column header 中移除，並把該 column node 往下有 1 的 row 從矩陣中移除。
3. uncover(int colId)：
   cover(int colId) 的反向操作，將 cover(int colId) 的作用消除，把被移除的 column 及 row 放回矩陣中。
4. 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) 的話，圖形表示就會如以下：

可以注意到：

1. 我們並沒有修改 node 1 的左右連結，這樣之後要把 column 1 uncover 放回矩陣時就會可以很方便地把 node 1 的左右 node 跟 node 1 連起來即可。
   即：
   

   right[left[colId]] = colId;
   left[right[colId]] = colId;

2. 另一個是我們沒有必要修改 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 求解數獨和程式實作，
程式碼會一起在下一篇文章中分享。