前言
半个月前成功尝试完成了数独的求解算法。但是总感觉有什么事情还没有完成。思来想去，原来是只是求解了数独，但是数独不知从何而来。是否可以通过算法自动生成一个数独？恰逢清明三天假，在节日来临之前，用一晚上进行了实现。
数独规则
首先看一下数独
屏幕快照 2018-03-25 下午6.30.52.png
数独的规则比较简单：
- 每一行包括了1到9的数字，并且不能重复。
- 每一列包括了1到9的数字，并且不能重复。
- 每一组包括了1到9的数字，并且不能重复。
数独题的基本要求：
数独题的要求为数独要有唯一解，表现在：
- 已填满的空格不能与它所在的行、列、组重合。
- 采用遍历的方式能够找到数独的解，并且解是唯一的。
生成数独题的步骤和流程图
步骤
- 步骤一、生成一个所有单元都是空的空数独
- 步骤二、随机选择一个空单元，找到它的所有可能解
- 步骤三、遍历空单元的每个可能解。将每个解填入，求的填入后数独的解的个数。
- 步骤四、如果有可能解的填入之后数独解个数为1，则此填入此可能解之后的数独即为生成的数独，否则，随机选择一个可能解，进行步骤二。
代码
获取数独的核心代码如下：
// 获取空数独 对应步骤一
char[] charArray = new char[81];
for (int i = 0; i < 81; i++) {
charArray[i] = '0';
}
TreeSet<Integer> indexs = new TreeSet<>();
TreeSet<Object> currentTreeSet = new TreeSet<>();
int time=0;
a: do {
//随机选择一个空单元，求出它的可能解 对应步骤二
int index = (int) (Math.random() * 81);
if (indexs.contains(index)) {
continue;
}
indexs.add(index);
initData(charArray);
int list = index / 9;
int row = index % 9;
System.out.println("list:"+list+"row"+row+"index"+index);
SoduNode currentNode = soduNodes[list][row];
Integer[] suitValue = currentNode.getSuitValue();
// 遍历空单元的每个可能解。将每个解填入，求的填入后数独的解的个数。对应步骤三
boolean hasOnlySolution = false;
currentTreeSet.clear();
b: for (int i = 0; i < suitValue.length; i++) {
currentNode.value = suitValue[I];
charArray[index] = (char) ('0' + suitValue[I]);
int solutionNum = getSolutionNum(charArray);
System.out.println("solutionNum"+solutionNum+"");
// 如果有可能解的填入之后数独解个数为1，则此填入此可能解之后的数独即为生成的数独 对应步骤四
if (solutionNum == 1) {
break a;
} else if (solutionNum > 1) {
currentTreeSet.add(suitValue[I]);
}
}
Integer[] solutions = new Integer[currentTreeSet.size()];
currentTreeSet.toArray(solutions);
// 如果未有可能解的填入之后数独解个数为1，随机选择一个可能解，进行步骤二。
int randomSolution = (int) (Math.random() * solutions.length);
currentNode.value = solutions[randomSolution];
charArray[index] = (char) ('0' + solutions[randomSolution]);
time++;
System.out.println("********************"+time+"*********************");
for (int i = 0; i < 9; i++) {
if(i%3==0){
System.out.println("********************************************");
}
System.out.println(SoduNode.getNodesValue(soduNodes[i][0].listNode));
}
System.out.println("*****************************************");
System.out.println("\n");
} while (true);
System.out.println("********************result*********************");
for (int i = 0; i < 9; i++) {
System.out.println(SoduNode.getNodesValue(soduNodes[i][0].listNode));
}
流程图
数独生成器.jpg
判断数独是否只有一个解的步骤和流程图
步骤
- 步骤一、利用数独求解算法获取数独的一个解。并且改进数独求解的算法，每次选择一个空单元时，记录未被验证的解集。
- 步骤二、如果没有成功，则此数独没有解，返回。
- 步骤三、按照解数独时选择空单元的顺序，从后往前遍历。每遍历一个单元时，将之后的单元置空。
- 步骤四、从后往前遍历单元时，遍历每个单元的未被验证的解集。将解决中的解填入单元中，求此时数独是否有解。
- 步骤五、如果按照五的步骤能够发现解，说明此数独有多解，否则，数独只有一个解。
** 代码**
@Override
public int findSolution(char[] charArray) {
initData(charArray);
System.out.println("");
//对应步骤一 利用数独求解算法获取数独的一个解。并且改进数独求解的算法，每次选择一个空单元时，记录未被验证的解集。
if (!findSoduResult()) {
// 步骤二、如果没有成功，则此数独没有解，返回。
return NONE_RESULT;
}
System.out.println("findSoduResult");
//步骤三、按照解数独时选择空单元的顺序，从后往前遍历。每遍历一个单元时，将之后的单元置空。
for (int m = 80; m >= 0; m--) {
int i = 80 / 9;
int k = 80 % 9;
步骤四、从后往前遍历单元时，遍历每个单元的未被验证的解集。将解决中的解填入单元中，求此时数独是否有解。
TreeSet<Integer> allValueSet = soduNodes[i][k].getAllValueSet();
if (!soduNodes[i][k].needTobeSolve || allValueSet.size() == 1) {
if (soduNodes[i][k].needTobeSolve) {
soduNodes[i][k].value = 0;
}
continue;
}
TreeSet<Integer> leftAllValue = soduNodes[i][k].getAllValueSet();
Iterator<Integer> iterator = leftAllValue.iterator();
a: while (iterator.hasNext()) {
Integer leftValue = (Integer) iterator.next();
if (leftValue == soduNodes[i][k].value) {
continue a;
}
soduNodes[i][k].value = leftValue;
//步骤五、如果按照五的步骤能够发现解，说明此数独有多解。
if (findSoduResult()) {
return MULTI_RESULT;
}
}
soduNodes[i][k].value = 0;
}
//步骤五、如果按照五的步骤不能够发现解，说明此数独有唯一解。
return SINGLE_RESULT;
}
流程图：
判断数独是否唯一解.jpg
运行
以下是整个算法运行过程：
********************result*********************
********************************************
0 9 0 * 0 4 6 * 0 0 3 *
4 0 0 * 0 1 0 * 0 0 6 *
0 0 0 * 0 9 0 * 2 7 4 *
********************************************
1 0 0 * 0 8 0 * 0 0 0 *
0 0 0 * 0 7 0 * 0 5 0 *
9 0 5 * 0 6 0 * 0 3 1 *
********************************************
0 0 0 * 0 3 0 * 0 0 0 *
8 2 6 * 4 0 1 * 3 0 7 *
3 0 0 * 0 0 8 * 0 6 0 *
联系我
邮箱：
sysuzhuminh@gmail.com
apk下载：
https://www.pgyer.com/ezPc
GitHub:
https://github.com/huolizhuminh/sodu
qq群：
数独爱好者群二维码.png
网友评论