N皇后问题

时间：2024-03-08 11:07:09

N皇后问题是比较典型的回溯法问题，不过在回溯法中，解决N皇后问题算是有一些难度的了。

网上有很多该问题的解法，我这个虽然不是抄来的，性能也不算彪悍，但相比之下，我对“机长出品”的可读性还是很有信心的。所以捞点儿干货贴在这里，以备将来查阅之需。

回溯法的本质是对树形结构的遍历，一层一层递进，保留符合条件的节点。到达终点后，随着递归的一层层退出，抹掉上一次遍历时留下的痕迹，从而开始下一轮遍历。

回溯法一般都会结合递归来实现，递归可以简化多层嵌套for循环的场景。但写递归函数时一定要把子问题逻辑捋清楚，并确保退出条件生效。也就是说，每经过一次递归操作，退出条件中的变量一定要有所变化，否则就是递得进去，归不出来了。递归虽然能够简化多层嵌套循环，但并没有改变其本质，因此并不是说递归一定比for循环效率高，避免无效遍历是提升循环效率的一个主要套路。

在N皇后问题中，树的每个节点都代表一个N×N大小的棋盘，棋盘上记录了该节点所有直系父级节点里皇后所在的位置，而每个皇后所在的位置必须保证以该位置为中心点画出的“米”字每一笔延伸到棋盘边缘都不会经过另一个皇后。其实，琢磨透了这点儿区别，N皇后问题和一般的用回溯法在一维数组里找组合的问题也就没多大差别了。

除了保证逻辑上正确，剩下主要就是优化。比如：皇后的位置是从上到下一行一行确定的，所以在判断对角线上是否存在其他皇后时，不需要检查“米”字下面那一撇一捺，因为此时下面的数据还没有生成，不会有皇后。

另外，别忘了每层递归完成时移除上次记录的数据。在这个问题中，还要记着抹掉上一行皇后占位的状态，否则下一轮递归到这一层时，残留的状态会让代码输出的结果“莫名其妙”。

class NQueensProlbem {
    private boolean[][] squareStates;

    public List<List<String>> solve(int sideLength) {
        List<List<String>> resultList = new ArrayList<>();

        squareStates = new boolean[sideLength][sideLength];
        backtrack(resultList, sideLength, new ArrayList<>(), 0, 0);

        return resultList;
    }

    private void backtrack(List<List<String>> resultList, int sideLength, List<String> rowList, int rowIndex,
            int columnIndex) {
        if (rowIndex == sideLength) {
            if (rowList.size() == sideLength) {
                resultList.add(new ArrayList<>(rowList));
            }

            return;
        }

        for (int index = columnIndex; index < sideLength + columnIndex; index++) {
            int offset = (index + 1) % sideLength;

            if (!isSquareAvailable(rowIndex, offset)) {
                continue;
            }

            StringBuilder rowBuilder = newRow(sideLength);

            rowBuilder.setCharAt(offset, 'Q');
            squareStates[rowIndex][offset] = true;
            rowList.add(rowBuilder.toString());
            backtrack(resultList, sideLength, rowList, rowIndex + 1, offset);

            if (!rowList.isEmpty()) {
                rowList.remove(rowList.size() - 1);
                Arrays.fill(squareStates[rowIndex], false);
            }
        }
    }

    private boolean isSquareAvailable(int rowIndex, int columnIndex) {
        if (rowIndex < 0 || rowIndex >= squareStates.length || columnIndex < 0 || columnIndex >= squareStates.length) {
            return false;
        }

        int sideLength = squareStates.length;

        // Description: Both entire row and column must be available.
        for (int index = 0; index < sideLength; index++) {
            if (squareStates[index][columnIndex] || squareStates[rowIndex][index]) {
                return false;
            }
        }

        // Description: From the current row to the top one, check if every top left and
        // top right one is available.
        for (int index = 0; index < rowIndex; index++) {
            int offset = rowIndex - index;
            int leftSquareIndex = columnIndex - offset;
            int rightSquareIndex = columnIndex + offset;

            if ((leftSquareIndex >= 0 && squareStates[index][leftSquareIndex])
                    || (rightSquareIndex < sideLength && squareStates[index][rightSquareIndex])) {
                return false;
            }
        }

        return true;
    }

    private StringBuilder newRow(int sideLength) {
        StringBuilder builder = new StringBuilder(sideLength);

        for (int squareIndex = 0; squareIndex < sideLength; squareIndex++) {
            builder.append(".");
        }

        return builder;
    }
}

相关文章