# 数独终盘生成的几种方法

1. 产生一个数独终盘（9X9）
2. 在第一步产生的数独终盘中，根据难易程度，在终盘上挖掉不同数目的数字。

## 矩阵转换法

• 先给定几个可用数独终盘作为备选种子矩阵。
• 产生一个随机数，随机选中其中的一个作为种子矩阵。

```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();
}
}```
```}
```

### 两个数互相交换法

```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九个数随机排列的一维数组。
• 循环行(下标从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 |
-----------------------
```

300个实例中，调用次数最小的为11，接近理想最小调用次数9. 最大值为217次，平均约50次。而且大部分实例调用的次数在100以内。

## 小结

0 条评论

• ### [动态规划] 数字三角形问题（一维数组实现）

一个数字三角宝塔。设数字三角形中的数字为不超过100的正整数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走。假设三角形行数小于等于100编程求解...

• ### 24点解法

24点游戏是小时候很喜欢玩的游戏，给出4个数，通过加、减、乘、除完成运算，最终得到结果为24。比如数字1、3、5和9，可以通过3 * 5 + 9 * 1 得到结...

• ### 可视化排序实践之冒泡排序

这样，一个简单地，模拟执行结合排序变化的例子就完成了。:) 有兴趣的读者可以试一试。

• ### LeetCode 75. Sort Colors题目分析

给定一个包含红，白，蓝且长度为 n 的数组，将数组元素进行分类使相同颜色的元素相邻，并按照红、白、蓝的顺序进行排序。 我们可以使用整数 0，1 和 2 分别代...

• ### 1009 产生数 2002年NOIP全国联赛普及组

009 产生数 2002年NOIP全国联赛普及组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 De...

• ### POJ-3866-Exclusive Access 2

ACM模版 描述 ? ? ? 题解 这绝对是我做过最长的题，也是最难理解的题，翻译成中文都很难理解。 简单的说，就是安排任务使用两个资源的顺序，使最坏情况下，执...

• ### HDU 3078 Network

Problem Description The ALPC company is now working on his own network system,...

• ### 最大子段和问题

问题描述： 给定长度为n的整数序列，a[1...n], 求[1,n]某个子区间[i , j]使得a[i]+…+a[j]和最大，或者求出最大的这个和。如果该序列的...

• ### POJ-1088 滑雪 （记忆化搜索，dp）

滑雪 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 86318 ...