题目描述

n皇后

样例

C++ 代码

#include<iostream>
#include<cstdio>
using namespace std;

const int N=20;//开两倍

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

void dfs(int u){//每行走
    if(u==n){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cout<<g[i][j];
            }
            cout<<endl;
        }
        cout<<endl;
    }

    for(int i=0;i<n;i++){
        if(!col[i]&&!dg[u+i]&&!udg[n-i+u]) 
        {
            //截距确定，直线也确定了
            //对于u+i，反对角线，行数u增加1，列数i减少1，直线不变，但是位置变了，它固定了那条直线上的值，若u+i不同
            //          则代表它的直线不同
            //对于-i+u，由于可能出现负数，所以+n，变成n-i+u，行数u增加1，列数i减少1，其值不变。

            //对称回溯
            g[u][i]='Q';
            col[i]=dg[u+i]=udg[n-i+u]=true;
            dfs(u+1);
            col[i]=dg[u+i]=udg[n-i+u]=false;
            g[u][i]='.';

        }
    }


}

int main(){

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

    dfs(0);

}