数独终盘生成的几种方法
数独（すうどく，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还没有完成，则重新尝试）。
小结
本文给出了数独终盘产生的几种方法，主要有矩阵转换发以及随机法。
大家如有什么其它方法，也请告知一下：）
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-04-14，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录