递归-八皇后问题（回溯算法）

心已赠人 2022-11-07 04:16 238阅读 0赞

一：八皇后问题

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848 年提出：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法(92)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70][]

算法思路：

1.  第一个皇后先放第一行第一列。
2.  第二个皇后放在第二行第一列、然后判断是否 OK， 如果不 OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适。
3.  继续第三个皇后，还是第一列、第二列……直到第 8 个皇后也能放在一个不冲突的位置，算是找到了一个正确解。
4.  当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到。
5.  然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4 的步骤。

说明：

理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题 . arr\[8\] = \{0 , 4, 7, 5, 2, 6, 1, 3\} //对应  arr  下标 表示第几行，即第几个皇后， arr\[i\] = val , val  表示第  i+1  个皇后，放在第  i+1 行的第 val+1  列。

Queue8实体类

package com.recursion;
    
    /**
     * @author lizhangyu
     * @date 2021/3/10 22:42
     */
    public class Queue8 {
    
        private int max = 8;
        private int[] arr = new int[max];
        private static int judgeCount = 0;
        private static int count = 0;
    
        public static void main(String[] args) {
            Queue8 queue8 = new Queue8();
            queue8.check(0);
            System.out.printf("一共有%d 解法\n", count);
            System.out.printf("一共判断冲突的次数%d 次", judgeCount);
        }
    
        public void check(int n) {
            //结束的条件
            if (n == 8) {
                print();
                return;
            }
            for (int i = 0; i < max; i++) {
                //先把当前这个皇后n，放到该行的第一列
                arr[n] = i;
                if (judge(n)) {
                    check(n+1);
                }
            }
    
        }
    
        public boolean judge(int n) {
            judgeCount++;
            for (int i = 0; i < n; i++) {
                //判断是否在同一列或者同一斜线上
                if (arr[i] == arr[n] || Math.abs(i-n) == Math.abs(arr[i]-arr[n])) {
                    return false;
                }
            }
            return true;
        }
    
        public void print() {
            count++;
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[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 解法
    一共判断冲突的次数15720 次

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70]: /images/20221023/3240d91298324ecaa235f2cb77f39259.png