将 N Queen 问题的所有解添加到数组列表中-解网

问：

n-queens 谜题是将 n 个皇后放在（n×n）棋盘上的问题，这样两个皇后就不能互相攻击。

我使用回溯来解决问题。但是我遇到了一个奇怪的问题。

下面是我写的代码：

import java.util.ArrayList;

public class NQueenProblem {

    static ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();

    static ArrayList<ArrayList<Integer>> nQueen(int n) {

        ArrayList<Integer> positions = new ArrayList<Integer>();
        //boolean[][] placed = new boolean[n][n];
        solveNQueenRec(n, 0, new boolean[n][n], positions);
        //for dubugging purpose. This prints empty arrays. not able to understand why?
        for (ArrayList<Integer> list : ans)
            System.out.println(list);
        return ans;
    }

    static void solveNQueenRec(int n, int col, boolean[][] placed, ArrayList<Integer> positions) {
        if (col == n) {
            //for debugging process
            System.out.println("Adding " + positions);
            ans.add(positions);
            System.out.println("Added " + positions);
        }
        for (int row = 0; row < n && col < n; row++) {
            if (isSafe(row, col, placed, n)) {
                placed[row][col] = true;
                positions.add(row + 1);
                solveNQueenRec(n, col + 1, placed, positions);
                placed[row][col] = false;
                positions.remove(positions.size() - 1);
            }
        }
        // return null;
    }

    private static boolean isSafe(int row, int col, boolean[][] placed, int n) {
        boolean safe = true;
        // checking if exists in same row
        for (int i = 0; i < col; i++) {
            if (placed[row][i])
                safe = false;
        }
        // checking for upper diagonal
        for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
            if (placed[i][j])
                safe = false;
        }
        // checking for lower diagonal
        for (int i = row, j = col; i < n && j >= 0; i++, j--) {
            if (placed[i][j])
                safe = false;
        }
        return safe;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        nQueen(4);

    }

}

我无法理解的是，当我在日志列表中看到被添加到我的 ans 时，为什么我的 ans 是空的。我是在犯什么愚蠢的错误。请帮我解决这个问题。如果可能的话，请帮助我提供链接以了解该问题以及我将来如何避免这些问题。

Java 算法 Pass-by-Reference 回溯传递

for (ArrayList<Integer> list : ans) {
    if (list.size() > 0)
        System.out.println(list);
}

static void solveNQueenRec(int n, int col, boolean[][] placed, ArrayList<Integer> positions) {
    if (col == n) 
        printQueens(positions);
    
    for (int row = 0; row < n && col < n; row++) {
        if (isSafe(row, col, placed, n)) {
            placed[row][col] = true;
            positions.add(row + 1);
            solveNQueenRec(n, col + 1, placed, positions);
            placed[row][col] = false;
            positions.remove(positions.size() - 1);
        }
    }
    // return null;
}


public static void printQueens(ArrayList<Integer> q) {
    int n = q.size();
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= n; j++) {
            if (q.get(i) == j) 
                System.out.print("Q ");
            else           
                System.out.print("* ");
        }
        System.out.println();
    }  
    System.out.println();
}

solution to 4-queens sample:
* Q * * 
* * * Q 
Q * * * 
* * Q * 

* * Q * 
Q * * * 
* * * Q 
* Q * *

是你的“问题”。您只是添加到对列表的引用中。因此充满了对同一列表的引用。当您在插入后多次修改时，直到清空它，最后充满了 n 个引用（n 是找到的解决方案的数量）与末尾为空的相同列表。anspositionsanspositionspositionsanspositions

您需要在找到解决方案时插入当前列表的副本：positions

ans.add(new ArrayList<Integer>(positions));

副本是通过构建具有原始列表确切内容的新列表来获得的。

上一个：Java ArrayList 独立副本

下一个：无法在 C++ [duplicate] 中获取额外函数中数组的长度

将 N Queen 问题的所有解添加到数组列表中

Adding all solutions of N Queen Problem to an arrayList

评论

评论