当前位置:   article > 正文

回溯法轻松高效率解决n皇后问题(java实现)_java利用回溯法,求解n后问题,要求设计出相应算法,并分析其时间复杂度

java利用回溯法,求解n后问题,要求设计出相应算法,并分析其时间复杂度

问题描述:
如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。(皇后,是国际象棋中的棋子,意味着国王的妻子。皇后只做一件事,那就是“吃子”。当她遇见可以吃的棋子时,就迅速冲上去吃掉棋子。当然,她横、竖、斜都可走步,可进可退)

解决该回溯问题,实际上就是一个决策树的遍历过程
算法思路:
第一个皇后理论上可以选择棋盘上任何一个落点,依次尝试第一个皇后的可能落点,对于第一个皇后每一个可能的落点寻找第二个合法的落点,再对于第二个皇后每一个可能的落点寻找第三个合法的落点…以此类推,当n个皇后全部落定后,记录此时的结果再进行下一次循环…

例如以4皇后为例的决策树如下:
在这里插入图片描述

当然,上述回溯法是通用的,其复杂度是指数级的,显然不太合理,需要剪枝进行优化。
接下来,可以针对该问题继续研究,将棋盘化作一个二维数组,数组中0代表空位,1代表皇后,分析问题可以发现:
1.最后成立的结果中一定是每行有且仅有一个皇后
2.放置第x(x<n)个皇后时,棋盘中其后面没有皇后,故只需判断当前落点的左上、右上、上这三个方向上时候有皇后来决定是否落子

没有剪枝时,程序运行8皇后耗时达到1200ms,通过以上结论剪枝后耗时<5ms,整整240倍的时间差!

public class Solution {
	//存储结果
    public static List<List<String>> list = new ArrayList<>();

    public static void main(String args[]) {
        solveNQueens(8);
    }
    public static List<List<String>> solveNQueens(int n) {
        long t1 = System.currentTimeMillis();
        int a[][] = new int[n][n];
        solve(a, n, 0);
        long t2 = System.currentTimeMillis();
        System.out.println("耗时 " + (t2 - t1) + " ms");
        return list;
    }
    public static void solve(int a[][], int n, int num) {
        for (int j = 0; j < n; j++) {
            if (a[num][j] == 0&&ifDown(a,num,j,n)) {//判断是否可以落点
                a[num][j] = 1;//落子
                if (num >= n - 1) {//判断是否是符合要求的结果
                    addList(a);//记录符合要求的结果
                    a[num][j] = 0;//恢复棋盘
                    return;
                } else solve(a, n, num + 1);//递归,落下一个皇后
                a[num][j] = 0;//恢复棋盘
            }
        }
    }
    public static void addList(int a[][]) {
        List<String> li = new ArrayList<>();
        for (int i = 0; i < a.length; i++) {
            StringBuilder str = new StringBuilder();
            for (int j = 0; j < a.length; j++) {
                if (a[i][j] == 0) str.append('.');
                else if (a[i][j] == 1) str.append('Q');
            }
            li.add(str.toString());
        }
        list.add(li);
    }
	//判断某点是否可以落子
    public static boolean ifDown(int a[][], int x,int y, int n) {
        //上
        for (int i = x; i >= 0; i--) {
            if (a[i][y] != 0) return false;
        }
        //左上
        for (int i = x, j = y; i >= 0 && j >= 0; i--, j--) {
            if (a[i][j] != 0) return false;
        }
		//右上
        for (int i = x, j = y; i >= 0 && j < n; i--, j++) {
            if (a[i][j] != 0) return false;
        }
        return true;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57

回溯算法原理简单明了,就是一种暴力穷举,其本身的复杂度是很高的,必须通过剪枝来优化该算法,否则效率会大打折扣。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/笔触狂放9/article/detail/633294
推荐阅读
相关标签
  

闽ICP备14008679号