2026年6月20日 星期六

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

數獨求解 Java 實現三部曲：

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

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

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

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

  1. 相同的格子 (cell) 只能有一個數字，例如一個 cell 如果是 1 就不能是 2~9 其他數字。
  2. 相同的 row 中相同的數字只能有一個，例如 row 1 上只能有一個 1、只能有一個 2 等。
  3. 相同的 column 中相同的數字只能有一個，例如 column 1 上只能有一個 1、只能有一個 2 等。
  4. 相同的宮 (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 子集
轉換成對應數獨的哪一個格子要填哪一個數字就可以了。

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

  1. 最簡單的 Backtracking 深度查詢遞迴演算法，效能最差，重試錯率很高。
  2. 用 Java 物件的方式實作 Dancing links，效能較差，且因為物件、鏈結等處理成本，有時花的時間會比 Backtracking 的時間還久。
  3. 用陣列 (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
  1. Backtracking ： 耗時 20578 ms。
  2. 用 Java 物件的方式實作 Dancing links : 耗時 41717 ms。
  3. 用陣列 (pure int array) 的方式實作 Dancing links ：耗時 277 ms。

源碼分享：

數獨(Sudoku)解答器.zip

張貼者： 於
標籤： , , , ,

沒有留言 :

張貼留言

訂閱： 張貼留言 ( Atom )