n

n

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

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

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

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

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

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

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

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

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

.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

算法思路：

• 函数名：void dfs(int r): 深度优先遍历函数。参数r：从第r行开始放棋子，处理第r行。
• 递归结束判定：见代码，当 r == n的时候，说明应该处理第 n行了，也代表第 0~n-1行放好棋子，也就是整个棋盘放好了棋子，也就是得到了一种解，也就是递归结束。
• 第r行，第i列能不能放棋子：用数组dg udg row col 分别表示：点对应的两个斜线以及行列上是否有皇后。 dg[i + r] 表示 r行i列处，所在的对角线上有没有棋子，udg[n - i + r]表示 r行i列处，所在的反对角线上有没有棋子，col[i]表示第i列上有没有棋子。如果 r行i列的对角线，反对角线上都没有棋子，即!row[i]&&!col[i] && !dg[i + r] && !udg[n - i + r]为真，则代表 r行i列处可以放棋子。

C++

#include<iostream>
using namespace std;
ct int  = 20;
int n;
char g[][];
bool row[], col[], dg[], udg[];

void dfs(int u)
{
    if (u == n)
    {
        for (int i = 0; i < n; ++ i) puts(g[i]);
        puts("");
        return;
    }
    for (int i = 0; i < n; ++ i)  // 一列一列的枚举
    {
        if (!row[u] && !col[i] && !dg[u + i] && !udg[n - u + i])  // 这里的这个dg和udg是最难理解的
        // u + i = c1 这个c1可以确定正斜线上面的一个点, -u + i = c2,这个c2可以确定反斜线上面的以一个点
        // 这里c2可能为负数 所以要加一个偏移量n
        {
            g[u][i] = 'Q';
            row[u] = col[i] = dg[u + i] = udg[n - u + i] = true;
            dfs (u + 1);
            row[u] = 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;
}

Java

import java.util.*;

public class Main
{
    static Scanner in = new Scanner(System.in);
    static int  = 20;
    static boolean[] col = new boolean[], dg = new boolean[], udg = new boolean[];
    static int n = 0;
    static char[][] chs = new char[][];
    
    static void dfs (int u)
    {
        if (u > n)
        {
            for (int i = 1; i <= n; ++ i)
            {
                for (int j = 1; j <= n; ++ j) 
                {
                    print(chs[i][j]);   
                }
                println();    
            }
            println();
            return;
        }
        for (int i = 1; i <= n; ++ i)
        {
            if (!col[i] && !dg[i - u + n] && !udg[i + u])
            {
                chs[u][i] = 'Q';
                col[i] = dg[i - u + n] = udg[i + u] = true;
                dfs(u + 1);
                col[i] = dg[i - u + n] = udg[i + u] = false;
                chs[u][i] = '.';
            }
        }
    }
    
    
    public static void main(String[] args)
    {
        n = ();
        for (int i = 1; i <= n; ++ i)
        {
            for (int j = 1; j <= n; ++ j) chs[i][j] = '.';
        }
        dfs(1);
    }
}