题目描述

n− 皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

现在给定整数 n，请你输出所有的满足条件的棋子摆法。

输入格式
共一行，包含整数 n。

输出格式
每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。

其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。

每个方案输出完成后，输出一个空行。

注意：行末不能有多余空格。

输出方案的顺序任意，只要不重复且没有遗漏即可。

数据范围
1≤n≤9
输入样例：
4
输出样例：
.Q..
…Q
Q…
..Q.

..Q.
Q…
…Q
.Q..

算法dfs

参考文献

y总

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

//数据方位开两倍，因为对角线的数量是2倍
const int N = 20;
//n行n列h个皇后
int n;
//g数组记录n皇后的一种摆放方案
char g[N][N];
//col数组标记一列上能不能放置 ，dg数组标记斜线上能不能放置,udg是反对角线，同理
bool col[N] , dg[N] , udg[N];

void dfs(int u ){
    if(u == n){//u=n说明已经搜索到最后一层了
        //当找到一种方案的时候，直接输出
        for(int i  = 0 ; i < n ; i++)puts(g[i]);//g是二维数组，但是这里是直接输出一行
        puts("");
        return ;
    }
    //开始枚举
    for(int i = 0 ; i < n ; i++ )   {
        //首先这一列上之前没有放过一个皇后,对角线和反对角线上也是
        if(!col[i] && !dg[u + i] && !udg[n - u + i]){//对角线的坐标不懂可以看图解
            g[u][i] = 'Q';
            //当选定i列之后，就要标记这一列不能再放置了，对角线上也是
            col[i] = dg[u + i] = udg[n - u + i] = true ;
            dfs(u + 1);
            //搜索完下面的层数之后，回到当前层的时候要恢复现场
            col[i] = dg[u + i] = udg[n - u + i] = 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);

    return 0;
}

算法dfs(搜索顺序不一样)

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

//数据方位开两倍，因为对角线的数量是2倍
const int N = 20;
//n行n列h个皇后
int n;
//g数组记录n皇后的一种摆放方案
char g[N][N];
//row标记一行上能不能放置，col标记一列上能不能放置 ，dg数组标记斜线上能不能放置,udg是反对角线，同理
bool row[N] , col[N] , dg[N ] , udg[N];

//x横坐标 y纵坐标  s皇后的个数
void dfs(int x ,int y , int s){

    //皇后的个数不会超过n
    if(y == n) y = 0 , x++;
    //当x= n的时候说明已经枚举完最后一行了
    if(x == n){
        //当s=n的时候，说明找到一组解
        if(s == n){
            //输出这组解
            for(int i = 0 ; i < n ; i++)puts(g[i]);
            puts("");

        }
        return;
    }
    //开始枚举每个格子的选择
    //第一种，不放皇后的选择,就直接递归到下一层
    dfs(x , y + 1 , s);
    //第二种，放皇后，先进行条件判断这个格子的这一行列和对角线上没有皇后才能放
    if(!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]){

        g[x][y] = 'Q';
        row[x] = col[y] = dg[x + y] = udg[x - y + n ] = true;
        dfs(x , y + 1 , s + 1);
        row[x] = col[y] = 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;
}