https://www.acwing.com/solution/content/2820/

https://www.acwing.com/solution/content/30231/

题目描述
blablabla

样例
n−皇后问题是指将 n 个皇后放在 n×n

的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

1_597ec77c49-8-queens.png

现在给定整数 n

，请你输出所有的满足条件的棋子摆法。
输入格式

共一行，包含整数 n

。
输出格式

每个解决方案占 n
行，每行输出一个长度为 n

的字符串，用来表示完整的棋盘状态。

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

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

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

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

1≤n≤9
数据范围

1≤n≤9

输入样例：

4

输出样例：

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

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

算法1
(暴力枚举) O(n2)
blablabla

import java.util.*;
/**
 * Title: Main.java 
 *  @Author molu
 *  @Date 2024年4月11日上午1:37:52
 */
public class Main{
    static int N=20;
    static int n;
    static char[][]g = new char[N][N];///模拟棋盘数组
    static boolean []col = new boolean[N];//列
    static boolean []dg = new boolean[N];//正对角线
    static boolean []udg=new boolean[N];//反对角线
    public static void main(String []args){
        Scanner in = new Scanner(System.in);
        n = in.nextInt();

       // int n = in.nextInt();
       //局部变量如果重新定义，则使用全局变量,造成无输出。

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                g[i][j]='.';
                //先把棋盘上每个位置 初始化为 . 
            }
        }
        dfs(0);
        //从第0层开始搜索
    }
    public static void dfs(int u){

        if(u==n){//n个皇后都放置好了
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    System.out.print(g[i][j]);
                }
                System.out.println();
            }
            System.out.println(); //其他方案数换行
            return; //返回到上一层
        }
        for(int i = 0;i<n;i++){ //i表示的是列数，u表示的是行数

            if(!col[i]&&!dg[u+i]&&!udg[n-u+i])//严格满足列、正对角线、反对角线之前均无放置(标记)过
            {

            g[u][i]='Q';//满足条件的放Q，即皇马的位置
            col[i]=dg[u+i]=udg[n-u+i]=true;//标记满足条件的皇马位置
            dfs(u+1);//继续递归处理下一层

            //将最后放置的皇后位置设置为false，返回上一层，开始回溯。
            //将其列、正对角线和反对角线都设置为false，表示这些位置可以重新模拟，搜索满足条件的位置。
            //再进行递归下一层。
            //回溯的那层，放置的皇后严格满足列、正对角线、反对角线之前均无放置过，否则不能放置于此。
            //如果均未被标记，则将皇后放置于此，否则不满足，置为 . 
             col[i]=dg[u+i]=udg[n-u+i]=false;


            g[u][i]='.';
            //初始化的g[u][i]='.'是先将棋盘所有的点设为 . 
            //为什么这里还需要再写g[u][i]='.';
            //是因为回溯过程中，会模拟皇后走过的位置。
            //如果没有加上这一句，输出方案显示的是到头+回溯过程中皇马模拟走过的所有位置。
            //所以需要加上这一句，将回溯过程中皇后不满足的位置设为 .
        }
        }
    }
}