题目描述

1.每一行只有一个Q，n个空，1…n代表行数，对应的空填写的就是填写Q的列，

样例

import java.util.Scanner;

public class Main {
    //对角线的个数是2n-1
    static final 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];

    static void dfs(int u) {
        //如果u == n 说明我们找到了一组方案
        if (u == 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;
        }

        //u代表行，i代表列
        for (int i = 0; i < n; i++)
            //判断该位置能否存放Q
            //反对角线和对角线坐标，就是截距b  y=x+b y=-x+b b=y-x(为了防止负数，加一个n)  b= y+x
            if (!col[i] && !dg[i + u] && !udg[i - u + n]) {
                //当前位置存放Q
                g[u][i] = 'Q';
                //对应的列、对角线和反对角线设为true 代表出现了
                col[i] = dg[i + u] = udg[i - u + n] = true;
                //向下 找下一行
                dfs(u + 1);
                //恢复对应的列、对角线和反对角线的值，设为false
                col[i] = dg[i + u] = udg[i - u + n] = false;
                //对应的值恢复为.
                g[u][i] = '.';
            }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();

        //初始全部设为.
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                g[i][j] = '.';

        dfs(0);

        scanner.close();
    }
}

对角线和反对角线

2.对于每个格子，我们只考虑放皇后还是不放皇后

import java.util.Scanner;

public class Main {
    static final int N = 10;
    static int n;
    static boolean[] row = new boolean[N];
    static boolean[] col = new boolean[N];
    static boolean[] dg = new boolean[N * 2];
    static boolean[] udg = new boolean[N * 2];
    static char[][] g = new char[N][N];

    static void dfs(int x, int y, int s) {

        //如果y出界了，y=0,x++ 进入到下一行，并且列重新定位到0
        if (y == n) {
            y = 0;
            x++;
        }

        //如果x=n 说明枚举完最后一行了
        if (x == n) {
            //如果现在放入的皇后数量刚好为n 说明我们找到了一种方案
            if (s == 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;
        }

        //不放皇后，进入下一列
        dfs(x, y + 1, s);

        // 放皇后
        //一样的判定
        if (!row[x] && !col[y] && !dg[y + x] && !udg[y - x + n]) {
            //当前位置放入Q
            g[x][y] = 'Q';
            ///对应的列、对角线和反对角线设为true 代表出现了
            row[x] = col[y] = dg[y + x] = udg[y - x + n] = true;
            //到下一列，放入的皇后加1
            dfs(x, y + 1, s + 1);
            //恢复对应的列、对角线和反对角线的值，设为false
            row[x] = col[y] = dg[y + x] = udg[y - x + n] = false;
            //对应的值恢复为.
            g[x][y] = '.';
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();

        //初始全部设为.
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                g[i][j] = '.';

        dfs(0, 0, 0);

        scanner.close();
    }
}