有沒有對數獨感興趣的朋友呢？數獨作為一款經典的邏輯游戲，其目標是在一個9x9的方格中填入數字1至9，確保每一行、每一列以及每一個3x3的子網格中都包含這些數字且不重復。盡管數獨的規則看似簡單，但編寫一個能夠自動求解數獨的程序卻是一項頗具挑戰性的任務。本文將深入探討如何運用回溯算法來實現數獨的自動求解。

數獨求解算法及步驟

我們使用一個二維數組來表示數獨的表格，空位置填充0。

數獨求解的核心算法是回溯算法。回溯算法是一種通過逐步構建解決方案并在遇到沖突時回退的算法。具體來說，我們嘗試在空格中填入一個數字，然后遞歸地繼續填充下一個空格。如果在某個步驟中發現無法繼續填充，則回退到上一步并嘗試其他數字。

• 算法步驟

1. 尋找空格：我們循環數獨的所有單元格，如果數組的值為0的話則此格未填寫數字。

2. 嘗試填入數字：對于這個空格，嘗試填入1到9中的一個數字。

3. 檢查數字的正確性：檢查填入的數字是否與當前行、列和3x3子網格中的數字有重復。

4. 遞歸求解：如果沒有重復，則遞歸地繼續填充下一個空格。

5. 回溯：如果在某個步驟中發現無法繼續填充，則回退到上一步并嘗試其他數字。

Java代碼實現

我們使用一個二維數組來表示數獨，有一種只求解數獨的方法及求解不是唯一解的所有可行解的方法。代碼如下

/*** 數獨求解*/
public class SudokuSolver {/*** 檢查數獨元素的正確性，及每行、每列、每九宮格的唯一性*/public static boolean checkValue(int[][] sudoku,int value,int row,int col){//檢驗當前元素所在行for (int i = 0; i < 9; i++) {if(sudoku[row][i] == value){return false;}}//檢驗當前元素所在列for (int i = 0; i < 9; i++) {if(sudoku[i][col] == value){return false;}}//檢驗當前元素所在九宮格for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {// 如果當前元素所在九宮格有值，則返回falseif(sudoku[row/3*3+i][col/3*3+j] == value){return false;}}}return true;};/*** 回溯算法求解數獨*/public static boolean solveSudokuSingleSec(int[][] sudoku) {//遞歸回溯法求解數獨,循環遍歷81個元素，如果當前元素為0，則嘗試1-9的值，如果符合要求，則遞歸求解，否則返回上一層繼續嘗試for (int i = 0; i < 9; i++) {for(int j = 0; j < 9; j++){//如果當前元素為0，則嘗試1-9的值，如果符合要求，則遞歸求解，否則返回上一層繼續嘗試if(sudoku[i][j]== 0){for (int k =1;k<=9;k++){//如果符合要求，則遞歸求解，否則返回上一層繼續嘗試if(checkValue(sudoku,k,i,j)){sudoku[i][j] = k;if(solveSudokuSingleSec(sudoku)){return true;}// 回溯sudoku[i][j] = 0;}}// 無法繼續填充，則回退到上一步并嘗試其他數字。return false;}}}// 找到一個解，則返回true,無需繼續回溯return true;}/***回溯算法求解數獨的所有可能解*/public static void solveSudokuSec(int[][] sudoku, List<int[][]> result) {// 遞歸回溯法求解數獨,循環遍歷81個元素，如果當前元素為0，則嘗試1-9的值，如果符合要求，則遞歸求解，否則返回上一層繼續嘗試for (int i = 0; i < 9; i++) {for(int j = 0; j < 9; j++){if(sudoku[i][j]== 0){for (int k =1;k<=9;k++){if(checkValue(sudoku,k,i,j)){sudoku[i][j] = k;// 遞歸求解solveSudokuSec(sudoku,result);// 回溯sudoku[i][j] = 0;}}// 無法繼續填充，則回退到上一步并嘗試其他數字。return;}}}// 找到一個解，記錄并添加到集合中int[][] resultArray = new int[9][9];for (int row = 0; row < 9; row++) {System.arraycopy(sudoku[row], 0, resultArray[row], 0, 9);}result.add(resultArray);}public static void main(String[] args) {int[][] initArraySingle = new int[][]{{8,0,0,0,0,0,0,0,0},{0,0,3,6,0,0,0,0,0},{0,7,0,0,9,0,2,0,0},{0,5,0,0,0,7,0,0,0},{0,0,0,0,4,5,7,0,0},{0,0,0,1,0,0,0,3,0},{0,0,1,0,0,0,0,6,8},{0,0,8,5,0,0,0,1,0},{0,9,0,0,0,0,4,0,0}};int[][] initArray = new int[][]{{8,0,0,0,0,0,0,0,0},{0,0,3,6,0,0,0,0,0},{0,7,0,0,9,0,2,0,0},{0,8,0,0,0,7,0,0,0},{0,0,0,0,4,5,7,0,0},{0,0,0,1,0,0,0,3,0},{0,0,1,0,0,0,0,6,8},{0,0,8,5,0,0,0,1,0},{0,9,0,0,0,0,4,0,0}};// 回溯算法求解數獨solveSudokuSingleSec(initArraySingle);for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {System.out.print(initArraySingle[i][j]+" ");}System.out.println();}List<int[][]> result = new ArrayList<>();// 回溯算法求解數獨的所有可能解solveSudokuSec(initArray,result);System.out.println("共"+result.size()+"種解法");for (int i = 0; i < result.size(); i++){System.out.println("解法"+(i+1)+":");for (int j = 0; j < 9; j++) {for (int k = 0; k < 9; k++) {System.out.print(initArraySingle[j][k]+" ");}System.out.println();}};}}

求解結果如下：

8 1 2 7 5 3 6 4 9 
9 4 3 6 8 2 1 7 5 
6 7 5 4 9 1 2 8 3 
1 5 4 2 3 7 8 9 6 
3 6 9 8 4 5 7 2 1 
2 8 7 1 6 9 5 3 4 
5 2 1 9 7 4 3 6 8 
4 3 8 5 2 6 9 1 7 
7 9 6 3 1 8 4 5 2 
共295種解法
解法1:
8 1 2 7 5 3 6 4 9 
9 4 3 6 8 2 1 7 5 
6 7 5 4 9 1 2 8 3 
1 5 4 2 3 7 8 9 6 
3 6 9 8 4 5 7 2 1 
2 8 7 1 6 9 5 3 4 
5 2 1 9 7 4 3 6 8 
4 3 8 5 2 6 9 1 7 
7 9 6 3 1 8 4 5 2 
解法2:
8 1 2 7 5 3 6 4 9 
9 4 3 6 8 2 1 7 5 
6 7 5 4 9 1 2 8 3 
1 5 4 2 3 7 8 9 6 
3 6 9 8 4 5 7 2 1 
2 8 7 1 6 9 5 3 4 
5 2 1 9 7 4 3 6 8 
4 3 8 5 2 6 9 1 7 
7 9 6 3 1 8 4 5 2 
解法3:
...

總結

通過使用回溯算法，我們可以有效地求解數獨問題。雖然回溯算法在最壞情況下的時間復雜度較高，但對于標準9x9的數獨問題，它通常能夠在合理的時間內找到解決方案。希望本文對你理解數獨求解算法有所幫助，并激發你進一步探索算法的興趣。