?算法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 the number of distinct solutions to the n-queens puzzle.

Example 1:

Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

Example 2:

Input: n = 1
Output: 1

#include <iostream>
#include <vector>using namespace std;// 檢查當前位置 (row, col) 是否可以放置皇后
bool isSafe(int row, int col, vector<int>& position) {for (int i = 0; i < row; i++) {// 檢查列和對角線if (position[i] == col || abs(position[i] - col) == abs(i - row)) {return false;}}return true;
}// 回溯函數
void solve(int row, vector<int>& position, int n, int& count) {// 如果當前行是最后一行，說明找到一個解if (row == n) {count++; // 解的數量加 1return;}// 嘗試在當前行的每一列放置皇后for (int col = 0; col < n; col++) {if (isSafe(row, col, position)) { // 如果當前位置安全position[row] = col; // 記錄當前行的皇后位置solve(row + 1, position, n, count); // 遞歸到下一行position[row] = -1; // 回溯，撤銷皇后}}
}// 主函數：求解 N-皇后問題的解的數量
int totalNQueens(int n) {int count = 0; // 記錄解的數量vector<int> position(n, -1); // 記錄每一行皇后的列位置，初始為 -1solve(0, position, n, count); // 從第 0 行開始回溯return count;
}

代碼說明

• isSafe 函數：
  • 檢查當前位置 (row, col) 是否可以放置皇后。
  • 檢查列和對角線是否有沖突。
• solve 函數：
  • 使用回溯算法逐行嘗試放置皇后。
  • 如果找到一個有效位置，遞歸到下一行。
  • 如果當前行所有位置都嘗試完畢，回溯并撤銷上一步的皇后。
• totalNQueens 函數：
  • 初始化一個數組 position，用于記錄每一行皇后的列位置。
  • 調用 solve 函數開始求解，并返回解的數量。

復雜度分析

• 時間復雜度：$O(N!)$，因為每行有 $N$ 種選擇，且需要檢查沖突。
• 空間復雜度：$O(N)$，用于存儲每一行皇后的列位置和遞歸棧。