简介

这是2018年就开发出来的代码，但由于一直无人问津，干脆将其搬到博客里来，兴许看到的人会稍微多一点。毕竟要秀一波的嘛！

一、体验数独计算器

二、Java代码

/**
 * 数独解答器。
 *
 * @author Microanswer 2018年5月3日14:39:50
 */
class SudoSolver {
    // 按顺序选取数填写
    public static final int GET_VALUE_BY_ORDER = 1;
    // 随机选取数填写
    public static final int GET_VALUE_BY_RANDOM = 2;

    // 待解答的数独
    private int[][] originSudo;
    // 解答数独过程监听器
    private SudoSolverListener sudoSolverListener;
    // 以指定的数独数组构建数独解答器
    public SudoSolver(int sudo[][]) {
        if (sudo == null) {
            this.originSudo = new int[9][9];
        } else {
            this.originSudo = copyArray(sudo);
        }
    }
    // 构造一个全是0的空数独，其解的个数量巨大。
    public SudoSolver() {
        this(null);
    }
    public void setSudoSolverListener(SudoSolverListener sudoSolverListener) {
        this.sudoSolverListener = sudoSolverListener;
    }
    public SudoSolverListener getSudoSolverListener() {
        return sudoSolverListener;
    }
    // 拷贝数组
    private int[][] copyArray(int[][] src) {
        int[][] newArray = new int[src.length][];
        for (int i = 0; i < src.length; i++) {
            int[] array = new int[src[i].length];
            for (int j = 0; j < src[i].length; j++) {
                array[j] = src[i][j];
            }
            newArray[i] = array;
        }
        return newArray;
    }
    // 将数独数组转化成String
    public static String stringSudo(int[][] sudo) {
        StringBuilder sbu = new StringBuilder();
        for (int i = 0; i < sudo.length; i++) {
            sbu.append("[");
            for (int j = 0; j < sudo[i].length; j++) {
                sbu.append((sudo[i][j] == 0 ? "□" : sudo[i][j])
                        + (j < sudo[i].length - 1 ? (" " + (j % 3 == 2 ? " " : "")) : ""));
            }
            sbu.append("]\n");
            if (i % 3 == 2 && i < sudo.length - 1) {
                sbu.append("\n");
            }
        }
        return sbu.toString();
    }
    // 打印数独
    public static void printSudo(int[][] sudo) {
        System.out.println(stringSudo(sudo));
    }
    // 获取待解答的原数独
    public int[][] getOriginSudo() {
        return originSudo;
    }
    // 执行数独解析
    public void findAnswer(SudoSolverListener solverListener) {
        setSudoSolverListener(solverListener);
        // 如果使用递归的方式来遍历填写到数独，能够简化代码，但是，个人觉得这个东西数据量巨大
        // 所以，此处使用一个记录器来记录当前尝试填写到了哪一个坐标位置的方式来循环完成，
        // 减少资源开销
        LinkedList<IJ> tryHistory = new LinkedList<>();
        // 临时数独数组，每次填写一个值过后，这个数组都会变化
        int[][] tempSudo = copyArray(originSudo);
        // 继续向下填写状态
        final int STATUS_KEEPGOING = 1;
        // 返回上个填写位置状态
        final int STATUS_BACK = 2;
        // 默认为继续向下填写
        int status = STATUS_KEEPGOING;
        // 开始循环寻找答案
        w: while (true) {
            // 搜寻
            IJ ij = null;
            if (STATUS_KEEPGOING == status) {
                ij = getNextEmptyPosition(tempSudo);
            } else if (STATUS_BACK == status) {
                ij = tryHistory.get(tryHistory.size() - 1);
            }
            if (null != ij) {
                if (status == STATUS_KEEPGOING) { // 如果状态为继续往下填写，直接使用可用值填写到数独
                    Integer nextNumber = ij.nextNumber(); // 获取一个用于填写的数字
                    if (null == nextNumber) {
                        // 这个位置的所有数字都被试过了或则这个位置没有适合的数字
                        if (sudoIsTrue(tempSudo)) {
                        } else {
                            // 数独还未完成，返回上一级处理
                            status = STATUS_BACK;
                        }
                    } else {
                        // 填写到数独并记录
                        tempSudo[ij.i][ij.j] = nextNumber;
                        tryHistory.add(ij);
                    }
                } else if (status == STATUS_BACK) {// 状态为返回上一级重新填写
                    Integer number = ij.nextNumber();// 获取一个可以填写的数字
                    if (null == number) {
                        // 所有数字都尝试遍了，或则这儿没有数字可以填写，继续上一步
                        tempSudo[ij.i][ij.j] = 0;
                        tryHistory.removeLast();
                        if (tryHistory.size() == 0) {
                            // 全部尝试的数字都试完了
                            onflish();
                            break;
                        }
                        status = STATUS_BACK;
                    } else {
                        // 有可以填写的数字, 那就填写吧
                        tempSudo[ij.i][ij.j] = number;
                        status = STATUS_KEEPGOING;
                    }
                }
            }
            onProgress(tempSudo);
            if (sudoIsTrue(tempSudo)) {
                boolean end = onFindAnswer(tempSudo);
                if (end) {
                    onflish();
                    break;
                }
                // 找到一个解答，开始另一波搜寻，查找其它答案
                for (int ind = tryHistory.size() - 1; ind >= 0; ind--) {
                    IJ ij2 = tryHistory.get(ind);
                    if (!ij2.hasNext()) {
                        tryHistory.remove(ind);
                        tempSudo[ij2.i][ij2.j] = 0;
                    } else {
                        // 发现一个尝试中还存在可以继续尝试使用的值，那么就从这个位置继续搜寻答案
                        status = STATUS_BACK;
                        continue w;
                    }
                }
                onflish();
                // 所有解全部找到
                break;
            } else {
                if (ij == null) {
                    // 没有可尝试方案
                    // 找不到解了
                    onflish();
                    break;
                }
            }
        }
    }
    // 数独完全解答完毕后调用
    protected void onflish() {
        if (sudoSolverListener != null) {
            sudoSolverListener.onFlish();
        }
    }
    // 数独在解答过程中回调
    protected void onProgress(int[][] sudo) {
        if (sudoSolverListener != null) {
            sudoSolverListener.onProgress(copyArray(sudo));
        }
    }
    // 数独在找到任意一个解答的时候回调
    protected boolean onFindAnswer(int[][] answer) {
        if (sudoSolverListener != null) {
            return sudoSolverListener.onAnswerFind(copyArray(answer));
        }
        return false;
    }
    // 获取下一个待填写的位置，没有待填写的位置的时候返回null
    private IJ getNextEmptyPosition(int[][] sudo) {
        // 原本是找到一个没有数字的地方就返回这个位置。
        // 后来发现，这样好像效率并不高
        //
        // for (int i = 0; i < sudo.length; i++)
        //     for (int j = 0; j < sudo[i].length; j++) {
        //         if (sudo[i][j] == 0) {
        //             return newIJ(i, j, findUseAbleNumbers(sudo, i, j));
        //         }
        //     }
        // 应该找到所有的空位置，选择能够用尝试填写的数较少的哪一个进行返回
        IJ useAbleNumbersMostLessIJ = null;
        for (int i = 0; i < sudo.length; i++)
            for (int j = 0; j < sudo[i].length; j++) {
                if (sudo[i][j] == 0) {
                    if (null == useAbleNumbersMostLessIJ) {
                        useAbleNumbersMostLessIJ = newIJ(i, j, findUseAbleNumbers(sudo, i, j));
                    } else {
                        IJ useAbleNumbersIJ = newIJ(i, j, findUseAbleNumbers(sudo, i, j));
                        if (useAbleNumbersIJ.size() < useAbleNumbersMostLessIJ.size()) {
                            useAbleNumbersMostLessIJ = useAbleNumbersIJ;
                        }
                    }
                }
            }
        return useAbleNumbersMostLessIJ;
    }
    // 寻找指定位置可以使用的数字
    private ArrayList<Integer> findUseAbleNumbers(int[][] sudo, int i, int j) {
        if (sudo[i][j] != 0) {
            throw new RuntimeException("这个位置已有数字：" + sudo[i][j]);
        }
        ArrayList<Integer> numbers = new ArrayList<>();
        for (int n = 1; n <= 9; n++)
            numbers.add(n);
        // 横排
        for (int a = 0; a < sudo[i].length; a++) {
            if (numbers.contains(sudo[i][a]))
                numbers.remove((Object) sudo[i][a]);
        }
        // 竖排
        for (int[] ints : sudo) {
            if (numbers.contains(ints[j]))
                numbers.remove((Object) ints[j]);
        }
        // 九宫格内
        // 获取到数独中该位置对应的九宫格
        int[] grid = getGridArray(sudo, i, j);
        for (int value : grid) {
            if (numbers.contains(value))
                numbers.remove(value);
        }
        return numbers;
    }
    // 校验数独是否正确
    public boolean sudoIsTrue(int[][] sudo) {
        // 先校验数独是否横9个数，竖9个数
        if (sudo == null) {
            return false;
        }
        int i = 0;
        for (; i < sudo.length; i++) {
            if (sudo[i].length != 9) {
                return false;
            }
        }
        if (i != 9) {
            return false;
        }

        boolean result = false;
        // 效验数据内容
        // 数独共有3个校验规则
        // 1、每横排数字1~9不能重复
        // 2、每竖排数字1~9不能重复
        // 3、每九宫格数组1~9不能重复
        for (i = 0; i < sudo.length; i++) {
            for (int j = 0; j < sudo[i].length; j++) {
                // 校验横排
                if (isNumberTrueInRow(sudo, i, j)) {
                    if (isNumberTrueInCol(sudo, i, j)) {
                        if (isNumberTrueInGrid(sudo, i, j)) {
                            // 三项校验都通过
                            result = true;
                        } else {
                            // 在九宫格内校验不通过
                            return false;
                        }
                    } else {
                        // 在竖排校验不通过
                        return false;
                    }
                } else {
                    // 在横排校验不通过
                    return false;
                }
            }
        }
        return result;
    }
    // 校验某个位置的数字在横排上是否满足正确
    private boolean isNumberTrueInRow(int[][] sudo, int i, int j) {
        // 获取到数独中的这一横排
        int[] row = sudo[i];
        // 获取到这个校验的数字
        int num = row[j];
        // 如果这个数是0，表示还没填写，返回false
        if (0 == num) {
            return false;
        }
        // 遍历这个横排，没有出现重复数字，视为满足
        return numInArrayOnceOrNone(num, row);
    }
    // 校验某个位置的数字在竖排上是否满足正确
    private boolean isNumberTrueInCol(int[][] sudo, int i, int j) {
        // 获取到数独中这一竖排
        int[] col = {sudo[0][j], sudo[1][j], sudo[2][j],
                sudo[3][j], sudo[4][j], sudo[5][j],
                sudo[6][j], sudo[7][j], sudo[8][j]};
        // 获取到这个校验的数字
        int num = col[i];
        // 如果这个数是0，表示还没填写，返回false
        if (0 == num) {
            return false;
        }
        // 遍历这个竖排，没有出现重复数字，视为满足
        return numInArrayOnceOrNone(num, col);
    }
    // 校验某个位置的数字在九宫格内是否满足正确
    private boolean isNumberTrueInGrid(int[][] sudo, int i, int j) {
        // 获取到数独中该位置对应的九宫格
        int[] grid = getGridArray(sudo, i, j);
        // 获取到这个校验的数字
        int num = sudo[i][j];
        // 如果这个数是0，表示还没填写，返回false
        if (0 == num) {
            return false;
        }
        // 遍历这个九宫格，没有出现重复数字，视为满足
        return numInArrayOnceOrNone(num, grid);
    }
    // 校验某个数值在数组中是否不存在或者只存在了一次
    private boolean numInArrayOnceOrNone(int num, int[] array) {
        int count = 0;
        if (num == 0) {
            return false; // 要判断的数是0的话，直接false
        }
        for (int value : array) {
            if (num == value) {
                count++;
            }
        }
        return count <= 1;
    }
    private int[] getGridArray(int[][] sudo, int i, int j) {
        // 获取到数独中该位置对应的九宫格
        int[] grid = new int[9];
        if ((0 <= i && i <= 2) && (0 <= j && j <= 2)) {        // 左上
            int index = 0;
            for (int h = 0; h <= 2; h++) {
                for (int s = 0; s <= 2; s++) {
                    grid[index] = sudo[h][s];
                    index++;
                }
            }
        } else if ((3 <= i && i <= 5) && (0 <= j && j <= 2)) { // 左中
            int index = 0;
            for (int h = 3; h <= 5; h++) {
                for (int s = 0; s <= 2; s++) {
                    grid[index] = sudo[h][s];
                    index++;
                }
            }
        } else if ((6 <= i && i <= 8) && (0 <= j && j <= 2)) { // 左下
            int index = 0;
            for (int h = 6; h <= 8; h++) {
                for (int s = 0; s <= 2; s++) {
                    grid[index] = sudo[h][s];
                    index++;
                }
            }
        } else if ((0 <= i && i <= 2) && (3 <= j && j <= 5)) {// 中上
            int index = 0;
            for (int h = 0; h <= 2; h++) {
                for (int s = 3; s <= 5; s++) {
                    grid[index] = sudo[h][s];
                    index++;
                }
            }
        } else if ((3 <= i && i <= 5) && (3 <= j && j <= 5)) {// 中中
            int index = 0;
            for (int h = 3; h <= 5; h++) {
                for (int s = 3; s <= 5; s++) {
                    grid[index] = sudo[h][s];
                    index++;
                }
            }
        } else if ((6 <= i && i <= 8) && (3 <= j && j <= 5)) {// 中下
            int index = 0;
            for (int h = 6; h <= 8; h++) {
                for (int s = 3; s <= 5; s++) {
                    grid[index] = sudo[h][s];
                    index++;
                }
            }
        } else if ((0 <= i && i <= 2) && (6 <= j && j <= 8)) {// 右上
            int index = 0;
            for (int h = 0; h <= 2; h++) {
                for (int s = 6; s <= 8; s++) {
                    grid[index] = sudo[h][s];
                    index++;
                }
            }
        } else if ((3 <= i && i <= 5) && (6 <= j && j <= 8)) {// 右中
            int index = 0;
            for (int h = 3; h <= 5; h++) {
                for (int s = 6; s <= 8; s++) {
                    grid[index] = sudo[h][s];
                    index++;
                }
            }
        } else if ((6 <= i && i <= 8) && (6 <= j && j <= 8)) {// 右下
            int index = 0;
            for (int h = 6; h <= 8; h++) {
                for (int s = 6; s <= 8; s++) {
                    grid[index] = sudo[h][s];
                    index++;
                }
            }
        } else {
            throw new RuntimeException("到达了不可能到达的位置。");
        }
        return grid;
    }
    // 坐标辅助类
    private class IJ {
        private int i, j;
        private int getValueBy = SudoSolver.GET_VALUE_BY_RANDOM;
        private ArrayList<Integer> useAbleNumbers;
        private ArrayList<Integer> tryedNumbers;
        private IJ(int i, int j) {
            this.i = i;
            this.j = j;
            tryedNumbers = new ArrayList<>();
        }
        public void setGetValueBy(int getValueBy) {
            this.getValueBy = getValueBy;
        }
        public boolean hasNext() {
            return useAbleNumbers.size() > 0;
        }
        public int size() {
            return useAbleNumbers.size();
        }
        Integer nextNumber() {
            if (useAbleNumbers.size() < 1) {
                return null;
            } else {
                Integer nu = null;
                if (this.getValueBy == SudoSolver.GET_VALUE_BY_RANDOM) {
                    int index = (int) Math.floor(Math.random() * useAbleNumbers.size());
                    nu = useAbleNumbers.remove(index);
                } else if (this.getValueBy == SudoSolver.GET_VALUE_BY_ORDER) {
                    nu = useAbleNumbers.remove(0);
                } else {
                    nu = useAbleNumbers.remove(0);
                }
                tryedNumbers.add(nu);
                return nu;
            }
        }
        IJ setUseAbleNumbers(ArrayList<Integer> useAbleNumbers) {
            this.useAbleNumbers = useAbleNumbers;
            return this;
        }
        @Override
        public boolean equals(Object obj) {
            if (obj instanceof IJ) {
                IJ ij = (IJ) obj;
                return ij.i == this.i && ij.j == this.j;
            }
            return super.equals(obj);
        }
    }
    // 创建一个新的IJ坐标对象
    private IJ newIJ(int i, int j, ArrayList<Integer>  useAbleNumbers) {
        return new IJ(i, j).setUseAbleNumbers(useAbleNumbers);
    }
    /**
     * 数独解析监听器
     *
     * @author Microanswer
     */
    public interface SudoSolverListener {
        /**
         * 当发现一个可行解的时候，该方法被调用。
         *
         * @param answer .
         * @return 返回 true 如果有多个解答将不再进行解答， 返回 false 将寻找所有答案
         */
        boolean onAnswerFind(int[][] answer);
        void onProgress(int[][] sudo);
        void onFlish();
    }
}

三、使用与测试

// Java 测试
public static void main(String[] args) {
    SudoSolver solver = new SudoSolver(new int[][]{
            {8, 5, 7, 3, 4, 9, 2, 0, 1},
            {2, 1, 0, 0, 7, 0, 0, 9, 5},
            {4, 9, 0, 2, 0, 0, 0, 0, 8},
            {1, 0, 0, 0, 0, 0, 0, 0, 9},
            {3, 4, 5, 0, 9, 0, 6, 1, 7},
            {6, 0, 0, 0, 0, 0, 0, 0, 4},
            {9, 3, 1, 4, 2, 5, 0, 7, 6},
            {5, 6, 8, 0, 1, 3, 0, 0, 2},
            {7, 2, 4, 0, 8, 6, 1, 0, 3}
    });
    solver.findAnswer(new SudoSolver.SudoSolverListener() {
        @Override
        public boolean onAnswerFind(int[][] answer) {
            SudoSolver.printSudo(answer);
            return false;
        }
        @Override
        public void onProgress(int[][] sudo) {
        }
        @Override
        public void onFlish() {
            System.out.println("解答完成");
        }
    });
}