How come my stack is getting overwritten after a for loop execution?

Question

I am doing an algorithm for a hill climbing search, and for some reason, the stack that I'm supposed to have at the end of the loop seems to be overwritten with the last iteration of the state that the loop generated.

Basically, here is a rundown of what this algorithm is doing:

This algorithm is being used to solve the N queens problem. All of the underlying code with the state class works perfectly fine. With this algorithm, it iterates through all possible successor states of the current state. It stores the next successor state within the neighborState variable (as seen in the code below). If a state cost is less than the current cost, it will add the neighborState with that new low cost into a neighborNode and store that into a stack. Any new min values that get detected will wipe the stack and insert the new lowest minimum nodes.

I've done a few tests within the loop to see what the outputs look like from what is being inserted into the stack. All of them seem to be correctly outputting. However, when I am outside the loop and check the stack, all the nodes in the stack have their states replaced to the last generated successor state from the loop. It seems that in every node that has the neighborState stored, each time the neighborState updates, it changes all the node neighborState values as well. I just can't seem to find a way to fix this though.

Some advice as to how I can fix this would be greatly appreciated!

*Note: Disregard the code after the for loop starting at the if statement, as it is still incomplete.

Here is the code:

import java.util.Random;
import java.util.Stack;

public class HillClimber {

private LocalSearchNode _current;
private int _shoulderSearchStepsAllowed;

// may need more instance variables

public HillClimber(LocalSearchNode initial, int searchShoulder) {
    _current = initial;
    _shoulderSearchStepsAllowed = searchShoulder;
}

public LocalSearchNode findSolution() {
    LocalSearchNode neighborNode = null;
    //Stack <LocalSearchNode> nodeStack;
    State currentState = null;
    //State neighborState = null;
    Double val = 0.0;
    boolean start = true;

    while (true) {

        currentState = _current.getState();
        Stack<LocalSearchNode> nodeStack = new Stack<LocalSearchNode>();

        // finds the highest valued successor of current
        for (String s : currentState.actions()) {
            State neighborState = currentState.successor(s);
            Double cost = neighborState.estimatedDistance(neighborState);

            // execute this for the first successor found
            if (start) {
                val = cost;
                System.out.println("Started with " + val);
                neighborNode = new LocalSearchNode(neighborState,
                        s, val, 0);
                nodeStack.push(neighborNode);
                start = false;
                ((QState) nodeStack.peek().getState()).test();
                System.out.println(nodeStack.size());
            }
            // resets node array if new min found and adds it to the array
            else if (cost < val) {
                System.out.println("Reset " + val + " with " + cost);
                val = cost;
                nodeStack = new Stack<LocalSearchNode>();
                neighborNode= new LocalSearchNode(neighborState,
                        s, val, 0);
                nodeStack.push(neighborNode);
                ((QState) nodeStack.peek().getState()).test();
                System.out.println(nodeStack.size());
            }
            // if cost is the same as current min val, add it to the array
            else if (cost.equals(val)) {
                val = cost;
                System.out.println("Added " + val);
                neighborNode = new LocalSearchNode(neighborState,
                        s, val, 0);
                nodeStack.push(neighborNode);
                ((QState) nodeStack.peek().getState()).test();
                System.out.println(nodeStack.size());
            }
        }

        System.out.println("Final min " + val);
        System.out.println(nodeStack.size());
        ((QState) nodeStack.elementAt(0).getState()).test();
        ((QState) nodeStack.elementAt(1).getState()).test();

        // returns current state if no better state found
        if (_current.getValue() < val) {
            // System.out.println(val);
            // ((QState) _current.getState()).test();
            return _current;
        } else {
            if (nodeStack.size() > 1) {
                Random generator = new Random();
                int i = generator.nextInt(nodeStack.size());
                _current = nodeStack.elementAt(i);
            } else {
                _current = nodeStack.firstElement();
            }
            start = true;
        }
    }
}

}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class QState implements State {
private List<String> _list;
private int[][] _state;
private int[] _qlist;

/**
 * Constructor takes in the board and row index value corresponding to the
 * queens at their respective column index
 * 
 * @param state
 * @param queens
 */
public QState(int[][] state, int[] queens) {
    _state = state;
    _qlist = queens;

    _list = new ArrayList<String>();

    // generates a list of all possible actions for this state
    for (int i = 0; i < _qlist.length; i++) {
        for (int j = 0; j < _qlist.length; j++) {
            if (_state[i][j] != -1) {
                _list.add("Move queen " + j + " to row " + i);
            }
        }
    }
}

/**
 * Returns a list of N * (N - 1) actions
 */
public List<String> actions() {
    return _list;
}

/**
 * Returns the matrix board configuration of this state
 * 
 * @return
 */
public int[][] getMatrix() {
    return _state;
}

/**
 * Returns the array of queens row index for the board configuration
 * 
 * @return
 */
public int[] getQList() {
    return _qlist;
}

/**
 * Parses the action and moves the queen to the new board location
 */
public State successor(String action) {
    State temp = null;
    int[][] newState = _state;
    int[] newQList = _qlist;

    String[] vals = action.split("\\s");
    int i = Integer.parseInt(vals[5]); // parses the row index
    int j = Integer.parseInt(vals[2]); // parses the column index

    newState[_qlist[j]][j] = 0; // clears the old queen
    newState[i][j] = -1; // sets the new queen
    newQList[j] = i; // adds the new queen to the list

    temp = new QState(newState, newQList);
    return temp;
};

/**
 * Returns the default step cost of 1.0
 */
public Double stepCost(String action) {
    return 1.0;
}

// overrides the built-in Java equals method
@Override
public boolean equals(Object s) {
    if (s == null) {
        return false;
    }

    if (this.getClass() != s.getClass()) {
        return false;
    }

    if (!Arrays.equals(this.getMatrix(), ((QState) s).getMatrix())) {
        return false;
    }
    return true;
}

/**
 * Returns the queen conflicts for the particular board
 */
public Double estimatedDistance(State s) {
    double conflicts = 0.0;
    int col = 0;
    int row = 0;

    for (int j = 0; j < _qlist.length; j++) {
        row = _qlist[j] - 1;
        col = j + 1;

        // checks the upper right diagonal for queen conflicts
        while (row >= 0 && col < _qlist.length) {
            if (_state[row][col] == -1) {
                conflicts++;
            }
            row--;
            col++;
        }

        row = _qlist[j] + 1;
        col = j + 1;

        // checks the lower right diagonal for queen conflicts
        while (row < _qlist.length && col < _qlist.length) {
            if (_state[row][col] == -1) {
                conflicts++;
            }
            row++;
            col++;
        }

        row = _qlist[j];
        col = j + 1;

        // checks the sideways right for queen conflicts
        while (col < _qlist.length) {
            if (_state[row][col] == -1) {
                conflicts++;
            }
            col++;
        }
    }
    // test();
    return conflicts;
}

public void test() {
    for (int i = 0; i < _qlist.length; i++) {
        for (int j = 0; j < _qlist.length; j++) {
            if (_state[i][j] == -1) {
                System.out.print("Q");
            } else {
                System.out.print("-");
            }
        }
        System.out.println("");
    }
    System.out.println("\n");
}

}

Answer 1

If you look at successor, this looks suspicious to me:

int[][] newState = _state;
int[] newQList = _qlist;

Here, it looks like you're sharing these arrays between objects. Without knowing much about what the program is doing, this kind of thing is typically the cause of the "shared update" behavior you've observed.

So updating the array from the returned successor will also change the state of the object that returned it (and so on).

There are a couple of easy ways to copy an array, namely System#arraycopy, Arrays#copyOf and clone. (All arrays are cloneable.) For the 2D array you might want to make a helper method since you'd probably need to make a deep copy. Something like:

static int[][] copyState(int[][] toCopy) {
    int[][] copy = new int[toCopy.length][];
    for(int i = 0; i < copy.length; i++) {

        // or   = Arrays.copyOf(toCopy[i], toCopy[i].length);
        copy[i] = toCopy[i].clone();
    }

    return copy;
}

I didn't spend a whole lot of time really parsing the code--there's a lot to go through, sorry--but I don't see you making a copies anywhere, just mutating them, so I'd put my bet on this.