八皇后

题目传送门

大致思路

经典题目,搜索,$a[i]$表示第i行的皇后在第几列
用dfs按行递归,对当前行的每一列做一个尝试,合法就作为答案备选
判断不合法:与先前的皇后在同一列,或在同一条斜线上($|y_1-y_2| == |x_1-x_2|$)

Code

void dfs(int row) {
    if (row >8) {
        cnt++;
        for (int i = 1; i < 9; i++)solutions[cnt][i]=a[i];
        return;
    }
    for (int i = 1; i < 9; i++) {
        bool found = true;
        for (int j = 1; j < row; j++) {
            if (a[j] == i || abs(row - j ) == abs(i - a[j])) {
                found = false;
                break;
            }
        }
        if (found) {
            a[row]=i;
            dfs(row + 1);
        }
    }
}

void solve() {
    int n;
    cin>>n;
    for(int i=1;i<=8;i++) cout<<solutions[n][i];
    cout<<el;
}


Mio_qh main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tt = 1;
    dfs(1);
    cin >> tt;  //多测
    while (tt--) solve();
}