N-皇后问题的回溯算法实现

N-皇后问题的回溯算法实现

引用

CSDN

1.

https://blog.csdn.net/Vitalia/article/details/146083103

问题描述

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

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：存在两种不同的4-皇后问题的解，如上图所示。

示例 2：

输入：n = 1
输出：[["Q"]]

关键点

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