11、数据结构和算法 - 实战:递归-八皇后问题

1.1 八皇后问题

在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问一共有多少种摆法。大数学家高斯认为一共有76种摆法,1854年在柏林的象棋杂志上不同的作者发表了共计40种不同的见解,后来还有人利用图论的方法得出共有92种摆法。

 

如何解决八皇后问题?

使用递归回溯法,这种方法从棋盘的第一行开始尝试摆放第一个皇后,摆放成功后,递归一层,再遵循规则在棋盘第二行来摆放第二个皇后。如果当前位置无法摆放,则向右移动一格再次尝试,如果摆放成功,则继续递归一层,摆放第三个皇后…

1.2 JAVA实现摆放方式

回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。

package com.yuanxw.datastructure.chapter11;

/**
 * 8皇后问题
 * 解:8皇后问题回溯方式
 */
public class Queen8Example {
   
     
    // 最大步骤
    private static int MAX_QUEEN = 8;
    private static int playCount = 0;
    private static int validCount = 0;

    /**
     * 棋局
     * 下标(index)表示行
     * 值(value)表示列
     */
    private int chessGame[] = new int[MAX_QUEEN];

    public static void main(String[] args) {
   
     
        Queen8Example queen = new Queen8Example();
        queen.play(0);
        System.out.println(String.format("摆放8皇后游戏位置共【%s】种解法", playCount));
        System.out.println(String.format("摆放8皇后游戏需要验证是否已经皇后冲突存在【%s】次", validCount));

    }
    /**
     * 开始游戏
     */
    public void play(int n) {
   
     
        // 先退出条件:如果是最大的皇后,说明运行结束。
        if (n == MAX_QUEEN) {
   
     
            print();
            playCount++;
            return;
        }

        for (int i = 0; i < MAX_QUEEN; i++) {
   
     
            // 把当前皇后n,放该行的第i列
            chessGame[n] = i;
            // 如果当前符合皇后的摆放规则,接着摆放下一行。
            if (isValid(n)) {
   
     
                // 递归摆放下一个皇后
                play(n + 1);
            }
        }
    }
    /**
     * 判断当前皇后所在的位置是否符合规则
     * 判断说明
       1.判断是否是在同一列:chessGame[i] == chessGame[n]
       2.公式:Math.abs(n - i) == Math.abs(chessGame[n] - chessGame[i])
        x,y[y-x](x-y)
        0,0[0](0)		0,1[1](-1)		0,2[2](-2)		0,3[3](-3)		0,4[4](-4)		0,5[5](-5)		0,6[6](-6)		0,7[7](-7)
        1,0[-1](1)		1,1[0](0)		1,2[1](-1)		1,3[2](-2)		1,4[3](-3)		1,5[4](-4)		1,6[5](-5)		1,7[6](-6)
        2,0[-2](2)		2,1[-1](1)		2,2[0](0)		2,3[1](-1)		2,4[2](-2)		2,5[3](-3)		2,6[4](-4)		2,7[5](-5)
        3,0[-3](3)		3,1[-2](2)		3,2[-1](1)		3,3[0](0)		3,4[1](-1)		3,5[2](-2)		3,6[3](-3)		3,7[4](-4)
        4,0[-4](4)		4,1[-3](3)		4,2[-2](2)		4,3[-1](1)		4,4[0](0)		4,5[1](-1)		4,6[2](-2)		4,7[3](-3)
        5,0[-5](5)		5,1[-4](4)		5,2[-3](3)		5,3[-2](2)		5,4[-1](1)		5,5[0](0)		5,6[1](-1)		5,7[2](-2)
        6,0[-6](6)		6,1[-5](5)		6,2[-4](4)		6,3[-3](3)		6,4[-2](2)		6,5[-1](1)		6,6[0](0)		6,7[1](-1)
        7,0[-7](7)		7,1[-6](6)		7,2[-5](5)		7,3[-4](4)		7,4[-3](3)		7,5[-2](2)		7,6[-1](1)		7,7[0](0)
     * @param n
     * @return
     */
    public boolean isValid(int n) {
   
     
        validCount ++;
        for (int i = 0; i < n; i++) {
   
     
            if (chessGame[i] == chessGame[n] || Math.abs(n - i) == Math.abs(chessGame[n] - chessGame[i])) {
   
     
                return false;
            }
        }
        return true;
    }

    /**
     * 打印8皇后问题结果
     */
    private void print() {
   
     
        for (int i : chessGame) {
   
     
            System.out.print((i + 1) + "\t");
        }
        System.out.println("");
    }
}

执行结果:

1	5	8	6	3	7	2	4	
1	6	8	3	7	4	2	5	
1	7	4	6	8	2	5	3	
1	7	5	8	2	4	6	3	
2	4	6	8	3	1	7	5	
2	5	7	1	3	8	6	4	
2	5	7	4	1	8	6	3	
2	6	1	7	4	8	3	5	
2	6	8	3	1	4	7	5	
2	7	3	6	8	5	1	4	
2	7	5	8	1	4	6	3	
2	8	6	1	3	5	7	4	
3	1	7	5	8	2	4	6	
3	5	2	8	1	7	4	6	
3	5	2	8	6	4	7	1	
3	5	7	1	4	2	8	6	
3	5	8	4	1	7	2	6	
3	6	2	5	8	1	7	4	
3	6	2	7	1	4	8	5	
3	6	2	7	5	1	8	4	
3	6	4	1	8	5	7	2	
3	6	4	2	8	5	7	1	
3	6	8	1	4	7	5	2	
3	6	8	1	5	7	2	4	
3	6	8	2	4	1	7	5	
3	7	2	8	5	1	4	6	
3	7	2	8	6	4	1	5	
3	8	4	7	1	6	2	5	
4	1	5	8	2	7	3	6	
4	1	5	8	6	3	7	2	
4	2	5	8	6	1	3	7	
4	2	7	3	6	8	1	5	
4	2	7	3	6	8	5	1	
4	2	7	5	1	8	6	3	
4	2	8	5	7	1	3	6	
4	2	8	6	1	3	5	7	
4	6	1	5	2	8	3	7	
4	6	8	2	7	1	3	5	
4	6	8	3	1	7	5	2	
4	7	1	8	5	2	6	3	
4	7	3	8	2	5	1	6	
4	7	5	2	6	1	3	8	
4	7	5	3	1	6	8	2	
4	8	1	3	6	2	7	5	
4	8	1	5	7	2	6	3	
4	8	5	3	1	7	2	6	
5	1	4	6	8	2	7	3	
5	1	8	4	2	7	3	6	
5	1	8	6	3	7	2	4	
5	2	4	6	8	3	1	7	
5	2	4	7	3	8	6	1	
5	2	6	1	7	4	8	3	
5	2	8	1	4	7	3	6	
5	3	1	6	8	2	4	7	
5	3	1	7	2	8	6	4	
5	3	8	4	7	1	6	2	
5	7	1	3	8	6	4	2	
5	7	1	4	2	8	6	3	
5	7	2	4	8	1	3	6	
5	7	2	6	3	1	4	8	
5	7	2	6	3	1	8	4	
5	7	4	1	3	8	6	2	
5	8	4	1	3	6	2	7	
5	8	4	1	7	2	6	3	
6	1	5	2	8	3	7	4	
6	2	7	1	3	5	8	4	
6	2	7	1	4	8	5	3	
6	3	1	7	5	8	2	4	
6	3	1	8	4	2	7	5	
6	3	1	8	5	2	4	7	
6	3	5	7	1	4	2	8	
6	3	5	8	1	4	2	7	
6	3	7	2	4	8	1	5	
6	3	7	2	8	5	1	4	
6	3	7	4	1	8	2	5	
6	4	1	5	8	2	7	3	
6	4	2	8	5	7	1	3	
6	4	7	1	3	5	2	8	
6	4	7	1	8	2	5	3	
6	8	2	4	1	7	5	3	
7	1	3	8	6	4	2	5	
7	2	4	1	8	5	3	6	
7	2	6	3	1	4	8	5	
7	3	1	6	8	5	2	4	
7	3	8	2	5	1	6	4	
7	4	2	5	8	1	3	6	
7	4	2	8	6	1	3	5	
7	5	3	1	6	8	2	4	
8	2	4	1	7	5	3	6	
8	2	5	3	1	7	4	6	
8	3	1	6	2	5	7	4	
8	4	1	3	6	2	7	5	
摆放8皇后游戏位置共【92】种解法
摆放8皇后游戏需要验证是否已经皇后冲突存在【15720】次