n皇后问题(dfs搜索)

解题思路:
下面是用递归的深度优先搜索求解n皇后问题的算法描述：

这里用一个N×N的矩阵来表示棋盘，但是我们不需要定义这样的数组，只要心中有N×N的棋盘即可。

1.算法开始：

当前行设为第一行，当前列设为第一列，从第一行第一列开始搜索，即只能让皇后从第一行放到第n行。

这样在每次判断是否满足情况时我们不用去判断是否皇后在相同行。

我们只用判断之前的 1 到 k - 1个皇后的位置和当前第k个皇后的位置是否属于同一列或者斜线，判断是否同一列。

2.判断边界条件：

在当前行，当前列的位置上判断是否满足条件(即保证经过这一点的行,列与斜线上都没有两个皇后)，若不满足，跳到第 5 步，即不符合边界条件。

不符合边界条件，不只是跳出了搜索范围，剪枝也可以从这里开始，比如这里不满足条件，向下继续搜索也不会再有结果。

这可以理解为超出边界的剪枝，我们的边界只得可能存在解的范围，这里已经超出有解的范围，必然要被踢出。

判断条件：

我们用数组 x[k] = i 来表示第 k 个皇后在第 k 行第 i 列，不用考虑是否在同一行的问题，只用判断之前的 1 到 k - 1个皇后的位置与当前的第 k 个皇后是否在同列或同一斜线。

同列条件： x[i] == x[k];      同一斜线斜率相同：abs(x[k] - x[i]) == abs(k-i);

3.搜索方法：

判断边界条件，搜索下一个皇后的位置。

4.pd2函数停止条件：

如果当搜索到第N+1 行的时候，即代表前N 行已经搜索完了，所以这个时候正好求出了一个解，记录加一，返回上一层搜索。

5.在当前位置上不满足条件的情形，进行回溯。

参考代码:

import java.util.Scanner;

public class Main {
    static int n;//皇后数
    static int sum;//方案数
    static int[] x;

    // 判断是否符合放置条件
    static boolean pd1(int k) {
        //k为行号，x[k]为列号
        //将k行的皇后分别与上面的进行比对，看是否同线
        for (int i = 1; i < k; i++) {
            //在同一斜线上，直线的斜率为+-1
            if (Math.abs(k - i) == Math.abs(x[k] - x[i]))
                return false;
                //在同一列
            else if (x[k] == x[i])
                return false;
        }
        return true;
    }

    //判断是否摆放完成
    static boolean pd2(int k) {
        //行号已经出界，摆放完成，return true;方案数加一
        if (k > n)
            sum++;
        else
            return false;
        return true;
    }

    static void DFS(int k) {
        //摆放完成，返回上一层
        if (pd2(k)) {
            //输出前3种方法
            if (sum <= 3) {
                for (int i = 1; i <= n; i++) {
                    System.out.print(x[i] + " ");
                }
                System.out.println();
            }
            return;
        } else {
            for (int i = 1; i <= n; i++) {
                //将第k个(行)皇后放在第i列上
                x[k] = i;
                //能摆放这个位置
                if (pd1(k)) {
                    //寻找下一个位置
                    DFS(k + 1);
                } else {
                    //找不到列号往后移动
                    continue;
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        x = new int[n + 1];
        DFS(1);//从第一个开始放
        System.out.print(sum);
    }
}