The n-queens puzzle is the problem of placing n queens on a (n×n) chessboard such that no two queens can attack each other.

I used backtracking to solve the problem. But I ran in a strange issue.

Below is the code I wrote:

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);

    }

}

What I am not able to understand is why my ans is empty when I could see in logs list being added to my ans. Am I doing some silly mistake. Please help me with the issue. If possible please help me with links to understand the issue and how could I avoid these issues in future.

CodePudding user response：

I think you believe that when the JVM executes

   ans.add(positions);

that it is taking a copy of the current state of positions and adding it to the list. It isn't, it is doing exactly what the code says: adding a reference to an ArrayList to ans.

All the items in ans are references to the same ArrayList, and that array list is empty when you print out ans.

CodePudding user response：

ans.add(positions);

is your "problem". You are just adding to ans a reference to the list positions. Thus ans is full of references to the same positions list. As you modify positions several time after insertion, until emptied it, at the end ans is full of n references (n being the number of solutions found) the same positions list that is empty at the end.

What you need is to insert a copy of the current positions list at the time a solution is found:

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

copy is obtained by constructing a new list with the exact content of the original one.

CodePudding user response：

Add this checking make sure it is greater than zero, then print out the answer. Moreover, add the print queen function, your will see the answer clearly. If this solve your problem, please make as answer.

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