Array List referecing in recursive calls

Question

Given the code bellow, I facing the following problem: I have this ArrayList that is supposed to store my solutions in it. On the first if condition, if I print there, It prints the solutions correctly. However, outside this function, it just print a single false matrix. In that in mind I suppose I having problems with referencing the object or something like that.

The solutions ArrayList was declared as an attribute of the class, I was hoping that, when the recursive backtracking found a solution and added to the ArrayList, it would update the attribute and I would be able to use it trough the whole class.

I was reading about the .clone() method, and thinking about passing a copy of solutions on each recursive call, but I not sure exactly how it would work..

public void recursiveBacktracking (ArrayList<boolean[][]> solutions, int x, int y, boolean visited[][]) {
    
    visited[x][y] = true;

    if (x == eRow && y == eCol) {
        solutions.add(visited);
        // If I print here..

    }

    if (isValidCell(x, y)) {
        // go down (x, y)
        if (x + 1 < map.getRow() && !visited[x + 1][y]) {
            recursiveBacktracking(solutions, x + 1, y, visited);
        }

        // go up (x, y)
        if (x - 1 >= 0 && !visited[x - 1][y]) {
            recursiveBacktracking(solutions, x - 1, y, visited);
        }

        // go right (x, y)
        if (y + 1 < map.getCol() && !visited[x][y + 1]) {
            recursiveBacktracking(solutions, x, y + 1, visited);

        }

        // go left (x, y)
        if (y - 1 >= 0 && !visited[x][y - 1]) {
            recursiveBacktracking(solutions, x, y - 1, visited);
        }
    }

    // backtrack from current cell and remove it from current path
    visited[x][y] = false;

e.ad · Accepted Answer · 2021-02-04 20:05:02Z

1

does changing

solutions.add(visited);

to

solutions.add(visited.clone());

is working for you?

Note that:

As you are working with references, the last line in your function forces every cell of the solutions matrix to be false

Edit: To make the above working you should define your own 'clone' method, because default clone is 'shallow' and use references as well, hence not helping in this issue.

edited Feb 4, 2021 at 20:05

answered Feb 4, 2021 at 19:26

e.ad

3802 silver badges11 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Egydio Pacheco Over a year ago

It didn't make any change doing that. About the note, I know that, however, the matrix that goes in the first if are the correct ones that I would like to store. Also if I print the solutions in the ArrayList inside that conditional if, it prints correctly all the solutions. But when I try to use outside this function I just get a full false matrix

e.ad Over a year ago

Let's start from the reason you get a full false matrix: for each x,y, after all the recursive calls, you set visited[x][y] to be false. hence you have an invariant that the finite state of each cell is false. and thats the reason you cant use it outside the function

e.ad Over a year ago

And about fixing the issue itself, perhaps you need to make your own clone method. A clone that copies the values themselves. are you comfortable with that?

Egydio Pacheco Over a year ago

I agree with you, however I just add a matrix to the solution ArrayList if it reach a specific point (x,y), so it's not adding a false matrix to the solution ArrayList. What I believe is happening, is that the changes I do inside that function does not have any effect on the solution attribute itself. And when the recursive calls ends, I end up losing the solution ArrayList

e.ad Over a year ago

The point is that you always add the 'same' matrix to the list. 'same': because the values are different each call, but the identity of the matrix is same. just for interest, if you print in the condition (where you get successful prints) the whole arraylist, do you get what you would expect?

|

Collectives™ on Stack Overflow

Array List referecing in recursive calls

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related