N皇后问题（DFS-深度优先算法）_dfs算法n皇后

N皇后问题（DFS-深度优先算法）

题目描述:

在 N×N 的方格棋盘放置了 N 个皇后，使得它们不相互攻击（即任意 22 个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成 45° 的斜线上。你的任务是，对于给定的 N，求出有多少种合法的放置方法。

输入描述:

输入中有一个正整数 N<=10，表示棋盘和皇后的数量

输出描述:

为一个正整数，表示对应输入行的皇后的不同放置数量。

输入输出样例:

示例:

输入:

5
1

输出:

10
1

运行限制:

    最大运行时间：1s
    最大运行内存: 256M
1
2

解题思路

1. 设置当前行为第一行，当前列为第一列，从第一行第一列（1,1）开始搜索，也就是说皇后只能从第一行放到第N行，我们也就不用再考虑同一行的问题，只需要去判断同一列和同一斜线的问题。
2. 利用数组进行存储，如：x[a] = i，就表示第a个皇后在第a行的第i列（即不用考虑同一行的问题）；
3. 同一列的判断： 只需要判断其行数和列数是否相等，即 x[a] != x[i]
4. 同一斜线的判断： 只需要判断其 行之差 != 列之差即可
5. 进行搜索： 当搜索到N+1行的时候，就表示第N行已经搜索完成，就将记录进行 +1 处理
6. 若在当前位置上不满足条件就进行回溯

JAVA语言：

import java.util.Scanner;
import static java.lang.Math.abs;
public class Main {
    static int x[] = new int[15];
    static int sum, n;
    static boolean PD(int k) {
        for (int i = 1; i < k; i++) {
            if (abs(k - i) == abs(x[k] - x[i]))
                return false;
            else if (x[k] == x[i])
                return false;
            //即判断是否符合条件来放,i表示皇后所在的行数，x[i]表示所在的列数，
            //所以前面那个条件用来判断两个皇后是否在对角线上,后面用来判断是否在同一列上。
            //行数不需要判断，因为他们本身的i就代表的是行数

        }
        return true;
    }

    static boolean check(int a) {

        if (a > n)
            sum++;
        else
            return false;
        return true;
    }

    static void DFS(int a) {
        if (check(a))
            return;
        else
            for (int i = 1; i <= n; i++) {
                x[a] = i;
                //第a个皇后放的列数
                if (PD(a))
                    //判断是否能放这步
                    DFS(a + 1);
                    //能的话进行下一个皇后的放置
                else continue;
                //不能就下一列
            }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        //表示几个皇后
        DFS(1);
        //每次都从第一个皇后开始
        System.out.println(sum);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52