题解 | #八皇后#

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

int num = 0;  //开始存
int ans[92][8];//存八皇后的所有串
int pos[8];//存第i行的皇后存在哪一列，下标为第几行，内容为该行数放于第几列

void DFS(int x) {
    if (x == 8) { //到达递归边界，退出
        for (int i = 0; i < 8; i++) {
            ans[num][i] = pos[i];
        }
        num++;
        return;
    }
    //加入他的邻居，一共有八列可能
    for (int i = 0; i < 8; i++) {
        int j;  //j为所处行数
        for (j = 0; j < x; j++) {//判断已经加入的行数
            if (pos[j] == i ||
                    abs(pos[j] - i) == abs(j - x)) {  //有列已经加入，或者对角线上存在元素(列-列==行-行)
                break;//有冲突，直接退出
            }
        }
        if (j == x) { //遍历结束发现没有冲突
            //加入队伍，x行至于i列
            pos[x] = i;
            DFS(x + 1);
        }

    }
}

int main() {
    int n;
    DFS(0);
    while (cin >> n) {
        for (int i = 0; i < 8; i++) {
            cout << ans[n - 1][i] + 1;
        }
        cout << endl;
    }
    return 0;
}