java数独解法[通俗易懂]

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46，售后保障稳定

玩了好久的数独，前几天突发奇想写一个解法，看了好多文章和源码，像回溯法和唯一解法，都不太理解其思路，于是就自己动手写了一个，效率还算可以，有优化的空间，但是懒得优化了。
整体的解法思路就是列出每个空格的备选数，然后逐一尝试，可谓是最笨的解法了，分享给大家图个乐，还希望大佬看到了可以指点一下里面的不足之处。同样因为懒，就没做成web应用，一个main方法自己跑着玩了就。
代码里面包含了1-5级的数独谜题例子（测试用的，就没删除），还有一个从控制台获取谜底的方法。
第一次发文章有些紧张啊，转载的话表明一下出处就行了，废话不多说，上代码

import java.util.*;
public class ShuDuKey { 

static boolean done = false;
public static void  main(String[] args) throws Exception { 

Integer[][] maps1 = { 

{ 
0,0,0,0,0,0,0,0,3},
{ 
8,9,7,6,3,4,5,2,1},
{ 
5,4,0,1,9,0,0,0,0},
{ 
4,0,0,0,1,5,0,7,0},
{ 
0,0,0,8,0,6,0,0,0},
{ 
0,1,0,3,4,0,0,0,2},
{ 
0,0,0,0,2,3,0,6,4},
{ 
0,3,5,0,0,7,2,1,8},
{ 
6,0,0,0,0,0,0,0,0}
};
Integer[][] maps2 = { 

{ 
0,1,0,0,0,6,2,0,0},
{ 
0,0,0,5,3,0,9,0,8},
{ 
6,9,0,2,4,0,0,0,0},
{ 
7,0,0,0,0,0,3,9,0},
{ 
0,3,5,0,6,0,8,4,0},
{ 
0,8,4,0,0,0,0,0,7},
{ 
0,0,0,0,5,4,0,3,1},
{ 
4,0,6,0,8,3,0,0,0},
{ 
0,0,1,9,0,0,0,0,0}
};
Integer[][] maps3 = { 

{ 
4,6,8,0,5,0,0,7,0},
{ 
5,0,0,9,7,0,0,0,3},
{ 
0,0,0,0,0,1,0,0,8},
{ 
0,0,7,0,0,0,0,5,0},
{ 
0,9,0,0,2,0,0,4,0},
{ 
0,5,0,0,0,0,8,0,0},
{ 
6,0,0,2,0,0,0,0,0},
{ 
2,0,0,0,6,5,0,0,4},
{ 
9,7,0,0,0,0,2,8,6}
};
Integer[][] maps4 = { 

{ 
6,4,0,0,3,8,7,0,9},
{ 
5,0,8,9,0,0,0,0,0},
{ 
0,0,0,0,1,0,0,0,0},
{ 
0,3,0,0,0,0,5,0,0},
{ 
0,0,0,7,2,1,0,0,0},
{ 
0,0,9,0,0,0,0,7,0},
{ 
0,0,0,0,9,0,0,0,0},
{ 
0,0,0,0,0,6,4,0,3},
{ 
3,0,1,4,7,0,0,8,5}
};
Integer[][] maps5 = { 

{ 
0,0,4,2,0,0,8,0,0},
{ 
0,0,0,0,0,0,0,0,0},
{ 
0,9,0,0,0,7,0,3,0},
{ 
0,0,5,6,8,0,7,0,0},
{ 
0,3,0,0,1,0,0,9,0},
{ 
0,0,7,0,5,9,1,0,0},
{ 
0,2,0,8,0,0,0,7,0},
{ 
0,0,0,0,0,0,0,0,0},
{ 
0,0,8,0,0,4,2,0,0}
};
Integer[][] mapsMax = { 

{ 
0,0,5,3,0,0,0,0,0},
{ 
8,0,0,0,0,0,0,2,0},
{ 
0,7,0,0,1,0,5,0,0},
{ 
4,0,0,0,0,5,3,0,0},
{ 
0,1,0,0,7,0,0,0,6},
{ 
0,0,3,2,0,0,0,8,0},
{ 
0,6,0,5,0,0,0,0,9},
{ 
0,0,4,0,0,0,0,3,0},
{ 
0,0,0,0,0,9,7,0,0}
};
Integer[][] sMap = scanMap();
doShuDu(sMap);
//doShuDu(maps5);
}
//获得数独谜题
private static Integer[][] scanMap() { 

Scanner sc = new Scanner(System.in);
System.out.println("请输入数独谜题，数字以空格隔开，空白处数字以0代替");
Integer[][] result = new Integer[9][9];
for (int i = 0; i < result.length; i++) { 

System.out.println("请输入第"+(i+1)+"行的数字：");
String[] strArr;
while (true) { 

String str = sc.nextLine();
if("exit".equals(str)){ 

System.exit(0);
}
strArr = str.split("\\s+|,|，");
if(strArr.length != 9){ 

System.out.println("输入错误，请重新输入"+(i+1)+"行数字！");
continue;
}
break;
}
for (int j = 0; j < result[i].length; j++) { 

result[i][j] = Integer.parseInt(strArr[j]);
}
}
System.out.println("谜题输入完毕，正在解析中。。。");
return result;
}
//解析数独谜题
public static void doShuDu(Integer[][] maps){ 

long start = System.currentTimeMillis();
List<String>[][] first = doShuDu1(maps);
if(done){ 

printMap(first);
System.out.println("共用时："+(System.currentTimeMillis()-start));
return;
}
System.out.println("执行第二步————————————————————————————————————————》》》");
List<String>[][] second = doShuDu2(maps,first);
if(done){ 

printMap(second);
System.out.println("共用时："+(System.currentTimeMillis()-start));
return;
}
System.out.println("执行第三步————————————————————————————————————————》》》");
}
//简单数独谜题解析
private static List<String>[][] doShuDu1(Integer[][] maps){ 

List<String>[][] result = new List[9][9];
boolean flag = true;
while(flag){ 

done = true;
flag = false;
for (int i = 0; i < maps.length; i++) { 

for (int j = 0; j < maps[i].length; j++) { 

if(maps[i][j] == 0){ 

result[i][j] = getNumList(i,j,maps);
if(result[i][j] == null){ 

return null;
}
if(result[i][j].size() == 1){ 

maps[i][j] = Integer.parseInt(result[i][j].get(0));
flag = true;
}
done = false;
}else{ 

if(result[i][j] == null){ 

result[i][j] = new ArrayList<>();
result[i][j].add(maps[i][j].toString());
}
}
}
}
}
return result;
}
//复杂数独谜题解析
private static List<String>[][] doShuDu2(Integer[][] maps, List<String>[][] first) { 

Map<String,List<String>[][]> resultMap = new HashMap<>();
Integer[][] tempMaps = arrayCopy(maps);
List<String>[][] result = new List[first.length][];
for (int i = 0; i < first.length; i++) { 

result[i] = first[i].clone();
}
int[][] count = new int[9][9];
boolean flag = true;
while(flag){ 

flag = false;
i:for (int i = 0; i < first.length; i++) { 

for (int j = 0; j < first[i].length; j++) { 

if(result[i][j].size() > 1){ 

boolean re = true;
while(re){ 

re = false;
//无法生成符合要求的二维数组，换数字重新来过
if(count[i][j] < result[i][j].size()){ 

tempMaps[i][j] = Integer.parseInt(result[i][j].get(count[i][j]++));
Integer[][] iarr = arrayCopy(tempMaps);
List<String>[][] ls = doShuDu1(iarr);
if(ls != null) { 

resultMap.put(i+","+j,result);
result = ls;
}else{ 

re = true;
}
}else { 

//该位置的数组应用完毕，仍未得到可用解，则置零
count[i][j] = 0;
//找到上一个选择的数字的位置
for (int k = 0; k < count.length; k++) { 

for (int l = 0; l < count[k].length; l++) { 

if(count[k][l] > 0){ 

i = k;
j = l;
}
}
}
result = resultMap.get(i+","+j);
for (int k = i; k < 9; k++) { 

for (int l = 0; l < 9; l++) { 

if(k == i && l == 0){ 

l = j;
}
tempMaps[k][l] = maps[k][l];
}
}
j--;
break;
}
}
flag = true;
}else{ 

tempMaps[i][j] = Integer.parseInt(result[i][j].get(0));
}
}
}
}
return result;
}
//获取该位置的候选数字
private static List<String> getNumList(int i, int j, Integer[][] maps) { 

List<String> temp = getList();
for (int jj = 0; jj < maps[i].length; jj++) { 

//移除当前同行已经出现的数字
temp.remove(maps[i][jj]+"");
}
for (int ii = 0; ii < maps.length; ii++) { 

//移除当前同列已经出现的数字
temp.remove(maps[ii][j]+"");
}
//移除九宫格已经确定的数字
int d = i/3*3;
int h = j/3*3;
for (int k = d; k < d+3; k++) { 

for (int l = h; l < h+3; l++) { 

temp.remove(maps[k][l]+"");
}
}
if(temp.size() > 0){ 

return temp;
}
return null;
}
//获取1-9的集合
private static List<String> getList(){ 

List<String> result = new ArrayList<>();
for (int i = 1; i < 10; i++) { 

result.add(i+"");
}
return result;
}
//复制二维数组
private static Integer[][] arrayCopy(Integer[][] oo){ 

Integer[][] result = new Integer[oo.length][];
for (int i = 0; i < oo.length; i++) { 

result[i] = oo[i].clone();
}
return result;
}
//打印二维数组
public static void printMap(Object[][] map){ 

for (int i = 0; i < 9; i++) { 

if(i%3==0 && i!=0){ 

System.out.println("---------------------");
}
for (int j = 0; j < 9; j++) { 

if (j==8) { 

System.out.println(map[i][j]);
} else if(j == 2 || j == 5) { 

System.out.print(map[i][j]+" | ");
}else{ 

System.out.print(map[i][j]+" ");
}
}
}
}
}

Jetbrains全家桶1年46，售后保障稳定