ArrayList 不会正确保存对象（N Queens 示例）

Question

我已经将 N Queens 问题解决为 return 一个包含所有可能解决方案的 ArrayList。

我知道算法本身是正确的，因为它打印出了正确的解。但是，当我遍历 returned ArrayList 时，我没有看到正确的解决方案。我只看到空网格（即 4 行 0）。

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

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

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() 在这里是不够的，因为它们执行浅拷贝你的数组是二维的）。

Answer 2

伊兰说得对。已更新 queens()：

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

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

        //creating copy of grid
        int[][] copyGrid = new int[GRID_SIZE][GRID_SIZE];
        for (int i =0; i < GRID_SIZE; i++) {
            copyGrid[i] = grid[i].clone();
        }

        list.add(copyGrid);

    }

ArrayList 不会正确保存对象（N Queens 示例）

ArrayList won't hold objects correctly (N Queens example)

java

arraylist

n-queens