java - ArrayList 无法正确保存对象(N Queens 示例)

Question

我已经解决了 N Queens 问题，返回一个包含所有可能解决方案的 ArrayList。

我知道算法本身是正确的，因为它打印出了正确的解决方案。但是，当我迭代返回的 ArrayList 时，我没有看到正确的解决方案。我只看到空网格(即 4 行 0)。

谁能告诉我为什么我在程序中打印了正确的答案，但它们没有正确地添加到 ArrayList 中？

这是我提供上下文的代码，但您应该真正注意 queens() 中的第一个 if 语句，其中 printGrid() 打印我(假设)添加到列表中的正确解决方案。但是，当我在 main 方法中迭代列表时，我得到 0。

public class Question {

    static int GRID_SIZE = 4;

    public static ArrayList<int[][]> queens(int[][] grid) {
        ArrayList<int[][]> list = new ArrayList<int[][]>();

        queens(grid, 0, list);

        return list;
    }

    public static void queens(int[][] grid, int row, ArrayList<int[][]> list) {

        // if you reached the end of the grid successfully
        if (row == GRID_SIZE) {

            //print grid - shows correct solution
            printGrid(grid);

            //adding correct solution to list?
            list.add(grid);

        }

        else {
            //iterate through columns
            for (int i = 0; i < GRID_SIZE; i++) {

                // check if the spot is free
                if (valid(grid, row, i)) {
                    // place queen
                    grid[row][i] = 1;

                    // move onto next row
                    queens(grid, row + 1, list);

                    //backtrack if placement of queen does not allow successful solution
                    grid[row][i] = 0;
                }
            }
        }
    }

    // need to check previous rows to see if it's safe to place queen
    public static boolean valid(int[][] grid, int row, int col) {

        // check columns of each previous row
        for (int i = 0; i < row; i++) {
            if (grid[i][col] == 1) {
                return false;
            }
        }

        // check left diagonal
        int rowNum = row;
        int colNum = col;
        while (rowNum >= 0 && colNum >= 0) {
            if (grid[rowNum--][colNum--] == 1) {
                return false;
            }
        }

        // check right diagonals
        rowNum = row;
        colNum = col;
        while (rowNum >= 0 && colNum < GRID_SIZE) {
            if (grid[rowNum--][colNum++] == 1) {
                return false;
            }
        }

        return true;
    }

    public static void printGrid(int[][] grid) {
        System.out.println("---------");
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid.length; j++) {
                System.out.print(grid[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("---------");
    }

    public static void main(String[] args) {
        int[][] grid = new int[GRID_SIZE][GRID_SIZE];

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid.length; j++) {
                grid[i][j] = 0;
            }
        }

        ArrayList<int[][]> list = queens(grid);

        System.out.println(list.size());

        printGrid(list.get(0));

    }
}

这是输出:

---------
0 1 0 0 
0 0 0 1 
1 0 0 0 
0 0 1 0 
---------
---------
0 0 1 0 
1 0 0 0 
0 0 0 1 
0 1 0 0 
---------
ITERATING THROUGH ARRAYLIST:
---------
0 0 0 0 
0 0 0 0 
0 0 0 0 
0 0 0 0 
---------
---------
0 0 0 0 
0 0 0 0 
0 0 0 0 
0 0 0 0 
---------

Answer 1

你只有一个数组实例，你不断地改变它并将其多次添加到列表中。最后，列表包含对该单个数组最终状态的引用。

您应该添加 grid 的副本，而不是 list.add(grid); (请注意 Arrays.copyOf() 或System.arraycopy() 在这里还不够，因为它们执行浅复制并且您的数组是二维的。