数独java版

在生成数独题目时，流程是：生成一个完整的数独——随机挖空——解题——如果只有一个解，则生成该题目，如果有多个解，则重新挖空。

数独题目的生成涉及的一个算法是回溯法，这里面的完整数独的生成、求解都用到了回溯法。

生成完整数独

在生成部分，先生成所有宫的1，再生成所有宫的2，以此类推。

主要有三个值：

boolean[][][] placeable = new boolean[9][9][9];// 第几个数字，第几宫，第几号位置

int[][] stepPos = new int[9][9];// 第几个数字，第几宫，值是位置

int[][] result=new int[9][9];

placeable 用来存储每个数字在每个宫的每个位置是否可以放置，初始时，只要该位置没有被占就可以放置，在生成数独的过程中，尝试在这个位置放置某数，如果与行列宫有冲突，则需更新placeable 。

stepPos 用来存储某个宫中已经放置的数字的位置。

result既是存储生成的数独。

生成阶段的回溯是通过一个双重循环实现的：

private static int[][] tryGenerateFinalAnswer() {
    int[][] result=new int[9][9];
    for (int number = 0; number < 9; number++) {
        //注意这里没有gong++
        for (int gong = 0; gong < 9;) {
            ArrayList<Integer> PlaceableList = getPlaceableList(number, gong);
            int length = PlaceableList.size();
            //回溯算法的重点就是这里，如果当前一步走不下去，就返回上一步，重走
            if (length <= 0) {					
                resetPlaceable(result,number, gong);
                gong--;
                if (gong < 0) {
                    number--;
                    gong = 8;
                }
                removeNum(result, number, gong);
                
            }else {
                int pos = PlaceableList.get(random.nextInt(length));
                if (isCollide(result,number, gong, pos)) {
                    placeable[number][gong][pos] = false;
                }else {
                    addNum(result, number, gong, pos);
                    gong++;
                }
            }
        }
    }
    return result;
}

其实一开始写数独生成的时候，想的是先随机生成第一个宫的所有数字，第二个宫在不与第一个宫冲突的情况下生成所有数字，以此类推，就是以宫为主顺序生成数独。这样的做法理论上可行，但实际上需要非常大量的运算，而且极易容易冲突。因为后面一旦走不下去，往往要返回一个宫的所有数字，但是以数字为主顺序，走不下去就只需要返回一个宫的一个数字。

随机挖空

随机挖空的部分比较简单，但是要注意使用另一个二维数组来存储生成的题目，不要在完整的数组上动，因为后面解题部分要对比完整的数组，看看解题是否正确。

解题

解题部分时参考了另一位大佬的代码，之前看的时候距今已经过了一年有余，所以找不到他的博客了。

解题部分的思想非常的巧妙，首先将数独题目中1-9这9个数，转化成二进制中1的位置。000000100表示3，如001000000表示7，而题目中空缺的位置，则以111111111表示，这表示这个位置的候选数字是1~9。

然后根据已确定的数字分析更新空格的候选数字，比如候选值有2、3、6，则该空的二进制数就是000100110。当二进制中只有一个1，则表示该值可以确定，使用Integer.bitCount(data[m][i]) 方法判断二进制中有几个1。

这里的分析主要就是排除行列宫中已有的数字。

一直循环分析所有空格，直到不能从已确定的数字中分析出新的候选信息，就从一个空格的候选值中假设一个值填进格子中，再以此推测剩余的空格，直到所有格子都被填满，或者是填补下去，那么就返回之前的假设，填其他值，以此类推。这其实和我们正常解数独的思路是一样的。

如果题目已经求得两个解，则返回，重新生成题目。因为这个题目是从一个完整的数独挖空而来，所以不可能没有解。

解题的回溯部分主要通过递归实现：

private static void solve(int[][] data) {
    if(resultNum>1) {
        return;
    }
    analyse(data);
    int result = check(data);
    if (result == 1) {
        int[] position = findLessCandidatesPos(data);
        int pv = data[position[0]][position[1]];
        int pvcount = Integer.bitCount(pv);
        for (int i = 0; i < pvcount; i++) {
            int testV = 1 << ((int) (Math.log(Integer.highestOneBit(pv)) / Math.log(2)));
            pv ^= testV;
            int[][] copy = copyArray(data);
            copy[position[0]][position[1]] = testV;
            //这里不理解为什么要返回
            if(i>1) {
                return;
            }
            solve(copy);
        }	        
    }else if (result == 0) {
        resultNum++;
        System.out.println("------------------------------------第"+(resultNum)+"个答案---------------------"
                + (System.nanoTime() - startTime) / 1000000.0 + "ms---");
        answer=data;
        binaryToInt(answer);
        printByRow(answer);
    }
}

解题中值得借鉴的就是将数字1~9表示成二进制中1的位置，这样可以很好的表示候选值。除了数独中的数字与候选值表示成二进制中1的位置，

在找候选值的方法中，也是用三个二进制数分别表示当前值所在的行、列、宫已经存在的数字，来计算候选值的。

在判断是否冲突的方法，也是用三个二进制数分别表示当前值所在的行、列、宫已经存在的数字，来判断是否冲突的。

唯一解的数独题目生成器完整代码：

import java.util.ArrayList;
import java.util.Random;

//int[][] 也是引用传递
public class Sudoku {
    static boolean[][][] placeable = new boolean[9][9][9];// 第几个数字，第几宫，第几号位置
    static int[][] stepPos = new int[9][9];// 第几个数字，第几宫，值是位置
    static Random random = new Random();
    static int resultNum;
    static long startTime;
    static int[][] answer;

    //生成终局（唯一），生成题目（需要试出只有一个解的题目），生成结果（程序做该题，与生成终局相同）
    public static void main(String[] args) {
        int[][] finalAnswer = generateFinalAnswer();
        int[][] qstGong;
        int[][] qstRow;
        int[][] anwserRow;
        answer = new int[9][9];
        do {
            System.out.println("完整的数独");
            printByGong(finalAnswer);
            qstGong = digholes(finalAnswer, 40);
            System.out.println("出的题目");
            printByGong(qstGong);
            qstRow = gongConvertToRow(qstGong);
            anwserRow = toBinary(qstRow);
            resultNum = 0;
            startTime = System.nanoTime();
            solve(anwserRow);
        } while (resultNum != 1);
    }

    //---------------生成终局---------------------//
    private static int[][] generateFinalAnswer() {
        int[][] result = null;
        do {
            initData();
            result = tryGenerateFinalAnswer();
        } while (result == null);
        return result;
    }

    private static void initData() {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                for (int n = 0; n < 9; n++) {
                    placeable[i][j][n] = true;
                }
            }
        }
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                stepPos[i][j] = -1;
            }
        }
    }

    //一般循环250多次就能找到一个完整的数独
    private static int[][] tryGenerateFinalAnswer() {
        int[][] result = new int[9][9];
        for (int number = 0; number < 9; number++) {
            //注意这里没有gong++
            for (int gong = 0; gong < 9; ) {
                ArrayList<Integer> PlaceableList = getPlaceableList(number, gong);
                int length = PlaceableList.size();
                //回溯算法的重点就是这里，如果当前一步走不下去，就返回上一步，重走
                if (length <= 0) {
                    resetPlaceable(result, number, gong);
                    gong--;
                    if (gong < 0) {
                        number--;
                        gong = 8;
                    }
                    removeNum(result, number, gong);

                } else {
                    int pos = PlaceableList.get(random.nextInt(length));
                    if (isCollide(result, number, gong, pos)) {
                        placeable[number][gong][pos] = false;
                    } else {
                        addNum(result, number, gong, pos);
                        gong++;
                    }
                }
            }
        }
        return result;
    }

    private static ArrayList<Integer> getPlaceableList(int num, int gong) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        for (int pos = 0; pos < 9; pos++) {
            if (placeable[num][gong][pos]) {
                result.add(pos);
            }
        }
        return result;
    }

    private static void addNum(int[][] array, int number, int gong, int pos) {
        stepPos[number][gong] = pos;
        array[gong][pos] = number + 1;
        notifyAllNum(gong, pos, false);
    }

    private static void removeNum(int[][] array, int number, int gong) {
        int pos = stepPos[number][gong];
        array[gong][pos] = 0;
        notifyAllNum(gong, pos, true);
        placeable[number][gong][pos] = false;
        stepPos[number][gong] = -1;
    }

    private static void resetPlaceable(int[][] array, int num, int gong) {
        for (int pos = 0; pos < 9; pos++) {
            if (array[gong][pos] == 0) {
                placeable[num][gong][pos] = true;
            } else {
                placeable[num][gong][pos] = false;
            }
        }
    }

    private static boolean isCollide(int[][] array, int num, int gong, int pos) {
        // 判断列
        for (int a = gong % 3; a < 9; a = a + 3) {
            for (int b = pos % 3; b < 9; b += 3) {
                if (array[a][b] == (num + 1)) {
                    return true;
                }
            }
        }
        // 判断行
        for (int a = gong / 3 * 3; a < (gong / 3 + 1) * 3; a++) {
            for (int b = pos / 3 * 3; b < (pos / 3 + 1) * 3; b++) {
                if (array[a][b] == (num + 1)) {
                    return true;
                }
            }
        }
        return false;
    }

    private static void notifyAllNum(int gong, int pos, boolean canPlacable) {
        for (int num = 0; num < 9; num++) {
            placeable[num][gong][pos] = canPlacable;
        }
    }

    //----------------------------------生成题目------------------------------//

    private static int[][] digholes(int[][] finalAnswer) {
        int holesNum = random.nextInt(12) + 12;
        return digholes(finalAnswer, holesNum);
    }

    private static int[][] digholes(int[][] finalAnswer, int holesNum) {
        int[][] result = copyArray(finalAnswer);
        ArrayList<Integer> diggedHoles = new ArrayList<Integer>();
        for (int i = 0; i < holesNum; i++) {
            int pos = random.nextInt(80);
            if (diggedHoles.contains(pos)) {
                i--;
            } else {
                diggedHoles.add(pos);
                result[pos / 9][pos % 9] = 0;
            }
        }
        return result;
    }

    //------------------------------解数独---------------------------//
    private static void solve(int[][] data) {
        if (resultNum > 1) {
            return;
        }
        analyse(data);
        int result = check(data);
        if (result == 1) {
            int[] position = findLessCandidatesPos(data);
            int pv = data[position[0]][position[1]];
            int pvcount = Integer.bitCount(pv);
            for (int i = 0; i < pvcount; i++) {
                int testV = 1 << ((int) (Math.log(Integer.highestOneBit(pv)) / Math.log(2)));
                pv ^= testV;
                int[][] copy = copyArray(data);
                copy[position[0]][position[1]] = testV;
                //为什么要返回呢？
                if (i > 1) {
                    return;
                }
                solve(copy);
            }
        } else if (result == 0) {
            resultNum++;
            System.out.println("------------------------------------第" + (resultNum) + "个答案---------------------"
                    + (System.nanoTime() - startTime) / 1000000.0 + "ms---");
            answer = data;
            binaryToInt(answer);
            printByRow(answer);
        }
    }

    //TODO 还可以加入其它删减候选数算法，将这变成一个解题演算器
    private static void analyse(int[][] data) {
        boolean changed = false;
        changed = reduce(data);
        if (changed) {
            analyse(data);
        }
    }

    private static boolean reduce(int[][] data) {
        boolean changed = false;
        for (int m = 0; m < 9; m++) {
            for (int n = 0; n < 9; n++) {
                //应该是不管推测出来的候选值有几个，都要视图更新数独
                int Candidates = findCandidates(data, m, n);
                changed = tryReduceCandidates(data, m, n, Candidates);
            }
        }
        return changed;
    }

    private static int findCandidates(int[][] data, int m, int n) {
        //当数独中有超过两个候选值的时候，表示该值尚且不确定，才需要再根据上下文推导
        if (Integer.bitCount(data[m][n]) == 1) {
            return data[m][n];
        }
        int row = 0;// 行已确定值集合
        int col = 0;// 列已确定值集合
        int block = 0; // 宫格已确定值集合

        for (int i = 0; i < 9; i++) {
            if (Integer.bitCount(data[m][i]) == 1) {//这是计算这个二进制上有多少个1，如果只有一个1，表示只有一个候选数，则这格只能填这个数了
                row += data[m][i];//row表示一行上的值，比如110101100表示这一行上已经存在98643这几个数了，但是在哪些格子上并不在乎
            }
            if (Integer.bitCount(data[i][n]) == 1) {
                col += data[i][n];
            }
        }
        for (int i = m / 3 * 3; i < m / 3 * 3 + 3; i++) {
            for (int j = n / 3 * 3; j < n / 3 * 3 + 3; j++) {
                if (Integer.bitCount(data[i][j]) == 1) {
                    block += data[i][j];
                }
            }
        }

        int existNum = row | col | block;
        int candidates = 0x1ff ^ existNum;
        if (candidates == 511) {
            System.out.println("1");
        }
        return candidates;
    }

    //data[m][n]存储的一直是候选数组成的二进制数，当每个data[m][n]中存储的二进制数中只有一个1则表示找到了答案
    private static boolean tryReduceCandidates(int[][] data, int m, int n, int candidates) {
        int old = data[m][n];
        data[m][n] = old & candidates;
        int a = data[m][n];
        if (a == 511) {
            System.err.println();
        }
        if (candidates == 511) {
            System.err.println();
        }
        if (data[m][n] != old) {
            return true;
        } else {
            return false;
        }
    }

    public static int[] findLessCandidatesPos(int[][] data) {
        int[] result = null;
        int smallCount = 10;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                int bitcount = Integer.bitCount(data[i][j]);
                if (bitcount == 2) {
                    return new int[]{i, j};
                } else if (bitcount != 1) {
                    if (smallCount > bitcount) {
                        smallCount = bitcount;
                        result = new int[]{i, j};
                    }
                }
            }
        }
        return result;
    }

    /**
     * 检查结果
     *
     * @param data
     * @return <b>0</b>   正确<br>
     * <b>1</b>    还有位置未填<br>
     * <b>-1</b>    错误<br>
     */
    private static int check(int[][] data) {
        for (int i = 0; i < 9; i++) {
            int row = 0;
            int col = 0;
            int block = 0;
            for (int j = 0; j < 9; j++) {
                if (Integer.bitCount(data[i][j]) > 1) {
                    return 1;
                }
                row |= data[i][j];//获得i行的所有已确定的数字
                col |= data[j][i];//获得i列的所有已确定的数字,沿对角线的方式统计行列
            }

            for (int h = i / 3 * 3; h < i / 3 * 3 + 3; h++) {
                for (int l = i % 3 * 3; l < i % 3 * 3 + 3; l++) {
                    block |= data[h][l];
                }
            }
            if (row != 0x1ff || col != 0x1ff || block != 0x1ff) {
                return -1;
            }
        }
        return 0;
    }

    //-----------------------其他------------------------------//
    private static int[][] toBinary(String source) {
        source = source.replace(" ", "");
        int[][] data = new int[9][9];
        for (int i = 0; i < source.length(); i++) {
            int v = source.charAt(i) - '0';
            if (v != 0) {
                data[i / 9][i % 9] = 1 << (v - 1);//这里是向左移，将1移动v-1位，将十进制数转换成对应位置上的1
            } else {
                data[i / 9][i % 9] = 0x1ff;//0x1ff表示为二进制是九个1，也就是111111111,表示该位置的候选数为1-9
            }
        }
        return data;
    }

    private static int[][] toBinary(int[][] source) {
        int[][] data = new int[9][9];
        for (int i = 0; i < 81; i++) {
            int v = source[i / 9][i % 9];
            if (v != 0) {
                data[i / 9][i % 9] = 1 << (v - 1);
            } else {
                data[i / 9][i % 9] = 0x1ff;
            }
        }
        return data;
    }

    public static int getV9(int v) {
        // 使用switch与使用Math.log时间效率差不多
        switch (v) {
            case 1:
                return 1;
            case 2:
                return 2;
            case 4:
                return 3;
            case 8:
                return 4;
            case 16:
                return 5;
            case 32:
                return 6;
            case 64:
                return 7;
            case 128:
                return 8;
            case 256:
                return 9;
            default:
                break;
        }
        return -1;
    }

    private static int[][] gongConvertToRow(int[][] array) {
        int[][] result = new int[9][9];
        int i = 0, j = 0;
        for (int d = 0; d < 9; d += 3) {
            for (int c = 0; c < 9; c += 3) {

                for (int a = d / 3 * 3; a < (d / 3 + 1) * 3; a++) {
                    for (int b = c / 3 * 3; b < (c / 3 + 1) * 3; b++) {
                        result[i][j] = array[a][b];
                        j++;
                        if (j == 9) {
                            j = 0;
                        }
                    }
                }
                i++;
            }
        }
        return result;
    }

    private static int[][] copyArray(int[][] data) {
        int[][] result = new int[9][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                result[i][j] = data[i][j];
            }
        }
        return result;
    }

    private static void binaryToInt(int[][] binaryData) {
        for (int m = 0; m < 9; m++) {
            for (int n = 0; n < 9; n++) {
                binaryData[m][n] = getV9(binaryData[m][n]);
            }
        }
    }

    private static void printByGong(int[][] array) {
        for (int d = 0; d < 9; d += 3) {
            for (int c = 0; c < 9; c += 3) {

                for (int a = d / 3 * 3; a < (d / 3 + 1) * 3; a++) {
                    for (int b = c / 3 * 3; b < (c / 3 + 1) * 3; b++) {
                        System.out.print(array[a][b] + " ");
                    }
                    System.out.print(" | ");
                }
                System.out.println();
            }
            System.out.println("--------------------------");
        }
    }

    private static void printByRow(int[][] data) {
        for (int m = 0; m < 9; m++) {
            for (int n = 0; n < 9; n++) {
                if (data[m][n] != -1) {
                    System.out.print(data[m][n] + " ");
                } else {
                    System.out.print("_ ");
                }
            }
            System.out.println();
        }
    }
}

————————————————
版权声明：本文为CSDN博主「参宿_七」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/Michaelia_hu/article/details/103390255