题目描述

n皇后

算法1

C++ 代码

#include<iostream>

using namespace std;

const int N=20;
char g[N][N];

int n;
bool row[N];
bool col[N];
bool dg[N];
bool udg[N];

void dfs(int x,int y,int s)//从左到右，每一行一个个开始遍历
{
    if(y==n)
    {
        y=0;
        ++x;
    }

    if(x==n)//坐标从0开始，搜到第n行结束
    {
        if(s==n)
        {
            for(int i=0;i<n;++i) puts(g[i]);
            puts("");//输出每行后，加换行

        }

        return ;//放在if外面
    }

    //不放
    dfs(x,y+1,s);

    //

    if(!col[y] && !row[x] && !dg[x+y] && !udg[x-y+n] )//坐标和，坐标差相等，数组下标为正数，所以加n
    {
        g[x][y]='Q';
        col[y]=row[x]=dg[x+y]=udg[x-y+n]=true;
        dfs(x,y+1,s+1);

        col[y]=row[x]=dg[x+y]=udg[x-y+n]=false;
        g[x][y]='.';
    }
}


int main()
{
    cin>>n;

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

    dfs(0,0,0);

    return 0;
}