Java回溯法求解N皇后问题时结果ArrayList为空的问题排查

你犯的是回溯算法中非常典型的可变对象引用传递错误：
Java中ArrayList属于可变对象，你在递归终止条件col == n中直接把positions对象的引用添加到结果集ans中，后续回溯过程中执行positions.remove(positions.size() - 1)会不断修改这个对象的内容，直到递归完全结束后positions会被清空。而ans中存储的所有元素都是指向同一个positions对象的引用，最终遍历的时候自然全是空数组。

只需要修改递归终止时添加结果的逻辑，存储当前positions的拷贝即可：

if (col == n) {
    //for debugging process
    System.out.println("Adding " + positions);
    ans.add(new ArrayList<>(positions)); // 新建列表存储当前状态的拷贝
    System.out.println("Added " + positions);
}

• 所有回溯类算法中，存储临时路径的最终结果时，必须创建可变对象的副本存储，不要直接添加原对象的引用
• 排查此类问题时可以打印对象的哈希码确认是否多次引用了同一个对象：System.out.println(positions.hashCode())，如果多次添加的对象哈希码完全一致，就说明是引用重复的问题

内容的提问来源于stack exchange，提问作者Vivek Kumar