How to generate neighbors for N-Queen Hill Climbing

Question

I'm having trouble generating neighbors for implementing hill climbing algorithms.

Here's the code I'm currently working with.

public ArrayList<Board> generateNeighbors(){
    ArrayList<Board> neighborBoards = new ArrayList<Board>();

    HashMap<Integer, Integer> initialQueenLocations = this.queenLocations;


    for(int i = 0; i < queen; i++){

        int[][] neighborBoard = new int[queen][queen];
        HashMap<Integer, Integer> neighborQueenLocations = initialQueenLocations;

        for(int k = i; k < queen; k++){

            for(int j = 0; j < queen; j++){
                neighborBoard[j][initialQueenLocations.get(j)] = 1;
            }

            int initialLocation = initialQueenLocations.get(k);

            if(initialLocation > 0){

                neighborBoard[k][initialLocation] = 0;
                neighborBoard[k][initialLocation - 1] = 1;

                neighborQueenLocations.put(k, initialLocation - 1);

                neighborBoards.add(new Board(neighborBoard, neighborQueenLocations));
                break; 
            }

        }
    }
}

The problem I'm having is that each new board I generate saves the last move, I'd like each neighbor board to have a step size of one. Here is the (wrong) output:

//initial
0|0|1|
0|1|0|
0|1|0|
//step 1
0|1|0|
0|1|0|
0|1|0|
//step 2
0|1|0|
1|0|0|
0|1|0|
//step 3
0|1|0|
1|0|0|
1|0|0|

Here is the output I'd like.

//initial
0|0|1|
0|1|0|
0|1|0|
//step 1
0|1|0|
0|1|0|
0|1|0|
//step 2
0|0|1|
1|0|0|
0|1|0|
//step 3
0|0|1|
0|1|0|
1|0|0|

As you can see, it is saving the move from the previous step. Can anybody help?

I can't understand the problem and your question, but at least unconditional break from the loop by `k` variable after the first iteration looks very suspicious. — leventov, Oct 09 '13 at 19:17
I'm attempting to generate possible neighbors with a step size of one. I'd like all the boards to only have a step size of one from the initial board. But the step 3 has 3 steps. Basically, each step is being saved and then manifesting itself in the next step. — aspalding, Oct 09 '13 at 19:23
Somehow it makes no sense to me: For the problem a one-dimensional `int[]` suffices. The neighbors get created by some *to be defined* set of operations, e.g. moving a single queen. This should be done in the Board constructor, then it gets clearer. — maaartinus, Oct 09 '13 at 21:50

Bjørn Bråthen · Accepted Answer · 2013-12-05T19:26:41.543

Your problem is that you overwrite your values in your initial HashMap. Where you set neighborQueenLocations to be initialQueenLocations, you basically just set a reference to your initialQueenLocations HashMap. So When you do neighborQueenLocations.put(k, initialLocation - 1);, you write to the memory which is reserved by the initialQueenLocations, but "accessing" it through your neighborQueenLocations variable.

    ...

    for(int i = 0; i < queen; i++){

        int[][] neighborBoard = new int[queen][queen];

        // Here you are setting a reference, not copying the values
        HashMap<Integer, Integer> neighborQueenLocations = initialQueenLocations;

    ...

And later in your code, you are overwriting the value in your initialQueenLocations HashMap, since neighborQueenLocations is just reference to your initialQueenLocations.

    ...
    neighborBoard[k][initialLocation] = 0;
    neighborBoard[k][initialLocation - 1] = 1;

    neighborQueenLocations.put(k, initialLocation - 1);
    ...

That's why it "remembers" the last step taken.

How to generate neighbors for N-Queen Hill Climbing

1 Answers1