来自递归调用的数组被覆盖

Question

我们正在编写一个程序，通过带回溯的递归方法解决星号数独问题。

solveIt方法调用的是solve方法，是递归方法。 grid 之前被声明为一个 9x9 二维数组，其中包含要填写的拼图。如果只有一个解，程序必须打印出完整的拼图，但是如果有更多解，它必须只打印出数字可能的解决方案。

问题是：在solve的内部，print();工作正常并打印出完整的拼图。然而，在该方法之外，它会打印出空的初始拼图。为什么是这样？我们无法弄清楚为什么当 solve 完成时，一个单独的变量（在本例中为 h）也会被随机覆盖。

int[][] h;
int solutionCounter = 0;

void solve() {
    int[] next = findEmptySquare();
    if (!(next[0] == -1 && next[1] == -1)) {
        if (grid[next[0]][next[1]] == 0) {
            for (int i = SUDOKU_MIN_NUMBER; i <= SUDOKU_MAX_NUMBER; i++) {
                if (!(givesConflict(next[0], next[1], i))) {
                    //fills in the puzzle
                    grid[next[0]][next[1]] = i;
                    //go to next number
                    solve();
                }
            }
            grid[next[0]][next[1]] = 0;
        }
    } else {
        //print(); here it works just fine
        solutionCounter++;
        h = grid.clone();
    }
}

void solveIt() {
    solve();
    if (solutionCounter > 1) {
        System.out.println(solutionCounter);
    } else {
        grid = h.clone();
        print(); //here it prints the empty puzzle
    }
}

Answer 1

解决方案

.clone() 方法似乎只是将 h 引用到 grid。因此 h 指向 grid 并采用其值导致我们遇到上述问题。

因此实施了以下解决方案：

//copy the grid into h.
for (int x = 0; x < 9; x++) {
    for (int y = 0; y < 9; y++) {
        h[x][y] = grid[x][y];
    }
}

有关 clone() 的更多信息：

https://www.geeksforgeeks.org/clone-method-in-java-2/

来自递归调用的数组被覆盖

Array from recursive call being overwritten

java

recursion

sudoku

multidimensional-array

recursive-backtracking