前言

半個月前成功嘗試完成了數(shù)獨(dú)的求解算法。但是總感覺有什么事情還沒有完成。思來想去，原來是只是求解了數(shù)獨(dú)，但是數(shù)獨(dú)不知從何而來。是否可以通過算法自動生成一個數(shù)獨(dú)？恰逢清明三天假，在節(jié)日來臨之前，用一晚上進(jìn)行了實(shí)現(xiàn)。

數(shù)獨(dú)規(guī)則

首先看一下數(shù)獨(dú)

屏幕快照 2018-03-25 下午6.30.52.png

數(shù)獨(dú)的規(guī)則比較簡單：

• 每一行包括了1到9的數(shù)字，并且不能重復(fù)。
• 每一列包括了1到9的數(shù)字，并且不能重復(fù)。
• 每一組包括了1到9的數(shù)字，并且不能重復(fù)。

數(shù)獨(dú)題的基本要求：
數(shù)獨(dú)題的要求為數(shù)獨(dú)要有唯一解，表現(xiàn)在：

• 已填滿的空格不能與它所在的行、列、組重合。
• 采用遍歷的方式能夠找到數(shù)獨(dú)的解，并且解是唯一的。

生成數(shù)獨(dú)題的步驟和流程圖

步驟

• 步驟一、生成一個所有單元都是空的空數(shù)獨(dú)
• 步驟二、隨機(jī)選擇一個空單元，找到它的所有可能解
• 步驟三、遍歷空單元的每個可能解。將每個解填入，求的填入后數(shù)獨(dú)的解的個數(shù)。
• 步驟四、如果有可能解的填入之后數(shù)獨(dú)解個數(shù)為1，則此填入此可能解之后的數(shù)獨(dú)即為生成的數(shù)獨(dú)，否則，隨機(jī)選擇一個可能解，進(jìn)行步驟二。
  代碼

獲取數(shù)獨(dú)的核心代碼如下：

         // 獲取空數(shù)獨(dú)  對應(yīng)步驟一    
        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 {
           //隨機(jī)選擇一個空單元，求出它的可能解 對應(yīng)步驟二
            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();


         //   遍歷空單元的每個可能解。將每個解填入，求的填入后數(shù)獨(dú)的解的個數(shù)。對應(yīng)步驟三
            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+"");
 // 如果有可能解的填入之后數(shù)獨(dú)解個數(shù)為1，則此填入此可能解之后的數(shù)獨(dú)即為生成的數(shù)獨(dú) 對應(yīng)步驟四
                if (solutionNum == 1) {
                    break a;

                } else if (solutionNum > 1) {
                    currentTreeSet.add(suitValue[I]);
                }
            }
            Integer[] solutions = new Integer[currentTreeSet.size()];
            currentTreeSet.toArray(solutions);
 // 如果未有可能解的填入之后數(shù)獨(dú)解個數(shù)為1，隨機(jī)選擇一個可能解，進(jìn)行步驟二。
            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));
        }

流程圖

數(shù)獨(dú)生成器.jpg

判斷數(shù)獨(dú)是否只有一個解的步驟和流程圖

步驟

• 步驟一、利用數(shù)獨(dú)求解算法獲取數(shù)獨(dú)的一個解。并且改進(jìn)數(shù)獨(dú)求解的算法，每次選擇一個空單元時，記錄未被驗(yàn)證的解集。
• 步驟二、如果沒有成功，則此數(shù)獨(dú)沒有解，返回。
• 步驟三、按照解數(shù)獨(dú)時選擇空單元的順序，從后往前遍歷。每遍歷一個單元時，將之后的單元置空。
• 步驟四、從后往前遍歷單元時，遍歷每個單元的未被驗(yàn)證的解集。將解決中的解填入單元中，求此時數(shù)獨(dú)是否有解。
• 步驟五、如果按照五的步驟能夠發(fā)現(xiàn)解，說明此數(shù)獨(dú)有多解，否則，數(shù)獨(dú)只有一個解。
  ** 代碼**

@Override
    public int findSolution(char[] charArray) {
        initData(charArray);
        System.out.println("");
//對應(yīng)步驟一 利用數(shù)獨(dú)求解算法獲取數(shù)獨(dú)的一個解。并且改進(jìn)數(shù)獨(dú)求解的算法，每次選擇一個空單元時，記錄未被驗(yàn)證的解集。
        if (!findSoduResult()) {
// 步驟二、如果沒有成功，則此數(shù)獨(dú)沒有解，返回。
            return NONE_RESULT;
        }
        System.out.println("findSoduResult");
//步驟三、按照解數(shù)獨(dú)時選擇空單元的順序，從后往前遍歷。每遍歷一個單元時，將之后的單元置空。
        for (int m = 80; m >= 0; m--) {
            int i = 80 / 9;
            int k = 80 % 9;
步驟四、從后往前遍歷單元時，遍歷每個單元的未被驗(yàn)證的解集。將解決中的解填入單元中，求此時數(shù)獨(dú)是否有解。
            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;
//步驟五、如果按照五的步驟能夠發(fā)現(xiàn)解，說明此數(shù)獨(dú)有多解。
                if (findSoduResult()) {
                    return MULTI_RESULT;
                }
            }
            soduNodes[i][k].value = 0;

        }
//步驟五、如果按照五的步驟不能夠發(fā)現(xiàn)解，說明此數(shù)獨(dú)有唯一解。
        return SINGLE_RESULT;
    }

流程圖：

判斷數(shù)獨(dú)是否唯一解.jpg

運(yùn)行

以下是整個算法運(yùn)行過程：

********************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 * 

聯(lián)系我

郵箱：
sysuzhuminh@gmail.com
apk下載：
https://www.pgyer.com/ezPc
GitHub:
https://github.com/huolizhuminh/sodu
qq群：

數(shù)獨(dú)愛好者群二維碼.png