Java 数据结构与算法：递归实现八皇后问题、思路分析、代码实现

八皇后 回溯算法

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

八皇后游戏连接

. 思路分析

1. 第一个皇后先放在第一行，第一列
2. 第二个皇后放第二行，第一列，然后判断同列是否有皇后，有则放到第二行的第二列，判断是否在同一列，不是再判断是否在同一斜线，如果在同一斜线，就继续放在第二行的第三列，依次类推
3. 每放依次就判断一次，都不行，就回退到上一行，继续放下一列再判断

原则上八皇后可以是8*8的二维数组表示，但是也可以以一维数组表示：

arr[8] ={0, 4, 7, 5, 2, 6, 1, 3}

数组下标索引为n，那么n+1表示皇后在第n+1行

数组arr[n]的值，表示皇后在n+1行的第arr[n]列

. 代码实现

public class EightQueens {
    public static void main(String[] args) {
        EightQueens eightQueens = new EightQueens();
        eightQueens.runEightQueens(0);
        System.out.println("一共"+eightQueens.i+"种走法");
    }

    // 定义一维数组，
    // map[3] 的意义是：第4行第map[3]列可放皇后
    int maxSize = 8;
    int map[] = new int[maxSize];
    int i = 0;

    // 第n个皇后，判断前面的皇后与它是否冲突
    public boolean judge(int n){
        for (int i = 0; i < n; i++) {
            // map[i] == map[n] 同一列
            // Math.abs(n-i) == Math.abs(map[n]-map[i]) 同一斜线
            if ( map[i] == map[n] || Math.abs(n-i) == Math.abs(map[n]-map[i]) ){
                return false;
            }
        }
        return true;
    }

    public void runEightQueens(int n){
        if(n == maxSize){
            i++;
            System.out.println(Arrays.toString(map));
            return;
        }

        // 第n行，也就是第n个皇后，i表示在第n行的所在位置
        for (int i = 1; i <= maxSize; i++) {
            map[n] = i;
            if ( judge(n) ){
                // 如果与前面所放的皇后都不冲突，就进入下一行放皇后
                // 如果冲突，在当前就继续往下一个位置放皇后，再判断
                runEightQueens(n+1);
            }
        }
    }
}

结果：

[1, 5, 8, 6, 3, 7, 2, 4]
[1, 6, 8, 3, 7, 4, 2, 5]
[1, 7, 4, 6, 8, 2, 5, 3]
...
[8, 2, 5, 3, 1, 7, 4, 6]
[8, 3, 1, 6, 2, 5, 7, 4]
[8, 4, 1, 3, 6, 2, 7, 5]
一共92种走法