每次回溯檢查對角線和直行

注意題目要排序

#include <bits/stdc++.h>
using namespace std;

int N;
vector<vector<int>> ans;
vector<int> path;
vector<bool> col,d1,d2;

void dfs(int r){
    if (r==N){
        ans.push_back(path);
        return;
    }
    for (int c=0 ; c<N ; c++){
        if (col[c] || d1[r-c+N-1] || d2[r+c]) continue;
            col[c] = d1[r-c+N-1] = d2[r+c] = true;
            path[r]=c;
            dfs(r+1);
            col[c] = d1[r-c+N-1] = d2[r+c] = false;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    while (cin>>N){
        if (N==0) break;
        ans.clear();
        path.assign(N,0);
        col.assign(N,false);
        d1.assign(2*N-1,false);
        d2.assign(2*N-1,false);
        dfs(0);
        
        sort(ans.begin(),ans.end());
        for (auto &x:ans){
            for (int r=0 ; r<N ; r++){
                for (int c=0 ; c<N ; c++){
                    if (c==x[r]) cout<<'Q';
                    else cout<<'x';
                }
                cout<<"\n";
            }
            cout<<"\n";
        }
        cout<<ans.size()<<"\n\n";
    }
    return 0;
}