回溯困难1 种解法

#51N 皇后

在 n × n 棋盘上放置 n 个皇后，使任意两个皇后不在同列或同一条对角线上。

#回溯#棋盘#剪枝

解题主线

按行递归后无需检查同行，只需记录列、主对角线 row - col 和副对角线 row + col 是否被占用。

两个对角线索引都可平移到 0 到 2n - 2 的数组范围。

完成第 n 行后必须保存棋盘并立即 return。

解法 1：按行回溯 + 占用数组

逐行选择列，使用三个 boolean 数组 O(1) 判断列和两类对角线冲突。

时间复杂度

O(n!)，按行且列不重复后的搜索树上界

空间复杂度

O(n²)，棋盘占 O(n²)，递归与占用数组占 O(n)

51. N 皇后 · 按行回溯 + 占用数组

java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

final class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        if (n <= 0) {
            return result;
        }
        char[][] board = new char[n][n];
        for (char[] row : board) {
            Arrays.fill(row, '.');
        }
        backtrack(0, board, new boolean[n], new boolean[2 * n - 1],
                new boolean[2 * n - 1], result);
        return result;
    }

    private void backtrack(int row, char[][] board, boolean[] columns,
                           boolean[] diagonals, boolean[] antiDiagonals,
                           List<List<String>> result) {
        int n = board.length;
        if (row == n) {
            List<String> placement = new ArrayList<>(n);
            for (char[] line : board) {
                placement.add(new String(line));
            }
            result.add(placement);
            return;
        }
        for (int column = 0; column < n; column++) {
            int diagonal = row - column + n - 1;
            int antiDiagonal = row + column;
            if (columns[column] || diagonals[diagonal] || antiDiagonals[antiDiagonal]) {
                continue;
            }
            board[row][column] = 'Q';
            columns[column] = diagonals[diagonal] = antiDiagonals[antiDiagonal] = true;
            backtrack(row + 1, board, columns, diagonals, antiDiagonals, result);
            columns[column] = diagonals[diagonal] = antiDiagonals[antiDiagonal] = false;
            board[row][column] = '.';
        }
    }
}

逐行选择列，使用三个 boolean 数组 O(1) 判断列和两类对角线冲突。

合并 char[][] 与 List<String> 两种同构实现，保留更直接且冲突检查为 O(1) 的棋盘版本。

边界与易错点

旧 char[][] 版本在 row == n 保存结果后没有返回，随后访问 board[n] 会越界。
放置皇后后要同步设置三组占用状态，回溯时也必须全部清除。
结果中每一行要创建新 String，不能暴露之后还会修改的 char[]。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

backtrack/Q051_NQueens.javabacktrack/Q051_nQueen.java