目录

1.问题描述

2.问题分析

3.完整源码

---

1.问题描述

八皇后问题是十九世纪著名的数学家高斯于1850年提出的。问题是:在8×8的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。可以把八皇后问题扩展到n皇后问题，即在n×n的棋盘上摆放n个皇后，使任意两个皇后都不能处于同一行、同一列或同一斜线上。 

---

2.问题分析

确定问题状态:问题的状态即棋盘的布局状态

构造状态空间树:状态空间树的根为空棋盘，每个布局的下一步可能布局是该布局结点的子结点。

-由于可以预知，在每行中有且只有一个皇后，因此可采用逐行布局的方式，即每个布局有个子结点。

●设4个皇后为x;，分别在第i行(i=1，2，3，4);

●问题的解状态:可以用(1,x)，(2,t2)，.......，(4,x4)表示4个皇后的位置

●由于行号固定，可简单记为: (X1,x2,X3,t4);例如:(4,2,1,3)

●问题的解空间: (x1,X2,x3,x4)， 1≤x;<4(i=1，2，3，4)，共4!个状态;

回溯法求解4皇后问题的搜索过程:

先将第一个皇后放在第一行的第一列上，符合题目要求

开始放置第二个皇后。放在第二行的第一个与第一行的皇后为同一列，不符合题意，继续向后搜素，放在第二列上面与第一个皇后在同一斜线上，不符合题意，继续向后搜素，发现放在第三列符合题意

开始放置第三个皇后。放在第三行的任意位置都会出现冲突，此时需要回溯，将第二个皇后放置在第四列，此时符合题意，继续放置第三个皇后，发现第三个皇后放置在第三行的第二列符合题意

继续放置第四个皇后。放在第四行的任意位置都会出现冲突，此时需要回溯，第三个皇后向后移动，发现依然不符合题意，继续回溯，第二行的皇后无法再向后移动，继续回溯，将第一个皇后向后移动到第二列，符合题意

移动第二个皇后，发现放在第四列符合题意

移动第三个皇后，发现放在第一列符合题意

移动第四个皇后，发现放在第三列符合题意

回溯结束

---

3.完整源码

#include <iostream>
using namespace std;
const int N = 20; 

// bool数组用来判断搜索的下一个位置是否可行
// col列，dg对角线，udg反对角线
// g[N][N]用来存路径

int n;
char g[N][N];
bool col[N], dg[N], udg[N];

void dfs(int u) {
    // u == n 表示已经搜了n行，故输出这条路径
    if (u == n) {
        for (int i = 0; i < n; i ++ ) puts(g[i]);   // 等价于cout << g[i] << endl;
        puts("");  // 换行
        return;
    }

    // 枚举u这一行，搜索合法的列
    int x = u;
    for (int y = 0; y < n; y ++ )
        // 剪枝(对于不满足要求的点，不再继续往下搜索)  
        if (col[y] == false && dg[y - x + n] == false && udg[y + x] == false) {
            col[y] = dg[y - x + n] = udg[y + x] = true;
            g[x][y] = 'Q';
            dfs(x + 1);
            g[x][y] = '.';  // 恢复现场
            col[y] = dg[y - x + n] = udg[y + x] = false;
        }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            g[i][j] = '.';

    dfs(0);

    return 0;
}