如何为N皇后爬山算法生成邻居

Question

我在实现爬山算法时遇到了生成邻居的问题。

以下是我目前正在使用的代码。

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

        }
    }
}

我遇到的问题是每次生成新棋盘时都会保存上一步的移动记录，我希望每个相邻棋盘的步长为1。以下是（错误的）输出：

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

这是我想要的输出。

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

你可以看到，它正在保存上一步的移动。有人能帮忙吗？

- aspalding

---

我无法理解问题和你的问题，但是在第一次迭代后通过 k 变量无条件中断循环至少看起来非常可疑。 - leventov

我正在尝试使用步长为1生成可能的邻居。我希望所有的棋盘都只与初始棋盘相差一个步长。但是第三步有3个步长。基本上，每一步都被保存下来，然后在下一步中显现出来。 - aspalding

抱歉，我不理解。步骤、步长... - leventov

编辑了帖子以反映我要寻找的输出。 - aspalding

对我来说有点不太理解：对于这个问题，一个一维的 int[] 就足够了。邻居是通过一些待定义的操作创建的，例如移动单个皇后。这应该在 Board 构造函数中完成，然后就会更清晰明了。 - maaartinus

Answer 1

你的问题在于你覆盖了初始HashMap中的值。当你将neighborQueenLocations设置为initialQueenLocations时，实际上只是设置了对initialQueenLocations HashMap的引用。所以当你执行neighborQueenLocations.put(k, initialLocation - 1);时，你写入的是由initialQueenLocations保留的内存，但是通过你的neighborQueenLocations变量“访问”它。

    ...

    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;

    ...

而后在你的代码中，你正在覆盖你的initialQueenLocations HashMap中的值，因为neighborQueenLocations只是对你的initialQueenLocations的引用。

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

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

这就是为什么它“记住”了上一步所采取的原因。

- Bjørn Bråthen