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，售后保障稳定