本文同步分享於個人Blog → InformisTry-HankLee
昨天介紹了Algorithm X的概念和流程，但跟數獨又有什麼關係呢？這個問題我大概花了兩～三天才弄懂，因此今天就要來介紹這一層關係，並且會提供給大家範例程式碼，那就讓我們看下去吧～
昨天提到Algorithm Ｘ在使用的時候，會先將資料轉換成Matrix，但是數獨到底跟Matrix有什麼關係勒？
我們以4x4的數獨為例（因為9x9的資料太多了），因為數獨基本上會有4個限制：
因此我們在製作Matrix的時候，欄（Column）的數量會是4x4x4，前兩個4的是數獨的大小，最後一個4就是這四個限制，因此欄的數量會是64個；而列的數量也是4x4x4，前兩個一樣是數獨的大小，最後一個4是『數字的數量(1~4)』，因此列的數量也是64，所以我們準備的Matrix就會是一個64x64的大矩陣。
如果是9x9的數獨，就會是324x729的更大矩陣。
在這個Matrix中，欄基本上是代表每一個欄位(如上圖），因為每16欄是一個限制，64欄總共分成4組，剛好對應4個限制，因此每一組中都會有1~16的編號，而全部的欄位的編號是用index 0~63；此外，列表示的是（值, 列, 欄）(cand, r, c)，也就是哪一個座標位置（欄位）的值是什麼，再來，會將每4個列設定為一組，每一組對應的是同一個欄位但不同值，以前面四個列為例，都是說在0,0這個位置中，填入的數字分別是1~4。
按照上表來看，第一組欄(index 0 ~ index 15)的限制是每一個欄位只能有一個值，因此你們會發現，在下面欄位中填1的時候，同一個欄位且同一欄都會填入1，因為同一欄表示的是同一個欄位（用上面的編號來看）；而第二組欄的限制是每一列填入的數字不可重複，因此對應到(cand, r, c)去看的話，就會看到同一欄中有填入1的欄位相互抵觸（有我就沒有他）；第三組欄的限制和第四組欄的限制也是透過同樣的方式去填入數字1。上表看起來可能不清楚，因此檔案可以在這邊下載，讓大家可以把檔案載回去看，可能需要一點時間研究，這個檔案中也包含了如果是套用到一個已知解答的4x4數獨上時，表格會變成什麼樣子，其中最下面可以看到每一個欄的1的合計都是1（也只能是這樣才是答案）。
那問題又來了：如何去判斷哪個欄位要填數字1? 上面的這個表格就是整理出來的公式，在程式實作的時候，就可以利用這些公式在對應的位置中填入數字1。
只要產生出了這個複雜的Matrix，我們就可以用Algorithm X的概念來計算數獨的答案。
程式的概念基本上是我們要先產生Matrix，因此可以透過MatrixUtils.generateMatrix(size, sqrt, symbols, numOfConstraints)這個方法來產生matrix，裡面就已經套入了上面提到的四個公式來在欄位中放入數字1（如果要看產生出來的結果，可以呼叫MatrixUtils.printMatrix()來看看結果是不是如預期，程式如下：
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* @author Hank Lee
* Shared in InformisTry -- https://jumperc2p.github.io/InformisTry/
*/
public class MatrixUtils {
public static Map<String, List<String>> combinations = new HashMap<>();
/**
* The generation methods to prepare matrix
* @param size the size of sudoku. For example, a 4x4 sudoku grid will give "4".
* @param sqrt the sqrt of the size of sudoku. For example, a 4x4 sudoku grid will give "2".
* @param symbols the symbols used in grid
* @param numberOfConstraints the number of constraints
* @param cages the cages for killer sudoku
* @return matrixes
*/
public static List<Matrix> generateMatrix(Integer size, Integer sqrt, Integer[] symbols, int numberOfConstraints) {
// Prepare to matrix
List<Matrix> matrixs = null;
matrixs = new ArrayList<>();
for (int row = 0; row < size; row++) {
for (int col = 0; col < size; col++) {
for (int value : symbols) {
Integer[] constraints = new Integer[size*size*numberOfConstraints];
// One value constraint:
// constraint number : row x size + col
constraints[row * size + col] = 1;
// Row constraint:
// constraint number : size^2 + row x size + value - 1
constraints[((int) Math.pow(size,2)) + row * size + value - 1] = 1;
// Column constraint:
// constraint number : 2 x size^2 + col x size + value - 1
constraints[2 * ((int) Math.pow(size,2)) + col * size + value - 1] = 1;
// Box constraint:
// constraint number : 3 x size^2 + (row / sqrt) x size x sqrt + (col / sqrt) x size + value - 1
constraints[3 * ((int) Math.pow(size,2)) + (row / sqrt) * size * sqrt + (col / sqrt) * size + value - 1] = 1;
matrixs.add(new Matrix(row, col, value, constraints));
}
}
}
// To print the matrix
// printMatrix(matrixs, size);
return matrixs;
}
/**
* To print the matrix in the console
*
* @param matrixes the matrix
* @param size the size of sudoku. For example, a 4x4 sudoku grid will give "4".
*/
public static void printMatrix(List<Matrix> matrixes, int size) {
//1,1,1 | c c c c c c c c c c c c c c c c | c c c c c c c c c c c c c c c c | c c c c c c c c c c c c | c c c c c c c c c c c c c c c c
System.out.println("r,c,v | c c c c c c c c c c c c c c c c | c c c c c c c c c c c c c c c c | c c c c c c c c c c c c c c c c | c c c c c c c c c c c c c c c c | c c c c c c c c c c c c c c c c");
System.out.println("-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------");
for (Matrix m : matrixes) {
System.out.print(m.row+","+m.col+","+m.value+" | ");
for (int i = 0; i < m.constraints.length; i++) {
if (i != 0 && i % (size*size) == 0)
System.out.print("| ");
Integer val = m.constraints[i];
System.out.print((val == null ? " ":m.constraints[i])+" ");
}
System.out.println();
if (m.value % size == 0)
System.out.println("-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------");
}
}
}
有了Matrix之後，在Solver裡面，因為數獨會有一些預設值，所以有了這些預設值的話，就透過removeRowsByGrid(sudokuGrid)去改變Matrix的內容（利用預設值將Matrix的內容刪減），然後才正式進行solve的動作，程式如下：
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* Algorithm X solver for standard Sudoku.
* @author Hank Lee
* Shared in InformisTry -- https://jumperc2p.github.io/InformisTry/
*/
public class AlgorXSolver {
// prepare the object to store matrix, partial solutions and the columns deleted
List<Matrix> matrixes = null;
List<Matrix> solutions = new ArrayList<>();
List<Integer> deletedColumns = new ArrayList<>();
Integer size = null;
public AlgorXSolver() {
} // end of AlgorXSolver()
/**
* The public solve method for other programs to call
*/
public boolean solve(SudokuGrid sudokuGrid) {
int numConstraints = 4;
// if the matrix is empty, it need to be generated by the size of sudoku grid
// and symbols and the number of constraints.
if (matrixes == null)
matrixes = MatrixUtils.generateMatrix(sudokuGrid.size, sudokuGrid.sqrt, sudokuGrid.symbols, numConstraints);
// As some cells have been inserted value,
// we need to get rid of those rows and columns related to them in the matrix
removeRowsByGrid(sudokuGrid);
// the total number of constraints need to be satisfied in the matrix
size = sudokuGrid.size * sudokuGrid.size * numConstraints;
// call the private solve method to find the solution of the standard sudoku
if (solve(matrixes, deletedColumns)) {
// After finding the solutions,
// add the value to each cell of the standard sudoku grind.
for (Matrix matrix : solutions) {
sudokuGrid.grid[matrix.row][matrix.col] = matrix.value;
}
return true;
}
return false;
} // end of solve()
/**
* The exact method to solve standard sudoku problem
*
* @param matrixes the matrixes to analyse
* @param deletedColumns those deleted columns of constraints in matrix
* @return the problem is solved or not.
*/
@SuppressWarnings("unchecked")
private Boolean solve(List<Matrix> matrixes, List<Integer> deletedColumns) {
// If Matrix is empty, the problem is solved; terminate successfully.
if (matrixes.size() == 0) {
return true;
}
// Find the minimize sum of column constraints in the current matrix
// and get the matrixes of potential solution
Map<String, Object> minMap = findMinSumByColumn(matrixes, deletedColumns);
List<Matrix> potentialSols = (List<Matrix>) minMap.get("potentialSols");
// If the index is null, it means that it cannot find a solution based on the
// current situation.
if (minMap.get("idx") == null) {
return false;
}
// If the min value is 0, then the size of potential solution will be 0,
// which means the process is terminated unsuccessfully.
if (potentialSols.size() == 0) {
return false;
}
// To store the current matrix and deleted columns for backtracking recovery
List<Matrix> tempmatrixes = new ArrayList<>();
tempmatrixes.addAll(matrixes);
List<Integer> tempDeletedColumns = new ArrayList<>();
tempDeletedColumns.addAll(deletedColumns);
for (Matrix matrix : potentialSols) {
// add the partial solutions
solutions.add(matrix);
// find which columns should be deleted
for (int i = 0; i < matrix.constraints.length; i++) {
if (matrix.constraints[i] != null && matrix.constraints[i] == 1) {
deletedColumns.add(i);
}
}
// remove matrix based on the deleted columns
for (Integer i : deletedColumns) {
// delete row by idx
matrixes.removeIf(x -> x.constraints[i] != null);
}
// Use the modified matrix to find partial solutions recursively.
if (solve(matrixes, deletedColumns)) {
return true;
// if it returns false, it means that the partial solution is wrong,
// and the process need to be recovered to the previous state, which is
// backtracking.
} else {
solutions.remove(matrix);
matrixes.removeAll(matrixes);
matrixes.addAll(tempmatrixes);
deletedColumns.removeAll(deletedColumns);
deletedColumns.addAll(tempDeletedColumns);
}
}
return false;
}
/**
* The method is used to find the minimize sum of columns in the current matrix
* and based on the column, prepare to matrixes which are potential solutions.
*
* @param matrixes the current matrix
* @param deletedColumns the column deleted
* @return
*/
private Map<String, Object> findMinSumByColumn(List<Matrix> matrixes, List<Integer> deletedColumns) {
Integer[] sum = new Integer[size];
Integer min = null;
Integer idx = null;
for (Matrix m : matrixes) {
for (int i = 0; i < size; i++) {
if (m.constraints[i] != null) {
if (sum[i] == null)
sum[i] = 0;
sum[i] = sum[i] + m.constraints[i];
}
}
}
for (int i = 0; i < size; i++) {
// if the index of column can be found in the list of deleted columns
// it means that the column should be skipped.
if (deletedColumns.contains(i)) {
continue;
}
if (sum[i] == null) {
idx = i;
break;
}
if (min == null || min > sum[i]) {
min = sum[i];
idx = i;
}
}
List<Matrix> potentialSols = new ArrayList<>();
if (min != null) {
for (Matrix m : matrixes) {
if (m.constraints[idx] != null) {
potentialSols.add(m);
}
}
}
Map<String, Object> minMap = new HashMap<>();
minMap.put("potentialSols", potentialSols);
minMap.put("idx", idx);
assert (idx == null);
return minMap;
}
/**
* Remove the rows and columns if the cell contains a value
*
* @param sudokuGrid the sudoku grid
*/
private void removeRowsByGrid(SudokuGrid sudokuGrid) {
for (int i = 0; i < sudokuGrid.size; i++) {
for (int j = 0; j < sudokuGrid.size; j++) {
if (sudokuGrid.grid[i][j] != null) {
// delete row by idx
for (Matrix m : matrixes) {
if (m.row == i && m.col == j && m.value == sudokuGrid.grid[i][j]) {
matrixes.remove(m);
for (int k = 0; k < m.constraints.length; k++) {
if (m.constraints[k] != null && m.constraints[k] == 1) {
deletedColumns.add(k);
}
}
for (Integer n : deletedColumns) {
// delete row by idx
matrixes.removeIf(x -> x.constraints[n] != null);
}
break;
}
}
}
}
}
}
}
當中的SudokuGrid則是紀錄數獨的物件，內容為：
/**
* @author Hank Lee
* Shared in InformisTry -- https://jumperc2p.github.io/InformisTry/
*
*/
public class SudokuGrid {
public Integer size = 0;
public Integer[] symbols = null;
public Integer[][] grid = null;
public Integer sqrt = 0;
public boolean validate() {
for (int currentY = 0; currentY < size; currentY++) {
for (int currentX = 0; currentX < size; currentX++) {
int currentNumber = grid[currentY][currentX];
if (!this.basicValidate(this, currentNumber, currentX, currentY))
return false;
}
}
return true;
}
/**
* To do the basic validation of sudoku grid.
* In the method, it only checks basic 3 constraints,
* which are box-value constraints, row-value constraints and column-value constraints
*
* @param sudokuGrid the sudoku grid
* @param currentNumber the current number to check
* @param currentX the current column of the cell
* @param currentY the current row of the cell
* @return true: valid, false: invalid
*/
public boolean basicValidate(SudokuGrid sudokuGrid, int currentNumber, int currentX, int currentY) {
// compare each number in one row
for (int x = 0; x < sudokuGrid.size; x++) {
if (currentX != x && sudokuGrid.grid[currentY][x] != null && currentNumber == sudokuGrid.grid[currentY][x])
return false;
}
// compare each number in one column
for (int y = 0; y < sudokuGrid.size; y++) {
if (currentY != y && sudokuGrid.grid[y][currentX] != null && currentNumber == sudokuGrid.grid[y][currentX])
return false;
}
// compare each number in one sub-grid
int modX = currentX / sudokuGrid.sqrt;
int modY = currentY / sudokuGrid.sqrt;
for (int y = (modY*sudokuGrid.sqrt); y<((modY+1)*sudokuGrid.sqrt); y++) {
for (int x = (modX*sudokuGrid.sqrt); x<((modX+1)*sudokuGrid.sqrt); x++) {
if (currentX != x && currentY != y && sudokuGrid.grid[y][x] != null && sudokuGrid.grid[y][x] == currentNumber)
return false;
}
}
return true;
}
}
這個範例程式我感覺還可以進行優化，目前執行起來的時間會比Backtracking還要長，但優化這件事情，就有緣再說囉！
用Algorithm Ｘ解決數獨的問題，麻煩的地方是要產生對應的Matrix，產生這個Matrix之後，一切就簡單了許多，上面的範例我是用Wikipedia上面的範例去進行的，針對這個範例寫出code之後，再直接套入這個數獨的Matrix，一樣可以產生結果。
三個字：『終於啊～～～～～』
30天實在是有點硬，不對，應該說，沒先把文章寫好就參加實在有點硬，但這次參加活動主要也是想為自己留下一個里程碑吧，演算法這些東西在學了之後說真的其實也忘了差不多，藉由這次的整理也算是讓自己可以複習這些內容，我已經盡量讓我自己可以每天都有文章可以產出，畢竟我現在是最後一個學期，手上一次在進行兩個專案，時間上實在是有點太緊繃，但也很高興自己完成了這件事。
原本希望能自己將內容寫的更有趣更清楚一點，但這我有點愧疚，我感覺自己寫出來的東西未如預期的簡單明瞭，也不知道大家能不能弄懂這些內容，希望還勉強可以接受。
謝謝30天都來看我的文章的人，也謝謝那些看過任何一篇文章的人，希望這些內容多多少少可以幫助到一些在學習的人。
最最後後工商一下，小弟今年弄了一個Blog -- InformisTry-HankLee，我以後會努力產文跟大家分享一些東西，如果有什麼主題希望我可以分享的，也可以聯繫我跟我說。
下台一鞠躬。
iThome鐵人賽
看影片追技術