java - 回溯：在 java 中创建数独求解器

Question

我的代码的目的，类似于迷宫的回溯算法，是计算 9 × 9 数独的解。数独及其解决方案像迷宫一样存储在二维 int 数组中。我知道：回溯算法尝试从单元格 [0.0] 中输入 1 ... 9 的值，该值从第 1 段开始的自由字段开始（值为 0）。测试这是否是一个有效值有点比迷宫更复杂，只需要检查单元格是否空闲。我认为使用方法 isRowOk 、 isColOk 、 isBlockOk 是一个好主意，以利用检查值是否完全允许，即尚未包含在块中。然后在回溯算法尝试递归地在下一个空闲单元格中输入值 1 ... 9 之前，这三个函数必须全部返回 OK。否则，如果 1 ... 9 的所有数字都已尝试过，则将取消搜索（回溯）并在呼叫搜索中尝试下一个可能的号码。有没有人有更好的主意，因为我的代码不能正常工作？

包装测试；

公共类数独{

private final int BLOCK_SIZE = 3;

private final int ROW_SIZE = BLOCK_SIZE * BLOCK_SIZE;

private int nrOfSolutions, nrOfTests;

private int[][] board;

private int[][][] testBoard = {
        /* |---------|---------|---------| */
        { { 5, 3, 0, 0, 7, 0, 0, 0, 0 }, { 6, 0, 0, 1, 9, 5, 0, 0, 0 }, { 0, 9, 8, 0, 0, 0, 0, 6, 0 },
                /* |---------|---------|---------| */
                { 8, 0, 0, 0, 6, 0, 0, 0, 3 }, { 4, 0, 0, 8, 0, 3, 0, 0, 1 }, { 7, 0, 0, 0, 2, 0, 0, 0, 6 },
                /* |---------|---------|---------| */
                { 0, 6, 0, 0, 0, 0, 2, 8, 0 }, { 0, 0, 0, 4, 1, 9, 0, 0, 5 }, { 0, 0, 0, 0, 8, 0, 0, 7, 9 } },
        /* |---------|---------|---------| */

        /* |---------|---------|---------| */
        { { 5, 3, 4, 6, 7, 8, 9, 1, 2 }, { 6, 7, 2, 1, 9, 5, 3, 4, 8 }, { 1, 9, 8, 3, 4, 2, 5, 6, 7 },
                /* |---------|---------|---------| */
                { 8, 5, 9, 7, 6, 1, 4, 2, 3 }, { 4, 2, 6, 8, 5, 3, 7, 9, 1 }, { 7, 1, 3, 9, 2, 4, 8, 5, 6 },
                /* |---------|---------|---------| */
                { 9, 6, 1, 5, 3, 7, 2, 8, 4 }, { 2, 8, 7, 4, 1, 9, 6, 3, 5 }, { 3, 4, 5, 2, 8, 6, 1, 7, 0 } },
        /* |---------|---------|---------| */

        /* |---------|---------|---------| */
        { { 0, 0, 0, 5, 4, 2, 0, 0, 0 }, { 9, 6, 7, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 3, 1, 8 },
                /* |---------|---------|---------| */
                { 0, 0, 0, 0, 7, 0, 8, 6, 4 }, { 0, 2, 0, 6, 0, 4, 0, 9, 0 }, { 6, 4, 5, 0, 1, 0, 0, 0, 0 },
                /* |---------|---------|---------| */
                { 8, 9, 1, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 5, 4, 7 }, { 0, 0, 0, 3, 2, 6, 0, 0, 0 } },
        /* |---------|---------|---------| */

};

public void testSudokuSolver() {
    for (int[][] s : this.testBoard) {
        this.board = s;
        this.print();

        nrOfSolutions = 0;
        nrOfTests = 0;
        this.solve(0, 0);
    }
}

private boolean isBlockOk(int row, int col, int num) {

    int iRowStart = (row / BLOCK_SIZE) * BLOCK_SIZE;
    int iColStart = (col / BLOCK_SIZE) * BLOCK_SIZE;

    for ( int irow = iRowStart; irow < iRowStart + BLOCK_SIZE; irow++) {
        for ( int icol = iColStart; icol < iColStart + BLOCK_SIZE; icol++) {

            if (num == board[irow][icol]) {
                return false;
            }
        }
    }
    return true;
}

private boolean isRowOk(int row, int num) {
    for (int i = 0; i < ROW_SIZE; i++) {
        if (num == board[row][i]) {
            return false;
        }
    }
    return true;
}

private boolean isColOK(int col, int num) {
    for (int i = 0; i < ROW_SIZE; i++) {
        if (num == board[i][col]) {
            return false;
        }
    }
    return true;
}

public void print() {
    final String horizBorder = " ┼────────┼────────┼────────┼";

    System.out.println();

    for (int i = 0; i < ROW_SIZE; i++) {
        if (0 == i % 3) {
            System.out.println(horizBorder);
        }

        for (int j = 0; j < ROW_SIZE; j++) {
            if (0 == j % 3) {
                System.out.print(" │ ");
            }

            int num = board[i][j];
            if (num == 0) {
                System.out.print("_ ");
            } else {
                System.out.print(num + " ");
            }

        }
        System.out.println(" │");
    }
    System.out.println(horizBorder);
}

private boolean isValid(int num, int row, int col) {
    return (isBlockOk(row, col, num) && isColOK(col, num) && isRowOk(row, num));
}

public boolean solve(int row, int col) {

    for (int i = 1; i < BLOCK_SIZE; i++) {
        for (int j = 1; j < BLOCK_SIZE; j++) {
            if (board[i][j] == 0) {
                for (int k = 1; k <= 9; k++) {
                    board[i][j] = k;
                    if (isValid(i, j, k) && solve(i, col)) {
                        return true;
                    }
                    board[i][j] = 0;
                }
                return false;
            }
        }
    }
    return true;
}

public static void main(String[] args) {
    new Sudoku().testSudokuSolver();
}

}

标签： java