Java实现的N皇后问题在N≥30时运行冻结 如何支持N到150及以上

问题根因 #

你当前使用的朴素回溯算法时间复杂度为O(N!)，N=30时计算量已经达到天文数字，程序无响应并非冻结，只是在穷举所有可能的落子路径，无法在可接受时间内完成计算。

优化方案 #

1. 安全校验逻辑优化（必改，性能提升10~100倍） #

原有isSafe方法每次判断需要遍历3条线，时间复杂度为O(N)，可以通过3个布尔数组记录占用状态，将判断逻辑降到O(1)：

// 类内新增三个全局标记数组
boolean[] rowUsed; // 记录某行是否已放皇后
boolean[] mainDiagUsed; // 记录主对角线（左上到右下）是否已放皇后，索引计算规则：row - col + N - 1
boolean[] subDiagUsed; // 记录副对角线（右上到左下）是否已放皇后，索引计算规则：row + col

// 初始化时创建数组
boolean solveNQ() {
    rowUsed = new boolean[N];
    mainDiagUsed = new boolean[2 * N - 1];
    subDiagUsed = new boolean[2 * N - 1];
    int board[][] = new int[N][N];
    // 其余原有逻辑不变
}

// 替换原有isSafe方法
boolean isSafe(int row, int col) {
    return !rowUsed[row] && !mainDiagUsed[row - col + N - 1] && !subDiagUsed[row + col];
}

// 放置/撤回皇后时同步更新标记数组
// 放置皇后时调用：placeQueen(row, col, true)
// 回溯撤回时调用：placeQueen(row, col, false)
void placeQueen(int row, int col, boolean isPlace) {
    rowUsed[row] = isPlace;
    mainDiagUsed[row - col + N - 1] = isPlace;
    subDiagUsed[row + col] = isPlace;
}

修改solveNQUtil逻辑，放置和撤回皇后时调用上述标记方法，无需再修改board数组也能完成校验，如果不需要打印棋盘甚至可以直接删掉board数组，用一维数组记录每列皇后的行号即可。

2. 回溯剪枝优化 #

不要固定按列顺序遍历，可以优先选择可选落子位置最少的列放置皇后，大幅减少无效搜索路径，性能可再提升数倍到数十倍。

3. 构造法（最优，可支持N>10000） #

如果你只需要输出任意一个合法解而非所有解，可以直接用N皇后的数学构造法，时间复杂度仅为O(N)，完全满足N=255的需求：

• 若N mod 6 不等于2或3：
  1. 先按顺序放置所有偶数行：2、4、6...N
  2. 再按顺序放置所有奇数行：1、3、5...N-1
• 若N mod 6等于2或3：
  令m=N/2，若m为奇数，先按顺序放置m、m+2、m+4...N、2、4...m-2，再放置m+3、m+5...N-1、1、3...m+1；若m为偶数调整对应顺序即可，无需回溯就能直接生成合法解。

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