回顾数据结构（Java版）——递归解决八皇后问题

清疚 2023-06-08 03:12 11阅读 0赞

> 八皇后是一道十分经典的数据结构与算法的题目，八皇后题目的核心思想就在一个8\*8的棋盘中，每行摆放一个皇后，并且每个皇后不能同行或者同列甚至斜着偷瞄一眼也不行，下来就使用递归来解决八皇后问题

使用递归来解决八皇后十分的简单，递归会不断的前进和回退，从而找出所有的解。  
实现步骤：

1.  使用一个数组`queen`来代表这个棋盘，为什么可以用一个一维数组来代表二维数组呢？很简单，因为每一行或者每一列只能放置一个皇后，因此皇后行或者列总会有一个值是固定的 ，比如`queen[0] = value`的含义就是第一个皇后的列数为`value`
2.  编写检测合法性的函数，我们假设按行放置，那么同列的还有同一斜线（可以根据判断斜率来判断是否在同一斜线）上的都不满足
3.  递归放置皇后，递归的终止条件就是如果放置的皇后放完了最后行（也就是正在放置等于MaxQueen的时候就保存棋盘，并且进行统计，如果这个终止条件不写或写错就有可能造成数组越界或者方法栈溢出），不是最后的元素的话，如果满足就进行递归，不满足就换下一个位置（程序的意思就是i++一次）

package com.wrial.recursion;
    /*
     * @Author  Wrial
     * @Date Created in 19:15 2019/10/15
     * @Description 递归实现八皇后 每个皇后不同行，不同列，不同一条对角线上
     */
    
    /*
    思路：可以根据列或者行来进行放皇后，比如我们可以控制每一行放一个，然后根据可选位置来放置后边的皇后
     */
    public class RecursionQueen {
        public static void main(String[] args) {
            RecursionQueen recursionQueen = new RecursionQueen();
            recursionQueen.place(0);
            System.out.println(count);
        }
    
        static int MaxQueen = 8;
        static int count;
        //采用的以为数组而不是二维数组来存取，含义是queen[i] = 第i+1个皇后的列数
        int[] queen = new int[MaxQueen];
    
        /*
        判断第n个和前面的冲不冲突，判断方法和上边的以为数组含义密切相关
        因为下标和对应的值分别代表的是行和列，因此行差如果等于列差就说明斜率，那就说明在一条线上
        */
        public boolean judge(int n) {
            for (int i = 0; i < n; i++) {
                if (queen[n] == queen[i] || Math.abs(n - i) == Math.abs(queen[n] - queen[i])) {
                    return false;
                }
            }
            return true;
        }
    
        public void record() {
            count++;
            for (int i : queen) {
                System.out.printf("%d\t", i);
            }
            System.out.println();
        }
    
        //置放皇后 从0开始放
        public void place(int begin) {
            //如果到8了，说明已经放好了，就打印记录
            if (begin == MaxQueen) {
                record();
                return;
            } else {
                for (int i = 0; i < MaxQueen; i++) {
                    queen[begin] = i;
                    if (judge(begin)) {
                        place(begin + 1);
                    }
                }
            }
        }
    }

运行结果92种方案，当然递归的缺陷也很大，因此它是一次次的前进和回溯试出来的，时间复杂度很高。但是不得不说递归思想也是很重要的。

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