八皇后

1462707762

问题描述

八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。
该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放
八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或
同一斜线上，问有多少种摆法。
解题思路

一个再经典不过的回溯算法，题目一来，可以直接给他下DFS，一开始其实我是用一个二维数组进行标记，原来还可以很巧妙的使用一位数组的下标跟对应值的关系进行验证，那么思路有了，即是从第一行开始遍历，那么问题又来了，怎么样判断他不合规律捏，横着竖着来就不用说了，斜着的话得思考思考啦，不过也不难，举个例子就可以发现他们的关系，即是纵坐标之差的绝对值跟横坐标之差的绝对值的相等的，没错，就是这样。

回溯点就是每一次进行标记的点与之前标记的点进行规制判断，符合则继续n+1到下一行寻找标记点，不符合则继续在当前行+1的列上标记判断…..
代码实现

public class NQueen {
static final int N = 8; // 皇后的数目
static int ans = 0;
static int[] vis = new int[N];

// n代表行数(即vis数组下标),vis[n]表示列数,所以记当前坐标为(n,vis[n]),数组下标跟跟对应的值
static void dfs(int n) {
    if (n == N) {
        ans++;
    } else
        for (int i = 0; i < N; i++) {
            vis[n] = i;
            if (check(n))// 满足条件继续执行
                dfs(n + 1);
        }
}

static boolean check(int k) {// 判断是否在一条直线上或者一条斜线上
    for (int j = 0; j < k; j++)
        if (Math.abs(vis[k] - vis[j]) == Math.abs(k - j)
                || vis[j] == vis[k])
            return false;
    return true;
}

public static void main(String[] args) {
    dfs(0);
    System.out.println(ans);
}

}