回溯法-n皇后问题_回溯法解决n皇后问题时间复杂度

问题描述：在nxn的棋盘上，放置彼此不受攻击的n个皇后。

规则：皇后可以攻击与之在同一行，同一列，同一斜线上的棋子。

以行为主导（不用再判断是否同行了）

算法设计：

（1）定义问题的解空间：问题解的形式为n元组：

分量xi表示第i个皇后放置在第i行，第xi列。

（2）解空间的组织结构：m叉树

（3）搜索解空间：

约束条件：

，不同列。

，不同斜线。

限界条件：不存在放置方案好坏的问题。

搜索过程：从根开始，以深度优先搜索的方式进行搜索。根结点是活结点，并且是当前的扩展结点。

#include <iostream>
#include <cmath>
 
#define M 105
using namespace std;
 
int n;
int x[M];
int countn;
 
bool Place(int t) {
    bool ok = true;
    for (int j = 1; j < t; j++) {
        if (x[t] == x[j] || t - j == fabs(x[t] - x[j])) {
            ok = false;
            break;
        }
    }
    return ok;
}
 
void Backtrack(int t) {
    if (t > n) {
        countn++;
        for (int i = 1; i <= n; i++)
            cout << x[i] << " ";
        cout << endl;
        cout << "----------" << endl;
    } else
        for (int i = 1; i <= n; i++) {
            x[t] = i;
            if (Place(t))
                Backtrack(t + 1);
        }
}
 
int main() {
    cout << "请输入皇后的个数n: ";
    cin >> n;
    countn = 0;
    Backtrack(1);
    cout << "答案的个数是： " << countn << endl;
    return 0;
}

算法复杂度分析：

（1）时间复杂度：

除最后一层：个结点需要扩展。

每个结点需要扩展n个分支：

每分支都要判断约束：

叶子个数，每个叶子输出最优解：

因此，时间复杂度为：

（2）空间复杂度：

x[]记录可行解，因此为：O(n)

算法优化扩展：

问题：解空间过大。

原因：使用了不同行作为显约束，使用了不同列，不同斜线作为隐约束。

改进：使用不同行，不同列作为显约束，使用不同斜线作为隐约束，缩小解空间。此时解空间树变为排列树。

例如：

x1=1，则x2不能等于1

x1=1，x2=2，则x3不能等于1，2