數獨（すうどく，Sudoku）是一種運用紙、筆進行演算的邏輯遊戲。玩家需要根據9×9盤面上的已知數字，推理出所有剩餘空格的數字，并滿足每一行、每一列、每一個粗線宮内的數字均含1-9，不重複。
一般情況下，産生一個數獨題目，包含兩個步驟：
- 産生一個數獨終盤（9X9）
- 在第一步産生的數獨終盤中，根據難易程度，在終盤上挖掉不同數目的數字。
經過該兩個步驟之後，我們就可以将某一個數獨難題展示出來，如：
本文列舉數獨終盤産生的幾個方法，大家一起來看看吧。
矩陣轉換法
矩陣轉換法，簡言之，就是對一個已有的數獨終盤矩陣進行操作。
主要采用交換數字、交換行/列資料等方法，産生新的矩陣。
為了完成矩陣的轉換，我們需要有可用的數獨終盤矩陣作為種子矩陣才行。可以采用如下做法完成：
- 先給定幾個可用數獨終盤作為備選種子矩陣。
- 産生一個随機數，随機選中其中的一個作為種子矩陣。
如編寫一個産生種子矩陣的工具類：
import java.util.Random;
/**
*
* @author wangmengjun
*
*/
public final class SeedSudokuMatrixFactory {
private static final int seedSudokuArrays[][][] = {
{ { 1, 2, 3, 4, 5, 6, 7, 8, 9 }, { 4, 5, 6, 7, 8, 9, 1, 2, 3 },
{ 7, 8, 9, 1, 2, 3, 4, 5, 6 },
{ 2, 1, 4, 3, 6, 5, 8, 9, 7 },
{ 3, 6, 5, 8, 9, 7, 2, 1, 4 },
{ 8, 9, 7, 2, 1, 4, 3, 6, 5 },
{ 5, 3, 1, 6, 4, 2, 9, 7, 8 },
{ 6, 4, 2, 9, 7, 8, 5, 3, 1 },
{ 9, 7, 8, 5, 3, 1, 6, 4, 2 } },
{ { 3, 9, 4, 5, 1, 7, 6, 2, 8 }, { 5, 1, 7, 6, 2, 8, 3, 9, 4 },
{ 6, 2, 8, 3, 9, 4, 5, 1, 7 },
{ 9, 3, 5, 4, 7, 1, 2, 8, 6 },
{ 4, 7, 1, 2, 8, 6, 9, 3, 5 },
{ 2, 8, 6, 9, 3, 5, 4, 7, 1 },
{ 1, 4, 3, 7, 5, 9, 8, 6, 2 },
{ 7, 5, 9, 8, 6, 2, 1, 4, 3 },
{ 8, 6, 2, 1, 4, 3, 7, 5, 9 } },
{ { 7, 6, 1, 9, 8, 4, 2, 3, 5 }, { 9, 8, 4, 2, 3, 5, 7, 6, 1 },
{ 2, 3, 5, 7, 6, 1, 9, 8, 4 },
{ 6, 7, 9, 1, 4, 8, 3, 5, 2 },
{ 1, 4, 8, 3, 5, 2, 6, 7, 9 },
{ 3, 5, 2, 6, 7, 9, 1, 4, 8 },
{ 8, 1, 7, 4, 9, 6, 5, 2, 3 },
{ 4, 9, 6, 5, 2, 3, 8, 1, 7 },
{ 5, 2, 3, 8, 1, 7, 4, 9, 6 } },
{ { 7, 1, 5, 4, 3, 6, 2, 9, 8 }, { 4, 3, 6, 2, 9, 8, 7, 1, 5 },
{ 2, 9, 8, 7, 1, 5, 4, 3, 6 },
{ 1, 7, 4, 5, 6, 3, 9, 8, 2 },
{ 5, 6, 3, 9, 8, 2, 1, 7, 4 },
{ 9, 8, 2, 1, 7, 4, 5, 6, 3 },
{ 3, 5, 7, 6, 4, 1, 8, 2, 9 },
{ 6, 4, 1, 8, 2, 9, 3, 5, 7 },
{ 8, 2, 9, 3, 5, 7, 6, 4, 1 } } };
private SeedSudokuMatrixFactory() {
}
/**
* 随機擷取一個預先定義好的數獨數組
*/
public static int[][] retrieveSeedSudokuArrayByRandom() {
int randomInt = new Random().nextInt(seedSudokuArrays.length);
return seedSudokuArrays[randomInt].clone();
}
} 複制
}
複制
有了種子矩陣之後，我們就可以對某個種子矩陣做矩陣轉換處理，進而擷取更多的可用的數獨終盤矩陣。
兩個數互相交換法
下圖就是一個數字9和資料1交換的例子：
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
/**
*
* @author wangmengjun
*
*/
public class SudokuPuzzleMatrixGenerator {
/** 待轉換的數組種子數組 */
private int[][] sampleArray = SeedSudokuMatrixFactory
.retrieveSeedSudokuArrayByRandom();
public int[][] generateSudokuArray() {
List<Integer> randomList = buildRandomList();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
for (int k = 0; k < 9; k++) {
if (sampleArray[i][j] == randomList.get(k)) {
sampleArray[i][j] = randomList.get((k + 1) % 9);
break;
}
}
}
}
return sampleArray;
}
private List<Integer> buildRandomList() {
List<Integer> result = Arrays.asList( 1, 2, 3, 4, 5, 6, 7, 8, 9 );
Collections.shuffle(result);
return result;
}
} 複制
/**
*
* @author wangmengjun
*
*/
public class Main {
public static void main(String[] args) {
int[][] grids = new SudokuPuzzleMatrixGenerator().generateSudokuArray();
printArray(grids);
}
/**
* 列印二維數組到控制台
*/
private static void printArray(int[][] grids) {
for (int i = 0; i < 9; i++) {
if (i % 3 == 0) {
System.out.println(" -----------------------");
}
for (int j = 0; j < 9; j++) {
if (j % 3 == 0) {
System.out.print("| ");
}
System.out.print(grids[i][j] == 0 ? " " : grids[i][j]);
System.out.print(" ");
}
System.out.println("|");
}
System.out.println(" -----------------------");
}
} 複制
某次運作的結果：
-----------------------
| 3 5 4 | 2 7 9 | 6 1 8 |
| 2 7 9 | 6 1 8 | 3 5 4 |
| 6 1 8 | 3 5 4 | 2 7 9 |
-----------------------
| 5 3 2 | 4 9 7 | 1 8 6 |
| 4 9 7 | 1 8 6 | 5 3 2 |
| 1 8 6 | 5 3 2 | 4 9 7 |
-----------------------
| 7 4 3 | 9 2 5 | 8 6 1 |
| 9 2 5 | 8 6 1 | 7 4 3 |
| 8 6 1 | 7 4 3 | 9 2 5 |
----------------------- 複制
調整行或者列
下面就是兩列互換的例子。對于行或者列，需要保證：
交換隻發生在前三行，中間三行，最後三行，前三列，中間三列以及最後三列之間。
而不能越界交換，比如第一行和第四行交換就是不允許的。
交換行
public int[][] generateSudokuArray1() {
Random random = new Random();
int randomRowNum = 0;
//随機交換20次
for (int i = 0; i < 20; i++) {
randomRowNum = random.nextInt(8) + 1;
for (int col = 0; col < 9; col++) {
if(randomRowNum % 3 ==0)
{
int temp = sampleArray[randomRowNum][col];
sampleArray[randomRowNum][col] = sampleArray[randomRowNum+1][col];
sampleArray[randomRowNum+1][col] = temp;
}
else
{
int temp = sampleArray[randomRowNum][col];
sampleArray[randomRowNum][col] = sampleArray[randomRowNum-1][col];
sampleArray[randomRowNum-1][col] = temp;
}
}
}
return sampleArray;
} 複制
交換列
public int[][] generateSudokuArray2() {
Random random = new Random();
int randomColumnNum = 0;
for (int i = 0; i < 20; i++) {
randomColumnNum = random.nextInt(8) + 1;
for (int row = 0; row < 9; row++) {
if(randomColumnNum %3 ==0)
{
int temp = sampleArray[row][randomColumnNum];
sampleArray[row][randomColumnNum] = sampleArray[row][randomColumnNum+1];
sampleArray[row][randomColumnNum+1] = temp;
}else
{
int temp = sampleArray[row][randomColumnNum];
sampleArray[row][randomColumnNum] = sampleArray[row][randomColumnNum-1];
sampleArray[row][randomColumnNum-1] = temp;
}
}
}
return sampleArray;
} 複制
交換行的一個測試示例：
/**
*
* @author wangmengjun
*
*/
public class Main {
public static void main(String[] args) {
int[][] grids = new SudokuPuzzleMatrixGenerator().generateSudokuArray1();
printArray(grids);
}
/**
* 列印二維數組到控制台
*/
private static void printArray(int[][] grids) {
for (int i = 0; i < 9; i++) {
if (i % 3 == 0) {
System.out.println(" -----------------------");
}
for (int j = 0; j < 9; j++) {
if (j % 3 == 0) {
System.out.print("| ");
}
System.out.print(grids[i][j] == 0 ? " " : grids[i][j]);
System.out.print(" ");
}
System.out.println("|");
}
System.out.println(" -----------------------");
}
} 複制
某次運作的結果：
-----------------------
| 2 3 5 | 7 6 1 | 9 8 4 |
| 7 6 1 | 9 8 4 | 2 3 5 |
| 9 8 4 | 2 3 5 | 7 6 1 |
-----------------------
| 3 5 2 | 6 7 9 | 1 4 8 |
| 6 7 9 | 1 4 8 | 3 5 2 |
| 1 4 8 | 3 5 2 | 6 7 9 |
-----------------------
| 4 9 6 | 5 2 3 | 8 1 7 |
| 5 2 3 | 8 1 7 | 4 9 6 |
| 8 1 7 | 4 9 6 | 5 2 3 |
----------------------- 複制
調整塊的位置
矩陣旋轉
另外，還可以以對角線對對稱，交換資料等方式，如：
public int[][] getArrayWithDiagonalSymmetry() {
int[][] result = new int[9][9];
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
result[i][j] = sampleArray[j][i];
}
}
return result;
} 複制
随機法
矩陣轉換法生成數獨終盤的方式具有友善速度塊的特點。
它的缺點産生的終盤的随機性不是很強，畢竟是從一個固定的種子矩陣轉換而得的。
之前的一篇博文，講解過回溯法解數獨，如果初始為空的二維數組，在周遊的時候，可以将1-9的候選數随機化，這樣就能産生相對随機性較大的數獨了。因為已經在之前部落格講過，這裡就不再叙述。
本文給出一個随機産生數獨終盤的另外一種方法。
該種方法就是考慮到，數獨的數量很多。
（約有6.67×10的21次方）種組合
終盤數量
終盤數量數獨中的數字排列千變萬化，那麼究竟有多少種終盤的數字組合呢？
6,670,903,752,021,072,936,960（約有6.67×10的21次方）種組合，2005年由Bertram Felgenhauer和Frazer Jarvis計算出該數字，并将計算方法釋出在他們網站上，如果将等價終盤（如旋轉、翻轉、行行對換，數字對換等變形）不計算，則有5,472,730,538個組合。數獨終盤的組合數量都如此驚人，那麼數獨題目數量就更加不計其數了，因為每個數獨終盤又可以制作出無數道合格的數獨題目。
參考自http://baike.baidu.com/link?url=ePXUCvpBaRKBkEA3pVfOkg3m-NBozO6a4GDS0N3E5_gK1nnJCDzd5O-YL1w7c5S3
假設
按照這個數量，如果我們将一個[1,2,3,4,5,6,7,8,9]的數組随機化，然後将其作為一行資料添加到一個二維數組中去，該行能滿足數獨終盤規則的機率是很大的。
思想
基于這個假設(假設的有效性會在文章後面驗證)，随機算法思想如下：
- 寫一個方法用于擷取一個由1到9九個數随機排列的一維數組。
- 循環行(下标從0到8)，将這個随機産生的一維數組作為目前行的内容，如果是第一行（行标為0），那麼直接作為該行的内容。如果是其它行，則驗證資料是否都符合條件。
- 如果符合條件，則再産生一個由1到9九個數随機排列的一維數組作為下一行的内容并驗證資料是否可用。如果不符合條件，則将該行資料設定為0，調整row和col，産生一個由1到9九個數随機排列的一維數組，重新對該行驗證。
- 程式中為了防止産生一維随機數組的方法調用很多次而沒有産生結果，設定一個最多調用該方法次數的門檻值，當達到這個門檻值還沒有産生結果，重新從 row =0 col =0 開始。
import java.util.Random;
/**
*
* @author wangmengjun
*
*/
public class SudokuPuzzleGenerator {
private Random random = new Random();
/**運作此程式300次，最大值是217，最小值11，平均約等于50
* 門檻值設定為220， 能滿足大部分程式，二維矩陣不會置為0，重新再産生值。
*/
private static final int MAX_CALL_RANDOM_ARRAY_TIMES = 220;
/**記錄目前buildRandomArray()方法調用的次數*/
private int currentTimes = 0;
public int[][] generatePuzzleMatrix() {
int[][] randomMatrix = new int[9][9];
for (int row = 0; row < 9; row++) {
if (row == 0) {
currentTimes = 0;
randomMatrix[row] = buildRandomArray();
} else {
int[] tempRandomArray = buildRandomArray();
for (int col = 0; col < 9; col++) {
if (currentTimes < MAX_CALL_RANDOM_ARRAY_TIMES) {
if (!isCandidateNmbFound(randomMatrix, tempRandomArray,
row, col)) {
/*
* 将該行的資料置為0，并重新為其準備一維随機數數組
*/
resetValuesInRowToZero(randomMatrix,row);
row -= 1;
col = 8;
tempRandomArray = buildRandomArray();
}
} else {
/**
* 将二維矩陣中的數值置為0，
* row指派為-1 col指派為8， 下一個執行的就是row =0 col=0，
*
* 重頭開始
*/
row = -1;
col = 8;
resetValuesToZeros(randomMatrix);
currentTimes = 0;
}
}
}
}
return randomMatrix;
}
private void resetValuesInRowToZero(int[][] matrix, int row)
{
for (int j = 0; j < 9; j++) {
matrix[row][j] = 0;
}
}
private void resetValuesToZeros(int[][] matrix) {
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
matrix[row][col] = 0;
}
}
}
private boolean isCandidateNmbFound(int[][] randomMatrix,
int[] randomArray, int row, int col) {
for (int i = 0; i < randomArray.length; i++) {
/**
* 試着給randomMatrix[row][col] 指派,并判斷是否合理
*/
randomMatrix[row][col] = randomArray[i];
if (noConflict(randomMatrix, row, col)) {
return true;
}
}
return false;
}
private boolean noConflict(int[][] candidateMatrix, int row, int col) {
return noConflictInRow(candidateMatrix, row, col)
&& noConflictInColumn(candidateMatrix, row, col)
&& noConflictInBlock(candidateMatrix, row, col);
}
private boolean noConflictInRow(int[][] candidateMatrix, int row, int col) {
/**
* 因為産生随機數矩陣是按照先行後列，從左到右産生的 ，該行目前列後面的所有列的值都還是0， 是以在行比較的時候，
* 隻要判斷該行目前列與之前的列有無相同的數字即可。
*
*/
int currentValue = candidateMatrix[row][col];
for (int colNum = 0; colNum < col; colNum++) {
if (currentValue == candidateMatrix[row][colNum]) {
return false;
}
}
return true;
}
private boolean noConflictInColumn(int[][] candidateMatrix, int row, int col) {
/**
* 與noConflictInRow(...)方法類似：
*
*
* 因為産生随機數矩陣是按照先行後列，從左到右産生的，該列目前行後面的所有行的值都還是0，
*
* 是以在列比較的時候， 隻要判斷該列目前行與之前的行有無相同的數字即可。
*
*/
int currentValue = candidateMatrix[row][col];
for (int rowNum = 0; rowNum < row; rowNum++) {
if (currentValue == candidateMatrix[rowNum][col]) {
return false;
}
}
return true;
}
private boolean noConflictInBlock(int[][] candidateMatrix, int row, int col) {
/**
* 為了比較3 x 3 塊裡面的數是否合理， 需要确定是哪一個Block，我們先要求出3 x 3的起始點。比如：Block 1
* 的起始點是[0][0] Block 2 的起始點是[3]][0]
*
* ... Block 9 的起始點是[6][6]
*/
int baseRow = row / 3 * 3;
int baseCol = col / 3 * 3;
for (int rowNum = 0; rowNum < 8; rowNum++) {
if (candidateMatrix[baseRow + rowNum / 3][baseCol + rowNum % 3] == 0) {
continue;
}
for (int colNum = rowNum + 1; colNum < 9; colNum++) {
if (candidateMatrix[baseRow + rowNum / 3][baseCol + rowNum % 3] == candidateMatrix[baseRow
+ colNum / 3][baseCol + colNum % 3]) {
return false;
}
}
}
return true;
}
/**
* 傳回一個有1到9九個數随機排列的一維數組,
*/
private int[] buildRandomArray() {
currentTimes++;
int[] array = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int randomInt = 0;
/**
* 随機産生一個1到8的随機數，使得該下标的數值與下标為0的數值交換，
*
* 處理20次，能夠擷取一個有1到9九個數随機排列的一維數組,
*/
for (int i = 0; i < 20; i++) {
randomInt = random.nextInt(8) + 1;
int temp = array[0];
array[0] = array[randomInt];
array[randomInt] = temp;
}
return array;
}
/**
* @return the currentTimes
*/
public int getCurrentTimes() {
return currentTimes;
}
/**
* @param currentTimes the currentTimes to set
*/
public void setCurrentTimes(int currentTimes) {
this.currentTimes = currentTimes;
}
} 複制
/**
*
* @author wangmengjun
*
*/
public class Main {
public static void main(String[] args) {
SudokuPuzzleGenerator example = new SudokuPuzzleGenerator();
for(int i=1;i<=3;i++) {
int[][] grids = example.generatePuzzleMatrix();
printArray(grids);
System.out.println();
}
}
/**
* 列印二維數組到控制台
*/
private static void printArray(int[][] grids) {
for (int i = 0; i < 9; i++) {
if (i % 3 == 0) {
System.out.println(" -----------------------");
}
for (int j = 0; j < 9; j++) {
if (j % 3 == 0) {
System.out.print("| ");
}
System.out.print(grids[i][j] == 0 ? " " : grids[i][j]);
System.out.print(" ");
}
System.out.println("|");
}
System.out.println(" -----------------------");
}
} 複制
某次測試的結果：
-----------------------
| 6 2 1 | 3 5 9 | 7 8 4 |
| 4 5 7 | 6 2 8 | 3 1 9 |
| 8 3 9 | 7 4 1 | 2 5 6 |
-----------------------
| 1 4 2 | 5 3 6 | 9 7 8 |
| 3 6 8 | 4 9 7 | 5 2 1 |
| 7 9 5 | 8 1 2 | 4 6 3 |
-----------------------
| 9 8 6 | 2 7 4 | 1 3 5 |
| 2 1 3 | 9 6 5 | 8 4 7 |
| 5 7 4 | 1 8 3 | 6 9 2 |
-----------------------
-----------------------
| 2 5 1 | 8 6 3 | 7 9 4 |
| 7 3 9 | 2 4 5 | 6 1 8 |
| 6 8 4 | 7 9 1 | 2 3 5 |
-----------------------
| 1 2 5 | 4 8 7 | 3 6 9 |
| 4 6 3 | 5 2 9 | 1 8 7 |
| 8 9 7 | 1 3 6 | 5 4 2 |
-----------------------
| 9 1 2 | 6 5 4 | 8 7 3 |
| 3 7 8 | 9 1 2 | 4 5 6 |
| 5 4 6 | 3 7 8 | 9 2 1 |
-----------------------
-----------------------
| 4 3 2 | 8 7 9 | 6 1 5 |
| 6 8 7 | 2 1 5 | 4 3 9 |
| 1 5 9 | 3 4 6 | 7 2 8 |
-----------------------
| 5 9 1 | 4 8 7 | 2 6 3 |
| 3 6 8 | 1 9 2 | 5 7 4 |
| 7 2 4 | 6 5 3 | 8 9 1 |
-----------------------
| 8 4 3 | 7 6 1 | 9 5 2 |
| 2 7 5 | 9 3 8 | 1 4 6 |
| 9 1 6 | 5 2 4 | 3 8 7 |
-----------------------
複制
假設有效性驗證及門檻值設定
針對上述的代碼，我跑10組，每組30個執行個體，看看這300個例子中，産生數獨終盤所需要調用随機産生由1到9的一維數組的次數各是多少， 結果如下：
從上面的結果圖中可以看出：
300個執行個體中，調用次數最小的為11，接近理想最小調用次數9.
最大值為217次，平均約50次。而且大部分執行個體調用的次數在100以内。
從這些資料分析中，上述假設基本上是合适的，門檻值最後選擇了接近實驗最大值217的220（如果嘗試次數大于220還沒有完成，則重新嘗試）。
小結
本文給出了數獨終盤産生的幾種方法，主要有矩陣轉換發以及随機法。
大家如有什麼其它方法，也請告知一下：）