【算法】 八皇后问题--回溯算法

1、八皇后问题介绍

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。
该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。
1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。

2、java实现

package com.data.algorithm.Queue8;

/**
 * 八皇后问题
 * 介绍：
 *     回溯算法的经典案例，在8*8格的国际象棋上摆放8个皇后，使其不能相互攻击，既：
 *  任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法？
 *
 * 解析：
 *     1 第一个皇后先放第一行第一列
 *     2 第二个皇后放第二行第一列，然后判断是否OK，如果不OK,继续放第二列，第三列，依次把所有列都放完
 *     3 继续放第三个皇后，还是第一列，第二列。。。直到第8个皇后也能放在一个不冲突的位置，算是找到一个正确的答案。
 *     4 当得到一个正确答案时，再退回上个栈，开始回溯，既得到所有解。
 *     5
 *
 * @author wangjie
 * @version V1.0
 * @date 2020/3/4
 */
public class Queue8 {

    //表示有多少皇后
    private int max = 8;

    //定义一个数组表示棋盘，下标表示行，值表示列
    private int [] array;

    //记录正确答案数量
    private static int count = 0;

    public Queue8() {
        this.array = new int[this.max];
    }

    public static void main(String[] args) {
        Queue8 queue8 = new Queue8();
        queue8.check(0);
        System.out.printf("一共有%d解法", count);
    }

    /**
     * 放置第n个皇后
     * @param n
     */
    private void check(int n) {
        if (n == this.max) {
            //n=8时，说明前8个皇后已经放好（n=0是第一个），得到了正确的答案，可以打印并结束，可以返回继续回溯了
            this.print();
        } else {
            //依次放入皇后
            for(int i = 0; i < this.max; ++i) {
                this.array[n] = i;
                //如果不相互攻击，就接着放下一个
                if (this.judge(n)) {
                    //递归
                    this.check(n + 1);
                }
                //无论是发生了相互攻击，还是递归结束返回答案，都开启下一轮尝试
            }

        }
    }

    /**
     *  判断放置第n个皇后时，会不会与之前放置的皇后发生攻击
     * @param n
     * @return
     */
    private boolean judge(int n) {
        for(int i = 0; i < n; ++i) {
            //同一列，同一斜线的皇后会相互攻击
            if (this.array[i] == this.array[n] || Math.abs(n - i) == Math.abs(this.array[n] - this.array[i])) {
                return false;
            }
        }
        return true;
    }

    /**
     * 打印棋盘中皇后所在位置，下标表示行，值表示列
     */
    private void print() {
        ++count;

        for(int i = 0; i < this.array.length; ++i) {
            System.out.print(this.array[i] + " ");
        }

        System.out.println();
    }
}

• 运行结果：

0 4 7 5 2 6 1 3 
0 5 7 2 6 3 1 4 
0 6 3 5 7 1 4 2 
0 6 4 7 1 3 5 2 
1 3 5 7 2 0 6 4 
1 4 6 0 2 7 5 3 
1 4 6 3 0 7 5 2 
1 5 0 6 3 7 2 4 
1 5 7 2 0 3 6 4 
1 6 2 5 7 4 0 3 
1 6 4 7 0 3 5 2 
1 7 5 0 2 4 6 3 
2 0 6 4 7 1 3 5 
2 4 1 7 0 6 3 5 
2 4 1 7 5 3 6 0 
2 4 6 0 3 1 7 5 
2 4 7 3 0 6 1 5 
2 5 1 4 7 0 6 3 
2 5 1 6 0 3 7 4 
2 5 1 6 4 0 7 3 
2 5 3 0 7 4 6 1 
2 5 3 1 7 4 6 0 
2 5 7 0 3 6 4 1 
2 5 7 0 4 6 1 3 
2 5 7 1 3 0 6 4 
2 6 1 7 4 0 3 5 
2 6 1 7 5 3 0 4 
2 7 3 6 0 5 1 4 
3 0 4 7 1 6 2 5 
3 0 4 7 5 2 6 1 
3 1 4 7 5 0 2 6 
3 1 6 2 5 7 0 4 
3 1 6 2 5 7 4 0 
3 1 6 4 0 7 5 2 
3 1 7 4 6 0 2 5 
3 1 7 5 0 2 4 6 
3 5 0 4 1 7 2 6 
3 5 7 1 6 0 2 4 
3 5 7 2 0 6 4 1 
3 6 0 7 4 1 5 2 
3 6 2 7 1 4 0 5 
3 6 4 1 5 0 2 7 
3 6 4 2 0 5 7 1 
3 7 0 2 5 1 6 4 
3 7 0 4 6 1 5 2 
3 7 4 2 0 6 1 5 
4 0 3 5 7 1 6 2 
4 0 7 3 1 6 2 5 
4 0 7 5 2 6 1 3 
4 1 3 5 7 2 0 6 
4 1 3 6 2 7 5 0 
4 1 5 0 6 3 7 2 
4 1 7 0 3 6 2 5 
4 2 0 5 7 1 3 6 
4 2 0 6 1 7 5 3 
4 2 7 3 6 0 5 1 
4 6 0 2 7 5 3 1 
4 6 0 3 1 7 5 2 
4 6 1 3 7 0 2 5 
4 6 1 5 2 0 3 7 
4 6 1 5 2 0 7 3 
4 6 3 0 2 7 5 1 
4 7 3 0 2 5 1 6 
4 7 3 0 6 1 5 2 
5 0 4 1 7 2 6 3 
5 1 6 0 2 4 7 3 
5 1 6 0 3 7 4 2 
5 2 0 6 4 7 1 3 
5 2 0 7 3 1 6 4 
5 2 0 7 4 1 3 6 
5 2 4 6 0 3 1 7 
5 2 4 7 0 3 1 6 
5 2 6 1 3 7 0 4 
5 2 6 1 7 4 0 3 
5 2 6 3 0 7 1 4 
5 3 0 4 7 1 6 2 
5 3 1 7 4 6 0 2 
5 3 6 0 2 4 1 7 
5 3 6 0 7 1 4 2 
5 7 1 3 0 6 4 2 
6 0 2 7 5 3 1 4 
6 1 3 0 7 4 2 5 
6 1 5 2 0 3 7 4 
6 2 0 5 7 4 1 3 
6 2 7 1 4 0 5 3 
6 3 1 4 7 0 2 5 
6 3 1 7 5 0 2 4 
6 4 2 0 5 7 1 3 
7 1 3 0 6 4 2 5 
7 1 4 2 0 6 3 5 
7 2 0 5 1 4 6 3 
7 3 0 2 5 1 6 4 
一共有92解法
Process finished with exit code 0