Java 数独暴力解算器，它是如何工作的？

Question

因此，您可以在此处找到下面的代码。我理解大部分代码，但有一点我不理解。我们创建名为 digits 的布尔数组的位置以及之后的位 3 * (x / 3)。

我认为它用于检查数独中的每个方块是否也有 9 个唯一数字，但我不确定如何向我旁边的人解释这一点。

为什么这里需要布尔数组？有人可以向我解释一下它在做什么以及为什么吗？

亲切的问候！

public int[][] solvePuzzle(int[][] matrix) {
    int x, y = 0;

    boolean found = false;

    // First we check if the matrix contains any zeros.
    // If it does we break out of the for loop and continue to solving the puzzle.
    for (x = 0; x < 9; x++) {
        for (y = 0; y < 9; y++) {
            if (matrix[x][y] == 0) {
                found = true;
                break;
            }
        }

        if (found) {
            break;
        }
    }

    // If the puzzle doesn't contain any zeros we return the matrix
    // We now know that this is the solved version of the puzzle
    if (!found) {
        return matrix;
    }

    boolean digits[] = new boolean[11];

    for (int i = 0; i < 9; i++) {
        digits[matrix[x][i]] = true;
        digits[matrix[i][y]] = true;
    }

    int boxX = 3 * (x / 3), boxY = 3 * (y / 3);
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            digits[matrix[boxX + i][boxY + j]] = true;
        }
    }

    // We loop over all the numbers we have to check if the next number fits in the puzzle
    // We update the matrix and check recursively by calling the same function again to check if the puzzle is correct
    // If it's not correct we reset the matrix field to 0 and continue with the next number in the for loop
    for (int i = 1; i <= 9; i++) {
        if (!digits[i]) {
            matrix[x][y] = i;

            if (solvePuzzle(matrix) != null) {
                return matrix;
            }

            matrix[x][y] = 0;
        }
    }

    // The puzzle can't be solved so we return null
    return null;
}

Answer 1

我在评论中添加了一些解释：

//we need to know what digits are we still allowed to use
//(not used in this row, not used in this column, not used in
//the same 3x3 "sub-box")
boolean digits[] = new boolean[11];

//so we run through the rows/coumns around the place (x,y)
//we want to fill in this iteration
for (int i = 0; i < 9; i++) {
    //take a used number from the row of x (matrix[x][i]) and mark it
    // as used
    digits[matrix[x][i]] = true;
    //take a used number from the column of y (matrix[i][y]) and mark it
    // as used
    digits[matrix[i][y]] = true;
}

//find the top-left corner of the sub-box for the position (x,y) we
//want to fill in
//example: x is 8 -> 3 * 8/3 -> 6, so we start from 6
int boxX = 3 * (x / 3), boxY = 3 * (y / 3);

//iterate through the sub-box horizontally and vertically
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
    //take a used number from the sub-box and mark it
    // as used
        digits[matrix[boxX + i][boxY + j]] = true;
    }
}

Answer 2

您似乎有两个问题不清楚：

布尔数组 - 该数组用于跟踪特定行或列上已经使用了哪些数字。因此，想象一下一行勾选框，每个勾选框旁边都有一个数字（数组索引）——这些框被选中或未选中以显示是否使用了一个数字。
表达式 3* (x/3) 和 3 * (y/3) - 你需要记住的是这是整数除法（这意味着结果除法总是向下舍入为整数。例如，如果 x=1，则 3 (x/3) 是 3 (1/3) 是 3 * (0) =0 （而如果这是浮点除法，则结果将是 3*(0.3333)=1。因此，这些数学表达式实质上会将您的数字更改为下一个最小的三倍数 - 即 1 -> 0, 2 -> 0, 3 -> 3、4 -> 3 等等

Java 数独暴力解算器，它是如何工作的？

Java Sudoku brute force solver, how does it work?

java

brute-force