java - How to add multiple solution with bactraking method

Question

I'm trying to learn bactracking however, while I would like to add all solution to my arraylist, it only contains the first solution that my method found. I checked isSafe method, it is correct. the only problem is my queensList method. could you please explain how can I add all solution to my arraylist. For instance, for the 4x4 table, my ArrayList's element is that

[0, 1, 0, 0]

[0, 0, 0, 1]

[1, 0, 0, 0]

[0, 0, 1, 0]

public static boolean queensList(int[][] aList, int r, int k, ArrayList<int[][]> qL) {
        if (r >= k) {
            qL.add(aList);
            return true;
        }
        for (int i = 0; i < k; i++) {

            if (isSafe(aList, r, i)) {
                aList[r][i] = 1;
                if (queensList(aList, r + 1, k, qL)) 
                    return true;
                aList[r][i] = 0;
            }
        }
        return false;
    }

    public static boolean isSafe(int[][] trying, int r, int c) {
        for (int i = 0; i < trying.length; i++) {
            if (trying[r][i] == 1 || trying[i][c] == 1)
                return false;
        }
        int i = 0;
        while (r - i < trying.length && 0 <= r - i && c - i < trying.length && 0 <= c - i || r - i < trying.length && 0 <= r - i && c + i < trying.length && 0 <= c + i
                || r + i < trying.length && 0 <= r + i && c - i < trying.length && 0 <= c - i || r + i < trying.length && 0 <= r + i && c + i < trying.length && 0 <= c + i) {
            if (r - i < trying.length && 0 <= r - i && c - i < trying.length && 0 <= c - i && trying[r - i][c - i] == 1)
                return false;
            if (r - i < trying.length && 0 <= r - i && c + i < trying.length && 0 <= c + i && trying[r - i][c + i] == 1)
                return false;
            if (r + i < trying.length && 0 <= r + i && c - i < trying.length && 0 <= c - i && trying[r + i][c - i] == 1)
                return false;
            if (r + i < trying.length && 0 <= r + i && c + i < trying.length && 0 <= c + i && trying[r + i][c + i] == 1)
                return false;
            i++;
        }
        return true;
    }

Answer 1

your exit condition of your function queensList should be only when (r >= k) , which means when the row r comes to the end k, and the queen is still safe, that's a valid solution.

However in your implementation, you also returned when you find a solution in the for loop, which means it did not finish the whole for loop to find all the possible solutions.

so make a small change to your backtracking function like this:

public static void queensList(int[][] aList, int r, int k, ArrayList<int[][]> qL) {
    //exit condition
    if (r >= k) {
        qL.add(aList);
        return;
    }
    for (int i = 0; i < k; i++) {
        if (isSafe(aList, r, i)) {
            aList[r][i] = 1;
            queensList(aList, r + 1, k, qL);
            aList[r][i] = 0;
        }
    }
}