在生成數獨題目時，流程是：生成一個完整的數獨——隨機挖空——解題——如果只有一個解，則生成該題目，如果有多個解，則重新挖空。

數獨題目的生成涉及的一個算法是回溯法，這里面的完整數獨的生成、求解都用到了回溯法。

1. 生成完整數獨

在生成部分，先生成所有宮的1，再生成所有宮的2，以此類推。

主要有三個值：

boolean[][][] placeable = new boolean[9][9][9];// 第幾個數字，第幾宮，第幾號位置

int[][] stepPos = new int[9][9];// 第幾個數字，第幾宮，值是位置

int[][] result=new int[9][9];

placeable 用來存儲每個數字在每個宮的每個位置是否可以放置，初始時，只要該位置沒有被占就可以放置，在生成數獨的過程中，嘗試在這個位置放置某數，如果與行列宮有沖突，則需更新placeable 。

stepPos 用來存儲某個宮中已經放置的數字的位置。

result既是存儲生成的數獨。

?

生成階段的回溯是通過一個雙重循環實現的：

private static int[][] tryGenerateFinalAnswer() {int[][] result=new int[9][9];for (int number = 0; number < 9; number++) {//注意這里沒有gong++for (int gong = 0; gong < 9;) {ArrayList<Integer> PlaceableList = getPlaceableList(number, gong);int length = PlaceableList.size();//回溯算法的重點就是這里，如果當前一步走不下去，就返回上一步，重走if (length <= 0) { resetPlaceable(result,number, gong);gong--;if (gong < 0) {number--;gong = 8;}removeNum(result, number, gong);}else {int pos = PlaceableList.get(random.nextInt(length));if (isCollide(result,number, gong, pos)) {placeable[number][gong][pos] = false;}else {addNum(result, number, gong, pos);gong++;}}}}return result;}

其實一開始寫數獨生成的時候，想的是先隨機生成第一個宮的所有數字，第二個宮在不與第一個宮沖突的情況下生成所有數字，以此類推，就是以宮為主順序生成數獨。這樣的做法理論上可行，但實際上需要非常大量的運算，而且極易容易沖突。因為后面一旦走不下去，往往要返回一個宮的所有數字，但是以數字為主順序，走不下去就只需要返回一個宮的一個數字。

2. 隨機挖空

隨機挖空的部分比較簡單，但是要注意使用另一個二維數組來存儲生成的題目，不要在完整的數組上動，因為后面解題部分要對比完整的數組，看看解題是否正確。

3. 解題

解題部分時參考了另一位大佬的代碼，之前看的時候距今已經過了一年有余，所以找不到他的博客了。

解題部分的思想非常的巧妙，首先將數獨題目中1-9這9個數，轉化成二進制中1的位置。000000100表示3，如001000000表示7，而題目中空缺的位置，則以111111111表示，這表示這個位置的候選數字是1~9。

然后根據已確定的數字分析更新空格的候選數字，比如候選值有2、3、6，則該空的二進制數就是000100110。當二進制中只有一個1，則表示該值可以確定，使用Integer.bitCount(data[m][i]) 方法判斷二進制中有幾個1。

這里的分析主要就是排除行列宮中已有的數字。

一直循環分析所有空格，直到不能從已確定的數字中分析出新的候選信息，就從一個空格的候選值中假設一個值填進格子中，再以此推測剩余的空格，直到所有格子都被填滿，或者是填補下去，那么就返回之前的假設，填其他值，以此類推。這其實和我們正常解數獨的思路是一樣的。

如果題目已經求得兩個解，則返回，重新生成題目。因為這個題目是從一個完整的數獨挖空而來，所以不可能沒有解。

解題的回溯部分主要通過遞歸實現：

private static void solve(int[][] data) {if(resultNum>1) {return;}analyse(data);int result = check(data);if (result == 1) {int[] position = findLessCandidatesPos(data);int pv = data[position[0]][position[1]];int pvcount = Integer.bitCount(pv);for (int i = 0; i < pvcount; i++) {int testV = 1 << ((int) (Math.log(Integer.highestOneBit(pv)) / Math.log(2)));pv ^= testV;int[][] copy = copyArray(data);copy[position[0]][position[1]] = testV;//這里不理解為什么要返回if(i>1) {return;}solve(copy);} }else if (result == 0) {resultNum++;System.out.println("------------------------------------第"+(resultNum)+"個答案---------------------"+ (System.nanoTime() - startTime) / 1000000.0 + "ms---");answer=data;binaryToInt(answer);printByRow(answer);}}

解題中值得借鑒的就是將數字1~9表示成二進制中1的位置，這樣可以很好的表示候選值。除了數獨中的數字與候選值表示成二進制中1的位置，

在找候選值的方法中，也是用三個二進制數分別表示當前值所在的行、列、宮已經存在的數字，來計算候選值的。

在判斷是否沖突的方法，也是用三個二進制數分別表示當前值所在的行、列、宮已經存在的數字，來判斷是否沖突的。

唯一解的數獨題目生成器代碼：//download.csdn.net/download/Michaelia_hu/12013857

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

總結

以上是生活随笔為你收集整理的唯一解的数独题目生成器——理解回溯法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。