java - 递归调用的数组被覆盖

Question

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

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

问题是：在里面solve，print();工作得很好并打印出完整的拼图。然而，在该方法之外，它会打印出空的初始拼图。为什么是这样？我们无法弄清楚为什么一个单独的变量（h在这种情况下）在完成时也会被随机覆盖solve。

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
    }
}

标签： javarecursionmultidimensional-arraysudokurecursive-backtracking

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/