八皇后问题

/ / 3350浏览

8皇后问题

1. 问题描述

​ 在一个8*8的棋盘上放置8个皇后，每行一个并使其不能互相攻击

2. 解决思路

​ 棋盘问题一般的解决方式可以使用回溯算法实现.

回溯算法也叫试探法, 它是一种系统地搜索问题的解的方法. 回溯算法的基本思想是: 从一条路往前走, 能进则进, 不能进则退回来, 换一条路再试.

最先想到的解决思路是构建一张二维棋盘数组, 以0填充当做空白棋盘, 以1当做皇后, 尝试向棋盘中填充. 依次判断该点的行列是否已经有皇后, 然后判断两个正负斜线是否有皇后, 不是特别的难, 重要的是一些边界的控制. 写完之后那个代码... 我自己的都不敢看. 今天无意中看到有个大佬发出的帖子, 解决思路非常独特, 记录一下.

3. 大牛的解决思路

使用一维数组构建棋盘, 数组中元素的值代表该列皇后所在的行数, 原本复杂的空间规模直接被压缩为 O(n), 对于列冲突一维数组一个位置只能放一个元素, 所以天然的排除了, 对于行冲突的判断就很简单了, 只要数组中的元素互不相等, 那么就不在一行里. 斜线的判断大佬使用的计算公式为: |row - i| = |col - arr[i]|, 其中 row 代表当前行号 col 代表当前循环的列, 含义就是: 如果两个皇后冲突, 那么 这两个皇后所在的行列相减的绝对值相等.

4. 以下为代码实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class TestQueen {

    //用于存放结果
    static List<int[]> res = new ArrayList<>();
    //定义最大递归层数
    static final int num = 8;
    //定义初始一维数组
    static int[] arr = new int[num];

    //八皇后测试
    public static void main(String[] args) {
        circle(0);
        for (int[] re : res) {
            System.out.println(Arrays.toString(re));
        }
        System.out.printf("共有%d种摆放方法", res.size());
    }

    //递归方法
    public static void circle(int n){
        if (n == num){  //达到最大递归层数时返回
            res.add(Arrays.copyOf(arr, num));
            return;
        }
        for (int i = 0; i < num; i ++){
            arr[n] = i;
            if (isConflict(n)){
                //如果当前列可以放置, 在下一列继续尝试
                circle(n + 1);
            }
        }
    }

    public static boolean isConflict(int n){
        for (int i = 0;i < n;i++) {
            //在同一行或者且行列相减的绝对值相等, 则不能放置
            if (arr[n] == arr[i] || Math.abs(n-i) == Math.abs(arr[n]-arr[i])){
                return false;
            }
        }
        return true;
    }
}

以上就即八皇后的全部解答.

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2021/07/07 02:09:30