一次Java解析数独的经历

作者：活的精彩的人2011_373 | 来源：互联网 | 2023-02-06 10:54

1.背景中午下楼去吃饭，电梯里看到有人在玩数独，之前也玩过，不过没有用程序去解过，萌生了一个想法，这两天就一直想怎么用程序去解一个数独。要去解开一个数独，首先要先了解数独的游戏规则，这样才能

1. 背景

　　中午下楼去吃饭，电梯里看到有人在玩数独，之前也玩过，不过没有用程序去解过，萌生了一个想法，这两天就一直想怎么用程序去解一个数独。要去解开一个数独，首先要先了解数独的游戏规则，这样才能找到对应的算法去解开。以下是本人用Java语言对数独进行的解析，代码只是抛砖引玉，欢迎大神们给指点指点。

2. 数独知识

　　数独是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复。

　　数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。

水平方向有九横行，垂直方向有九纵列的矩形，画分八十一个小正方形，称为九宫格（Grid），如图一所示，是数独（Sudoku）的作用范围。

三行与三列相交之处有九格，每一单元称为小九宫（Box、Block），简称宫，如图四所示

更多关于数独的知识可以查看百度百科。

3. 生成随机数独

　　在解开一个数独之前，首先要知道数独是怎么生成的，接下来先随机生成一个9*9的数独。

　　生成思路：使用嵌套for循环，给每个格子填数，这个格子中的数必是1-9中的某一个数字，在填第n个格子时，要排除行、列、宫中已经存在的数字，在剩下的数字中随机选一个，如果排除掉行、列、宫中的数字后，已经没有可选数字了，说明这个数独生成错了，while循环重新开始生成，直到生成一个可用的数独。这个地方用到了Set集合及集合中的方法，以下是生成数独的代码。

package com.woasis.demo;

import java.util.*;

/**
 * 数独
 *       1  3  3  4  5  6  7  8  9
 *   1. [1, 2, 3, 4, 5, 6, 7, 8, 9]
 *   2. [1, 2, 3, 4, 5, 6, 7, 8, 9]
 *   3. [1, 2, 3, 4, 5, 6, 7, 8, 9]
 *   4. [1, 2, 3, 4, 5, 6, 7, 8, 9]
 *   5. [1, 2, 3, 4, 5, 6, 7, 8, 9]
 *   6. [1, 2, 3, 4, 5, 6, 7, 8, 9]
 *   7. [1, 2, 3, 4, 5, 6, 7, 8, 9]
 *   8. [1, 2, 3, 4, 5, 6, 7, 8, 9]
 *   9. [1, 2, 3, 4, 5, 6, 7, 8, 9]
 *
 */
public class Sudoku {


    public static void main(String[] args) {
        boolean flag = true;
        while (flag) {
            try {
                start();
                flag = false;
            } catch (ArithmeticException e) {
                System.out.println(e);
            }
        }
    }

    /**
     * 开始生成数独
     */
    private static void start(){
        int[][] source = new int[9][9];
        //第i行
        for (int i=0; i<9; i++){
            // 第i行中的第j个数字
            for (int j=0; j<9; j++){
                //第i行目前的数组
                int[] row = Arrays.copyOf(source[i], j);
                int[] column = new int[i];
                for (int k=0; k){
                    column[k] = source[k][j];
                }
                //所在宫
                List palaceList = new ArrayList<>();
                //取整,获取宫所在数据
                int palaceRow = i/3;
                int palaceColumn = j/3;
                for (int m=0; m<3; m++){
                    for (int n=0; n<3; n++){
                        palaceList.add(source[palaceRow*3+m][palaceColumn*3+n]);
                    }
                }
                source[i][j] = getNumber(row, column, palaceList.stream().mapToInt(Integer::intValue).toArray());;
            }
        }

        //打印随机生成的数独数组
        for (int i=0; i){
            System.out.println(Arrays.toString(source[i]));
        }
    }


    /**
     * 从即没有在行也没有在列中，选出一个随机数
     * @param row
     * @param column
     * @return
     */
    private static int getNumber(int[] row, int[] column, int[] palace ){
        //数组合并，并去重，使用Set集合
        Set mergeSet = new HashSet<>();
        for (int i=0; i){
            mergeSet.add(row[i]);
        }
        for (int j=0; j){
            mergeSet.add(column[j]);
        }

        for (int k=0; k){
            mergeSet.add(palace[k]);
        }
        Set source  = new HashSet<>();
        for (int m=1; m<10; m++){
            source.add(m);
        }
        //取差集
        source.removeAll(mergeSet);
        int[] merge = source.stream().mapToInt(Integer::intValue).toArray();
        //随机返回一个下标
        return merge[getRandomCursor(merge.length)];
    }

    /**
     * 获取一个随机下标
     * @param length
     * @return
     */
    public static int getRandomCursor(int length) {
        return Math.abs(new Random().nextInt())%length;
    }
}

如下图是代码执行后生成的随机数独，行、列、宫中都是1-9个数字，没有重复。

4. 数独的解析

　　数独已经可以生成了，现在就对数独进行解析，首先声明一下，接下来的方法可能对一些数独是解不开的，解开数独不是唯一目的，而是在解析数独中对一些Java知识进行回顾和学习。采用的是隐形唯一候选数法，什么是唯一候选数法呢，就是某个数字在某一行列宫格的候选数中只出现一次，就是这个格子只有一个数可选了，那这个格子里就只能填这个数，这就是唯一候选数法，其实也是排除法。参照的这篇文章进行的一次数独解析，数独解题方法大全，可以参考学习一下。

　　解题思路：

要解析的数独，与数独对应的隐形数组；
排除掉隐形数组中的数字，哪些数字需要排除呢，就是数独中已有的数字，要排除该数字所在的行、列、宫。例如，如下图R4C4格是2，则R4行、C4列以及2所在的宫除了R4C4格子之外，其余的候选数中都不能有2这个数字了。

　　3. 排除一次完成后，看剩下的隐形数组中有没有剩下的单个数，如果有则剩下的这个候选数字就是该位置所要填的数字，有的话需要递归一次2步骤；查看行中有没有唯一的单数，如果有递归一次2步骤；查看列中有没有唯一的单数，如果有递归一次2步骤。

　　4. 排除以部门隐形数字之后，有一些数字是不好排除的，就是一些对数，对数就是在一个宫两个格子，候选数字都是AB，要么这个格子是A要么另一个格子是B。到这个地方之后不好排除，只能用试探法，假如一个格子是A，那么另一个格子是B，这样去试探，如果试探一次后发现试探的对的，那么就确认这种试探是可行的，如果不对，则数值对换。

　　5. 步骤4试探对之后，再从步骤2进行递归，直到获得最终解。

以下是完整代码：

　　其中demo中解析的数独就是数独解题方法大全中隐形唯一候选数法中的一个例子。

  1 package com.woasis.demo;
  2 
  3 import java.util.*;
  4 
  5 public class SudokuCrack {
  6     public static void main(String[] args) {
  7         //生成候选数字表,9行9列，每个格子有9个数字
  8         int[][][] candi = new int[9][9][9];
  9         //初始化候选数字表
 10         for (int i=0; i<9; i++){
 11             for (int j=0; j<9; j++){
 12                 candi[i][j] = new int[]{1,2,3,4,5,6,7,8,9};;
 13             }
 14         }
 15         int[][] sudo = {
 16                 {0,0,9,6,0,0,0,3,0},
 17                 {0,0,1,7,0,0,0,4,0},
 18                 {7,0,0,0,9,0,0,8,0},
 19                 {0,7,0,0,8,0,5,0,0},
 20                 {1,0,0,0,4,0,0,2,0},
 21                 {0,2,0,0,1,0,9,0,0},
 22                 {5,0,0,0,0,9,0,0,0},
 23                 {6,0,0,0,0,3,0,0,2},
 24                 {4,0,0,0,0,0,0,0,1}
 25         };
 26         
 27         if (isOkSudo(candi, sudo)){
 28             System.out.println("校验是不是一个合法数独：是");
 29         }else {
 30             System.out.println("校验是不是一个合法数独：不是");
 31             return;
 32         }
 33 
 34         crack(candi, sudo);
 35 
 36         //获取隐形数组中两个相等的数
 37         List equalCandi = getEqualCandi(candi,sudo);
 38 
 39         //获取其中一个进行试探。
 40         for (CandiInfo info : equalCandi){
 41 
 42             //获取坐标
 43             String[] location = info.location.split("\\|");
 44             String[] ALocation = location[0].split("-");
 45             int aRow = Integer.parseInt(ALocation[0]);
 46             int aColumn = Integer.parseInt(ALocation[1]);
 47             String[] BLocation = location[1].split("-");
 48             int bRow = Integer.parseInt(BLocation[0]);
 49             int bColumn = Integer.parseInt(BLocation[1]);
 50             //获取数据
 51             int[] data = info.nums.stream().mapToInt(Integer::intValue).toArray();
 52 
 53             System.out.println("开始进行试探：data="+data[0]+", "+data[1]+" 位置："+aRow+"-"+aColumn+", "+bRow+"-"+bColumn);
 54 
 55             if(isRight(candi, sudo,aRow, aColumn, bRow, bColumn, data[0], data[1])){
 56                 modifySudoAndCandi(candi, sudo, aRow, aColumn, data[0]);
 57                 modifySudoAndCandi(candi, sudo, bRow, bColumn, data[1]);
 58             }else{
 59                 modifySudoAndCandi(candi, sudo, aRow, aColumn, data[1]);
 60                 modifySudoAndCandi(candi, sudo, bRow, bColumn, data[0]);
 61             }
 62             crack(candi, sudo);
 63         }
 64 
 65 
 66         System.out.println("解析完成：");
 67         for (int i=0; i<9; i++){
 68             System.out.println(Arrays.toString(sudo[i]));
 69         }
 70     }
 71 
 72     /**
 73      * 试探这样的组合是否正确
 74      * @param candi
 75      * @param sudo
 76      * @param aRow
 77      * @param aColumn
 78      * @param bRow
 79      * @param bColumn
 80      * @param data0
 81      * @param data1
 82      * @return
 83      */
 84     private static boolean isRight(int[][][] candi, int[][] sudo, int aRow, int aColumn, int bRow, int bColumn, int data0, int data1){
 85         int[][][] deepCandiCopy = new int[9][9][9];
 86         for (int i=0; i<9; i++){
 87             deepCandiCopy[i] = candi[i].clone();
 88         }
 89         int[][] deepSudoCopy = new int[9][9];
 90         for (int i=0; i<9; i++){
 91             deepSudoCopy[i]= sudo[i].clone();
 92         }
 93         modifySudoAndCandi(deepCandiCopy, deepSudoCopy, aRow, aColumn, data0);
 94         modifySudoAndCandi(deepCandiCopy, deepSudoCopy, bRow, bColumn, data1);
 95 
 96         crack(deepCandiCopy, deepSudoCopy);
 97 
 98         return isOkSudo(deepCandiCopy,deepSudoCopy);
 99     }
100 
101     /**
102      * 隐藏数法解析数独
103      * @param candi 隐藏数数组
104      * @param sudo 要解的数独
105      */
106     private static void crack(int[][][] candi, int[][] sudo){
107 
108         eliminateCandidateNumbers(candi, sudo);
109 
110         //一轮结束后，查看隐形数组里有没有单个的，如果有继续递归一次
111         boolean flag = false;
112         for (int k=0; k<9; k++){
113             for (int q=0; q<9; q++){
114                 int f = sudo[k][q];
115                 if (f == 0){
116                     int[] tmp = candi[k][q];
117                     Set s = new HashSet<>();
118                     for (int t=0; t){
119                         if (tmp[t]>0){
120                             s.add(tmp[t]);
121                         }
122                     }
123                     //说明有单一成数据可以用的
124                     if (s.size() == 1){
125                         flag = true;
126                         modifySudoAndCandi(candi, sudo, k, q, s.stream().mapToInt(Integer::intValue).toArray()[0]);
127                     }
128                 }
129             }
130         }
131         //如果有确定的单个数，进行递归一次
132         if (flag){
133             crack(candi, sudo);
134         }
135         //查看行有没有唯一数字，有就递归一次
136         flag = checkRow(candi, sudo);
137         if (flag){
138             crack(candi, sudo);
139         }
140         //查看列有没有唯一数字，有就递归一次
141         flag = checkColumn(candi, sudo);
142         if (flag){
143             crack(candi, sudo);
144         }
145     }
146 
147     /**
148      * 剔除数组中的候选数字,剔除行、列、宫
149      * @param candi
150      * @param sudo
151      */
152     private static void eliminateCandidateNumbers(int[][][] candi, int[][] sudo){
153         for (int i=0; i<9; i++){
154             for (int j=0; j<9; j++){
155                 int num = sudo[i][j];
156                 //剔除备选区数字
157                 if (num>0){
158                     candi[i][j] = new int[]{0,0,0,0,0,0,0,0,0};
159                     for (int m=0; m<9; m++){
160                         int[] r = candi[i][m];
161                         r[num-1] = 0;
162                         int[] c = candi[m][j];
163                         c[num-1] = 0;
164                     }
165                     //摒除宫里的唯一性
166                     //取整,获取宫所在数据
167                     int palaceRow = i/3;
168                     int palaceColumn = j/3;
169                     for (int m=0; m<3; m++){
170                         for (int n=0; n<3; n++){
171                             int[] p = candi[palaceRow*3+m][palaceColumn*3+n];
172                             p[num-1] = 0;
173                         }
174                     }
175                 }
176             }
177         }
178     }
179 
180     /**
181      * 修改数独的值并剔除隐形数字
182      * @param candi
183      * @param sudo
184      * @param row
185      * @param column
186      * @param v
187      */
188     private static void modifySudoAndCandi(int[][][] candi, int[][] sudo, int row, int column, int v){
189         //修改数独的值
190         sudo[row][column] = v;
191 
192         //剔除备选区数字
193         candi[row][column] = new int[]{0,0,0,0,0,0,0,0,0};
194         for (int m=0; m<9; m++){
195             int[] r = candi[row][m];
196             r[v-1] = 0;
197             int[] c = candi[m][column];
198             c[v-1] = 0;
199         }
200         //摒除宫里的唯一性
201         //取整,获取宫所在数据
202         int palaceRow = row/3;
203         int palaceColumn = column/3;
204         for (int m=0; m<3; m++){
205             for (int n=0; n<3; n++){
206                 int[] p = candi[palaceRow*3+m][palaceColumn*3+n];
207                 p[v-1] = 0;
208             }
209         }
210     }
211 
212     /**
213      * 查看行中的隐形数组有没有唯一存在的候选值
214      * @param candi
215      * @param sudo
216      * @return
217      */
218     private static boolean checkRow(int[][][] candi, int[][] sudo){
219         boolean flag = false;
220         for (int i=0; i<9; i++){
221             Map> candiMap = new HashMap<>();
222             int[] row = sudo[i];
223             for (int j=0; j<9; j++){
224                 if (row[j]==0){
225                     int[] tmp = candi[i][j];
226                     Set set = new HashSet<>();
227                     for (int k=0; k){
228                         if (tmp[k]>0) {
229                             set.add(tmp[k]);
230                         }
231                     }
232                     candiMap.put(String.valueOf(i)+"-"+String.valueOf(j), set);
233                 }
234             }
235             if (candiMap.size()>0) {
236                 Set keys = candiMap.keySet();
237                 Iterator iterator = keys.iterator();
238                 while (iterator.hasNext()){
239                     String tKey = (String) iterator.next();
240                     //要查看的集合
241                     Set set = deepCopySet(candiMap.get(tKey));
242                     //深复制
243                     Set tmpKeys = candiMap.keySet();
244                     Iterator tmpKeyIterator =tmpKeys.iterator();
245                     while (tmpKeyIterator.hasNext()){
246                         String tmpKey = (String) tmpKeyIterator.next();
247                         //取交集
248                         if (!tKey.equals(tmpKey)) {
249                             set.removeAll(candiMap.get(tmpKey));
250                         }
251                     }
252                     //交集取完，集合空了,看下一个结合有没有
253                     if (set.size() == 0){
254                         continue;
255                     }else {
256                         //还剩一个唯一值
257                         if (set.size() == 1){
258                             String[] ks = tKey.split("-");
259                             flag = true;
260                             modifySudoAndCandi(candi, sudo, Integer.parseInt(ks[0]),Integer.parseInt(ks[1]), set.stream().mapToInt(Integer::intValue).toArray()[0] );
261                         }
262                     }
263                 }
264             }
265         }
266         return flag;
267     }
268 
269     /**
270      * 查看列中的隐形数组有没有唯一存在的候选值
271      * @param candi
272      * @param sudo
273      * @return
274      */
275     private static boolean checkColumn(int[][][] candi, int[][] sudo){
276         boolean flag = false;
277         for (int i=0; i<9; i++){
278             Map> candiMap = new HashMap<>();
279             for (int j=0; j<9; j++){
280                 if (sudo[j][i]==0){
281                     int[] tmp = candi[j][i];
282                     Set set = new HashSet<>();
283                     for (int k=0; k){
284                         if (tmp[k]>0) {
285                             set.add(tmp[k]);
286                         }
287                     }
288                     candiMap.put(String.valueOf(i)+"-"+String.valueOf(j), set);
289                 }
290             }
291             if (candiMap.size()>0) {
292                 Set keys = candiMap.keySet();
293                 Iterator iterator = keys.iterator();
294                 while (iterator.hasNext()){
295                     String tKey = (String) iterator.next();
296                     //要查看的集合
297                     Set set = deepCopySet(candiMap.get(tKey));
298                     //深复制
299                     Set tmpKeys = candiMap.keySet();
300                     Iterator tmpKeyIterator =tmpKeys.iterator();
301                     while (tmpKeyIterator.hasNext()){
302                         String tmpKey = (String) tmpKeyIterator.next();
303                         //取交集
304                         if (!tKey.equals(tmpKey)) {
305                             set.removeAll(candiMap.get(tmpKey));
306                         }
307                     }
308                     //交集取完，集合空了,看下一个结合有没有
309                     if (set.size() == 0){
310                         continue;
311                     }else {
312                         //还剩一个唯一值
313                         if (set.size() == 1){
314                             String[] ks = tKey.split("-");
315                             flag = true;
316                             modifySudoAndCandi(candi,sudo, Integer.parseInt(ks[1]),Integer.parseInt(ks[0]),set.stream().mapToInt(Integer::intValue).toArray()[0]);
317                         }
318                     }
319                 }
320             }
321         }
322         return flag;
323     }
324 
325     /**
326      * 获取隐形数字中宫中两个相等的数字
327      * @return
328      */
329     private static  List getEqualCandi(int[][][] candi, int[][] sudo){
330         //找到两个相等数字
331         //遍历宫
332         List maps = new ArrayList<>();
333         for (int m=0; m<3; m++){
334             for (int n=0; n<3; n++){
335                 Map> palaceMap = new HashMap<>();
336                 for (int i=0; i<3; i++){
337                     for (int j=0; j<3; j++){
338                         int sudoRow = m*3 + i;
339                         int sudoColumn = n*3 +j;
340                         if (sudo[sudoRow][sudoColumn] == 0) {
341                             int[] tmpX = candi[sudoRow][sudoColumn];
342                             Set set = new HashSet<>();
343                             for (int k=0; k){
344                                 if (tmpX[k]>0) {
345                                     set.add(tmpX[k]);
346                                 }
347                             }
348                             if (set.size() == 2) {
349                                 palaceMap.put(String.valueOf(sudoRow) + "-" + String.valueOf(sudoColumn), set);
350                             }
351                         }
352                     }
353                 }
354 
355                 Set pSet = palaceMap.keySet();
356                 Iterator pIterator = pSet.iterator();
357                 while (pIterator.hasNext()){
358                     String key = (String) pIterator.next();
359                     Iterator tmpIterator = pSet.iterator();
360                     while (tmpIterator.hasNext()){
361                         String tmpKey = (String) tmpIterator.next();
362                         if (!key.equals(tmpKey)){
363                             Set tmpIntSet = palaceMap.get(tmpKey);
364                             Set palaceIntSet = deepCopySet(palaceMap.get(key));
365                             palaceIntSet.removeAll(tmpIntSet);
366                             //说明两个集合相等
367                             if (palaceIntSet.size() == 0){
368                                 CandiInfo candiInfo = new CandiInfo();
369                                 candiInfo.location = key+"|"+tmpKey;
370                                 candiInfo.nums = palaceMap.get(key);
371                                 maps.add(candiInfo);
372                             }
373                         }
374                     }
375                 }
376             }
377         }
378         List infos = new ArrayList<>();
379         CandiInfo candiInfo = null;
380         for (CandiInfo info : maps){
381             if (candiInfo == null){
382                 candiInfo = info;
383             }else {
384                 if (candiInfo.nums.equals(info.nums)) {
385                     infos.add(info);
386                 }
387                 candiInfo = info;
388             }
389         }
390         return infos;
391     }
392 
393     /**
394      * 校验这个数独是不是还满足数独的特点
395      * 思路：
396      * 1. 校验行和列有没有重复的数字
397      * 2. 校验数独是0的格子，对应的隐形数组还有没有值，如果没有候选值，肯定是某一个地方填错了
398      * @param candi  隐形数组
399      * @param sudo  数独二维数组
400      * @return
401      */
402     private static boolean isOkSudo(int[][][] candi, int[][] sudo){
403         boolean flag = true;
404         for (int i=0; i<9; i++){
405             //校验行
406             Set rowSet = new HashSet<>();
407             //校验列
408             Set clumnSet = new HashSet<>();
409             for (int j=0; j<9; j++){
410                 int rowV = sudo[i][j];
411                 int cloumV = sudo[j][i];
412                 if (rowV>0){
413                     if (!rowSet.add(rowV)) {
414                         flag = false;
415                         break;
416                     }
417                 }
418                 if (cloumV>0){
419                     if (!clumnSet.add(cloumV)) {
420                         flag = false;
421                         break;
422                     }
423                 }
424 
425             }
426             if (!flag){
427                 break;
428             }
429         }
430         //校验隐形数字是否为空
431         for (int m=0; m<9; m++){
432             for (int n=0; n<9; n++){
433                 if (sudo[m][n] == 0){
434                     int[] s = candi[m][n];
435                     Set set = new HashSet<>();
436                     for (int p=0; p){
437                         if (s[p]>0){
438                             set.add(s[p]);
439                         }
440                     }
441                     if (set.size() == 0){
442                         flag =  false;
443                         break;
444                     }
445                 }
446             }
447         }
448         return  flag;
449     }
450 
451     /**
452      * 深度复制set集合
453      * @param source
454      * @return
455      */
456     private static Set deepCopySet(Set source){
457         Set deepCopy = new HashSet<>();
458         Iterator iterator = source.iterator();
459         while (iterator.hasNext()){
460             deepCopy.add((Integer) iterator.next());
461         }
462         return deepCopy;
463     }
464 
465     public static class CandiInfo{
466         String location;
467         Set nums;
468     }
469 }

以下是解析出的结果：

5. 经验总结

　　从有解析数独这个想法，到代码实现，大约经历了3天左右，在这个过程中会想一下怎么去构造解析，以及代码的逻辑，和解题的思路。对其中的收获就是Set集合的用法，数组的深浅复制，值传递引用传递等，以及怎么去构建一个数据结构来表示想要表达的东西。有些东西确实是了解，但是真正用的时候可能觉得自己知道的还不够，知识需要去积累学习，希望通过一个数独的解题思路，来温故一些基础知识。感谢阅读！