⭐算法OJ⭐N-皇后问题【回溯剪枝】（C++实现）N-Queens

问题描述

The n-queens puzzle is the problem of placing $n$ queens on an $n\times n$ chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

在 $N\times N$ 的棋盘上放置 $N$ 个皇后，使得它们互不攻击。皇后可以攻击同一行、同一列或同一对角线上的任何棋子。因此，需要找到所有可能的皇后位置，满足这些条件。

Example 1:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

Input: n = 1
Output: [["Q"]]

关键点

• 棋盘大小：$N\times N$ 的棋盘。
• 皇后数量：$N$ 个皇后。
• 攻击规则：
  • 不能在同一行。
  • 不能在同一列。
  • 不能在同一对角线。

解决方法

回溯算法

• 逐行放置皇后。
• 每放置一个皇后，检查是否与已放置的皇后冲突。
• 如果冲突，回溯并尝试下一个位置。
• 找到所有可能的解。

递归实现

• 使用递归尝试每一行的每个位置。
• 通过剪枝减少无效搜索。

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// 检查当前位置 (row, col) 是否可以放置皇后
bool isSafe(int row, int col, vector<string>& board, int n) {
    // 检查列
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') {
            return false;
        }
    }

    // 检查左上对角线
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') {
            return false;
        }
    }

    // 检查右上对角线
    for (int i = row, j = col; i >= 0 && j < n; i--, j++) {
        if (board[i][j] == 'Q') {
            return false;
        }
    }

    return true;
}

// 回溯函数
void solve(int row, vector<string>& board, vector<vector<string>>& result, int n) {
    // 如果当前行是最后一行，说明找到一个解
    if (row == n) {
        result.push_back(board); // 将当前棋盘配置存入结果
        return;
    }

    // 尝试在当前行的每一列放置皇后
    for (int col = 0; col < n; col++) {
        if (isSafe(row, col, board, n)) { // 如果当前位置安全
            board[row][col] = 'Q'; // 放置皇后
            solve(row + 1, board, result, n); // 递归到下一行
            board[row][col] = '.'; // 回溯，撤销皇后
        }
    }
}

// 主函数：求解 N-皇后问题
vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> result; // 存储所有解
    vector<string> board(n, string(n, '.')); // 初始化棋盘，所有位置为空（'.'）
    solve(0, board, result, n); // 从第 0 行开始回溯
    return result;
}

代码解释

• isSafe 函数：

  • 检查当前位置 (row, col) 是否可以放置皇后。
  • 检查列、左上对角线和右上对角线是否有冲突。

• solve 函数：

  • 使用回溯算法逐行尝试放置皇后。
  • 如果找到一个有效位置，递归到下一行。
  • 如果当前行所有位置都尝试完毕，回溯并撤销上一步的皇后。

• solveNQueens 函数：

  • 初始化棋盘（用 '.' 表示空位）。
  • 调用 solve 函数开始求解。

复杂度分析

• 时间复杂度：$O(N!)$，因为每行有 $N$ 种选择，且需要检查冲突。
• 空间复杂度：$O(N^2)$，用于存储棋盘和递归栈。