F1 N-Queens Problem

介绍

N皇后问题（N-Queens Problem）是一个经典的组合优化问题，源于国际象棋。问题要求在N×N的棋盘上放置N个皇后，使得任意两个皇后都不能互相攻击，即不能处于同一行、同一列或同一对角线上。

回溯算法（Backtracking）是解决N皇后问题的标准方法。该算法通过尝试在棋盘上放置皇后，当发现当前放置方案无法继续时，就撤销最近的选择，回溯到上一步并尝试其他可能性，直到找到完整解或尝试所有可能后确认无解。

N皇后问题不仅是理解回溯算法的典型案例，也在计算机科学、人工智能、约束满足问题研究中具有重要意义。

算法步骤

使用回溯算法解决N皇后问题的基本步骤：

1. 从第一行开始，尝试在每一行放置一个皇后

2. 对于当前行，尝试在每一列放置皇后

3. 检查放置是否有效（不与已放置的皇后冲突）

4. 如果有效，则递归处理下一行

5. 如果无法在当前行找到有效位置，则回溯到上一行，尝试其他列位置

6. 当成功放置N个皇后时，记录解决方案

冲突检测

1. 检查同一列是否已有皇后

2. 检查左上到右下对角线是否已有皇后

3. 检查右上到左下对角线是否已有皇后

核心特性

• 递归回溯：通过递归尝试不同放置方案，失败则回溯

• 剪枝：提前检测无效放置，避免无谓的搜索

• 时间复杂度：最坏情况下为O(N!)，实际会因剪枝而降低

• 空间复杂度：O(N)，存储棋盘状态和递归调用栈

• 约束满足：每步决策都必须满足所有已有皇后不受攻击的约束

基础实现

下面展示不同语言的N皇后问题实现：

Java实现

import java.util.*;

public class NQueens {
    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        if (n <= 0) {
            return result;
        }
        
        // 初始化棋盘
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(board[i], '.');
        }
        
        // 回溯求解
        backtrack(board, 0, result);
        return result;
    }
    
    private static void backtrack(char[][] board, int row, List<List<String>> result) {
        // 如果已经放置了n个皇后，记录解
        if (row == board.length) {
            result.add(constructSolution(board));
            return;
        }
        
        int n = board.length;
        // 尝试在当前行的每一列放置皇后
        for (int col = 0; col < n; col++) {
            // 检查是否可以放置
            if (isValid(board, row, col)) {
                // 放置皇后
                board[row][col] = 'Q';
                
                // 递归到下一行
                backtrack(board, row + 1, result);
                
                // 回溯，撤销选择
                board[row][col] = '.';
            }
        }
    }
    
    // 检查在指定位置放置皇后是否有效
    private static boolean isValid(char[][] board, int row, int col) {
        int n = board.length;
        
        // 检查同一列
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }
        
        // 检查左上到右下对角线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        
        // 检查右上到左下对角线
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        
        return true;
    }
    
    // 根据棋盘状态构造解决方案
    private static List<String> constructSolution(char[][] board) {
        List<String> solution = new ArrayList<>();
        for (char[] row : board) {
            solution.add(new String(row));
        }
        return solution;
    }
    
    // 打印棋盘
    private static void printBoard(List<String> board) {
        for (String row : board) {
            System.out.println(row);
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        int n = 4;
        List<List<String>> solutions = solveNQueens(n);
        
        System.out.println(n + "皇后问题的解：");
        System.out.println("共找到 " + solutions.size() + " 种解法
");
        
        for (int i = 0; i < solutions.size(); i++) {
            System.out.println("解法 " + (i + 1) + ":");
            printBoard(solutions.get(i));
        }
    }
}

Python

def solve_n_queens(n):
    if n <= 0:
        return []
    
    # 初始化结果集
    result = []
    
    # 初始化棋盘
    board = [['.' for _ in range(n)] for _ in range(n)]
    
    def is_valid(row, col):
        # 检查同一列
        for i in range(row):
            if board[i][col] == 'Q':
                return False
        
        # 检查左上到右下对角线
        i, j = row - 1, col - 1
        while i >= 0 and j >= 0:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j -= 1
        
        # 检查右上到左下对角线
        i, j = row - 1, col + 1
        while i >= 0 and j < n:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j += 1
        
        return True
    
    def backtrack(row):
        # 如果已经放置了n个皇后，记录解
        if row == n:
            solution = [''.join(row) for row in board]
            result.append(solution)
            return
        
        # 尝试在当前行的每一列放置皇后
        for col in range(n):
            # 检查是否可以放置
            if is_valid(row, col):
                # 放置皇后
                board[row][col] = 'Q'
                
                # 递归到下一行
                backtrack(row + 1)
                
                # 回溯，撤销选择
                board[row][col] = '.'
    
    # 从第一行开始回溯
    backtrack(0)
    return result

# 测试
n = 4
solutions = solve_n_queens(n)
print(f"{n}皇后问题的解：")
print(f"共找到 {len(solutions)} 种解法
")

for i, solution in enumerate(solutions):
    print(f"解法 {i + 1}:")
    for row in solution:
        print(row)
    print()

优化策略

位运算优化

使用位运算提高效率，减少空间和时间消耗：

public static List<List<String>> solveNQueensWithBitwise(int n) {
    List<List<String>> result = new ArrayList<>();
    if (n <= 0) {
        return result;
    }
    
    char[][] board = new char[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(board[i], '.');
    }
    
    // 使用位运算记录已被攻击的列、对角线
    backtrackWithBitwise(board, 0, 0, 0, 0, result);
    return result;
}

private static void backtrackWithBitwise(char[][] board, int row, int cols, int diag1, int diag2, List<List<String>> result) {
    int n = board.length;
    if (row == n) {
        result.add(constructSolution(board));
        return;
    }
    
    // 获取当前行所有可放置皇后的位置
    // (~(cols | diag1 | diag2)) & ((1 << n) - 1) 计算所有可用位置
    int availablePositions = (~(cols | diag1 | diag2)) & ((1 << n) - 1);
    
    while (availablePositions != 0) {
        // 获取最低位的1（表示可以放置皇后的位置）
        int position = availablePositions & -availablePositions;
        // 计算列号
        int col = Integer.bitCount(position - 1);
        
        // 放置皇后
        board[row][col] = 'Q';
        
        // 更新约束并递归到下一行
        backtrackWithBitwise(
            board,
            row + 1,
            cols | position,               // 更新列约束
            (diag1 | position) << 1,       // 更新对角线1约束
            (diag2 | position) >> 1,       // 更新对角线2约束
            result
        );
        
        // 撤销选择
        board[row][col] = '.';
        
        // 清除当前位置，尝试下一个位置
        availablePositions &= (availablePositions - 1);
    }
}

优化冲突检测

使用辅助数组记录已占用的列和对角线，减少冲突检测的时间复杂度：

public static List<List<String>> solveNQueensOptimized(int n) {
    List<List<String>> result = new ArrayList<>();
    if (n <= 0) {
        return result;
    }
    
    char[][] board = new char[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(board[i], '.');
    }
    
    // 记录列和对角线是否被占用
    boolean[] cols = new boolean[n];                // 列
    boolean[] diag1 = new boolean[2 * n - 1];       // 左上到右下对角线
    boolean[] diag2 = new boolean[2 * n - 1];       // 右上到左下对角线
    
    backtrackOptimized(board, 0, cols, diag1, diag2, result);
    return result;
}

private static void backtrackOptimized(char[][] board, int row, boolean[] cols, boolean[] diag1, boolean[] diag2, List<List<String>> result) {
    int n = board.length;
    if (row == n) {
        result.add(constructSolution(board));
        return;
    }
    
    for (int col = 0; col < n; col++) {
        // 计算对角线索引
        int d1 = row + col;            // 左上到右下对角线
        int d2 = row - col + n - 1;    // 右上到左下对角线
        
        // 检查是否可以放置
        if (cols[col] || diag1[d1] || diag2[d2]) {
            continue; // 当前位置被攻击，跳过
        }
        
        // 放置皇后并标记
        board[row][col] = 'Q';
        cols[col] = true;
        diag1[d1] = true;
        diag2[d2] = true;
        
        // 递归到下一行
        backtrackOptimized(board, row + 1, cols, diag1, diag2, result);
        
        // 回溯，撤销选择
        board[row][col] = '.';
        cols[col] = false;
        diag1[d1] = false;
        diag2[d2] = false;
    }
}

优缺点

优点

• 保证找到所有解：回溯法能够系统地找到N皇后问题的所有解

• 剪枝有效：通过提前检测冲突，大幅减少搜索空间

• 内存占用少：只需要记录当前状态，不需要存储搜索路径上的所有状态

• 实现简单：算法思路直观，容易理解和实现

• 通用性：同样的回溯框架可以应用于其他约束满足问题

缺点

• 指数级时间复杂度：最坏情况下为O(N!)，随N增大而迅速增长

• 不适用于大规模问题：当N较大时（如N>20），计算时间过长

• 难以并行化：回溯过程依赖于前序状态，很难并行

• 性能依赖于启发式：没有好的启发式策略，可能导致大量无效搜索

• 递归调用开销：深度递归可能导致栈溢出

应用场景

1. 组合优化问题：解决资源分配、任务调度等约束满足问题

2. 算法教学：作为回溯算法的标准教学案例

3. 并行计算研究：研究NP难问题的并行求解策略

4. 棋盘游戏AI：国际象棋等棋类游戏的局部问题求解

5. 电路设计：某些电路布局问题与N皇后问题类似

扩展

变种N皇后问题

处理棋盘上有障碍物的情况：

public static List<List<String>> solveNQueensWithObstacles(char[][] board) {
    List<List<String>> result = new ArrayList<>();
    if (board == null || board.length == 0) {
        return result;
    }
    
    int n = board.length;
    // 记录列和对角线是否被占用
    boolean[] cols = new boolean[n];
    boolean[] diag1 = new boolean[2 * n - 1];
    boolean[] diag2 = new boolean[2 * n - 1];
    
    // 标记障碍物
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 'X') { // X表示障碍物
                // 障碍物位置不能放置皇后，但也不能被皇后攻击
                board[i][j] = 'X';
            }
        }
    }
    
    backtrackWithObstacles(board, 0, cols, diag1, diag2, result);
    return result;
}

private static void backtrackWithObstacles(char[][] board, int row, boolean[] cols, boolean[] diag1, boolean[] diag2, List<List<String>> result) {
    int n = board.length;
    if (row == n) {
        List<String> solution = new ArrayList<>();
        for (char[] rowArray : board) {
            solution.add(new String(rowArray));
        }
        result.add(solution);
        return;
    }
    
    for (int col = 0; col < n; col++) {
        // 如果当前位置是障碍物，跳过
        if (board[row][col] == 'X') {
            continue;
        }
        
        int d1 = row + col;
        int d2 = row - col + n - 1;
        
        if (cols[col] || diag1[d1] || diag2[d2]) {
            continue;
        }
        
        board[row][col] = 'Q';
        cols[col] = true;
        diag1[d1] = true;
        diag2[d2] = true;
        
        backtrackWithObstacles(board, row + 1, cols, diag1, diag2, result);
        
        board[row][col] = '.';
        cols[col] = false;
        diag1[d1] = false;
        diag2[d2] = false;
    }
}

计算解的数量

只计算N皇后问题解的数量，而不生成具体解：

public static int countNQueensSolutions(int n) {
    if (n <= 0) {
        return 0;
    }
    
    return countSolutions(n, 0, 0, 0, 0);
}

private static int countSolutions(int n, int row, int cols, int diag1, int diag2) {
    if (row == n) {
        return 1; // 找到一个解
    }
    
    int count = 0;
    // 获取当前行所有可放置皇后的位置
    int availablePositions = (~(cols | diag1 | diag2)) & ((1 << n) - 1);
    
    while (availablePositions != 0) {
        // 获取最低位的1
        int position = availablePositions & -availablePositions;
        
        // 递归计算下一行
        count += countSolutions(
            n,
            row + 1,
            cols | position,
            (diag1 | position) << 1,
            (diag2 | position) >> 1
        );
        
        // 清除当前位置，尝试下一个位置
        availablePositions &= (availablePositions - 1);
    }
    
    return count;
}

测验

这里准备了一些测试题，方便大家判断自己的掌握情况：

1. 对于8皇后问题，总共有多少种不同的解？回溯算法大约需要探索多少个状态？

2. 如何优化N皇后问题的冲突检测，使其时间复杂度从O(N)降低到O(1)？

3. 为什么N皇后问题的回溯算法比简单的穷举法（生成所有可能的棋盘状态）更高效？

测验答案

1. 8皇后问题共有92种不同的解。回溯算法需要探索的状态数远少于8^8（所有可能的放置方式），实际约需探索15720个状态，因为大部分无效状态会被提前剪枝。

2. 使用三个布尔数组分别记录列、主对角线和副对角线的占用情况。对于位置(i,j)，列的索引是j，主对角线索引是i+j，副对角线索引是i-j+n-1。通过查表判断是否冲突，将时间复杂度从O(N)降至O(1)。

3. (1)回溯算法利用棋盘特性（每行只能放一个皇后）减少搜索空间；(2)当检测到冲突时立即回溯，不会继续探索无效分支；(3)剪枝策略大幅减少了需要考虑的状态数，而穷举法则需要检查所有N^N种可能的棋盘状态。

相关的 LeetCode 热门题目

给大家推荐一些可以用来练手的 LeetCode 题目：

• 51. N皇后 - 返回所有符合要求的N皇后问题解

• 52. N皇后 II - 返回N皇后问题解的数量

• 37. 解数独

• 79. 单词搜索 - 回溯算法在网格中搜索

• 46. 全排列

N皇后问题是回溯算法的经典应用，通过系统性地搜索解空间，找到所有满足条件的放置方案。这个问题不仅是算法学习的重要案例，也在实际的组合优化问题中有着重要应用。