算法OJN-皇后问题回溯剪枝C实现N-Queens

JAY.LIN 收录于算法Oj

2025-03-07 约 942 字预计阅读 2 分钟

https://bing.ee123.net/img/rand?artid=146083103

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

问题描述

The n-queens puzzle is the problem of placing

n n

n queens on an

n × n n \times n

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 × N N \times N

N 的棋盘上放置

N 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 × N N \times N
N
×
N 的棋盘。
皇后数量：
N 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 ! ) O(N!)
O
(
N
!) ，因为每行有
N N
N 种选择，且需要检查冲突。
空间复杂度：
O ( N 2 ) O(N^2)
O
(
N
2
) ，用于存储棋盘和递归栈。