数据结构与算法 — 八皇后问题(回溯算法)

问题描述

在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

假设上图中红点为一个皇后的位置，那么他的同行，列，斜线上都不能再放置其他皇后(也就是红线覆盖的位置)

此图为八皇后问题的其中一种解法，目前已经有人用图论的方法解出92种结果。

思路分析

一、如何实现

这就和我们人做这种题的时候一样，所有放置皇后的过程都是一行一行来的，首先将第一行的皇后放在第一个位置，然后再看第二行。最开始也是将第二行的皇后放在第二行的第一个位置，发现冲突了，然后在移到第二行的第二个位置，还是冲突了，就再次移动，直到不与之前的皇后冲突，就开始进行下一行的放置以此类推。如果遇到了一整行都是与之前放置的皇后冲突的话就会从上一行里进行改变（比如在放第8行的皇后时，发现所有位置都不成立，那么他就会到第7行中，寻找符合的位置，再不行就到第6行里找，以此类推、、、）。

二、保存结果

一般这种图，我们都是用二维数组来表示的。但是这里我们可以使用普通的数组来表示。创建一个array数组，长度为8。array={2，5，1，6，0，3，7，4}，这就代表着一种解法。下标为0的值为2，就代表第1行的第二个位置放置了一个皇后，下标为1的值为5，就代表第二行的第5个位置放置了一个皇后。以此类推。。。算法结束后，我们只需要遍历数组就可以得到解法。

三、检验是否冲突

这个问题中，检验是否冲突是很重要的一步。同行与同列都是很容易检验的。因为是普通的数组，不同的下标就代表着不同的行，所以这本身就解决了皇后同行的问题。检验是否同列，只需要在放入新皇后的时候，看看它的值，是否与其他下标的值相同，相同则表示他们在同一列。
检验是否在同一斜线也很容易理解，如果他们在同一斜线，那么这条斜线的斜率就为1，这两个皇后的行之差的绝对值与列之差的绝对值相同那么就是在同一直线上。你也可以把它想作是一个等腰RT三角形，它的两个直角边相同，他们两个肯定就是在同一直线上。

如图，绿点和红点分别是两个皇后，他们的行坐标之差的绝对值为abs(4-2)=2。列坐标之差的绝对值为abs(2-4)=2。两者相等那么就代表他们处于同一斜线，不能成立。

代码实现

public class Queens {
    int max = 8; //一共8个皇后，定义初始值
    int[] array = new int[max];
    static int count=0;
    public static void main(String[] args) {
        Queens queens = new Queens();
        queens.put(0);
        System.out.println(count);
    }

    //结果输出方法
    private void print() {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
        }
        System.out.println();
    }

    //检查放到第n个皇后时，是否与之前的皇后冲突
    private boolean check(int n) {
        for (int i = 0; i < n; i++) {
            if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[i] - array[n])) {
                return false;
            }
        }
        return true;
    }

    //放置第n个皇后
    private void put(int n){
        if (n == max){ //因为下标是从0开始的，所以当n=8时代表再放就是第九个皇后了，就是已经放完了8个。直接打印结果即可。
            count++;
            print();
            return;
        }
        for (int i=0;i<max;i++){
            array[n] = i;//先把这个皇后放到此行的第一个位置
            if (check(n)){//检查放第n个皇后时是否冲突，不冲突的话就继续放置第n+1个。
                put(n+1);
            }
        }//如果冲突了就继续执行 array[n] = i这就相当于这一行的这个位置是不行的，我们要试试下个位置了
    }
}

运行结果

因为解法一共有很多很多种，这里只截取了部分，但是最后输出了解法总个数为92个。