精华内容
下载资源
问答
  • java解决八皇后问题
    2021-11-24 23:19:42

    用Java解决八皇后问题

    问题表述为:在8×8格的国际象棋上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果
    思路分析:
    三个方法:
    check()递归调用求解
    judge()判断放的位置是否合理,与之前的是否冲突
    show()用于打印结果
    个人的见解,如有错误或者更好的,望不吝赐教!

    public class Queue8 {
        int[] arr=new int[8];//存储8个皇后
        static int count=0;//正解的个数
        public static void main(String[] args){
        Queue8 queue8=new Queue8();
        queue8.check(0);
        System.out.println("一共有"+count+"种解法");
    
        }
        private void check(int n){//递归求解
            if(n==8){//跳出递归的条件
                show();
                return;
            }
            for(int i=0;i<8;i++){
                arr[n]=i;
                if(judge(n)){
                    check(n+1);
                }
            }
        }
        private boolean judge(int n){
            for(int i=0;i<n;i++){
                if(arr[i] == arr[n] || Math.abs(n-i) == Math.abs(arr[n] - arr[i]) ) {//看成一个等腰三角形,判断两边是否长度大小相等
                    return false;
                }
            }
            return true;
        }
        private void show(){
            count++;
            for(int i=0;i<8;i++){
                System.out.print(arr[i]+" ");
            }
            System.out.println();
        }
    }
    
    
    更多相关内容
  • Java解决八皇后问题

    2022-04-26 10:51:39
    Java解决八皇后

    Java解决八皇后问题

    八皇后问题(英文:Eight queens),是由国际象棋棋手马克斯·贝瑟尔于1848年提出的问题,是回溯算法的典型案例。

    问题表述为:在8×8格的国际象棋上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转,和对角线对称变换的摆法看成一类,共有42类。计算机发明后,有多种计算机语言可以编程解决此问题。
    1

    8皇后之间需满足:

    1.不在同一行上

    2.不在同一列上

    3.不在同一斜线上

    回溯算法思路

    八皇后问题如果用穷举法需要尝试88=16,777,216种情况。每一列放一个皇后,可以放在第 1 行,第 2 行,……,直到第8行。穷举的时候从所有皇后都放在第1行的方案开始,检验皇后之间是否会相互攻击。如果会,把列H的皇后挪一格,验证下一个方案。移到底了就“进位”到列G的皇后挪一格,列H的皇后重新试过全部的8行。这种方法是非常低效率的,因为它并不是哪里有冲突就调整哪里,而是盲目地按既定顺序枚举所有的可能方案。

    回溯算法优于穷举法。将列A的皇后放在第一行以后,列B的皇后放在第一行已经发生冲突。这时候不必继续放列C的皇后,而是调整列B的皇后到第二行,继续冲突放第三行,不冲突了才开始进入列C。如此可依次放下列A至E的皇后,如图2所示。将每个皇后往右边横向、斜向攻击的点位用叉标记,发现列F的皇后无处安身。这时回溯到列E的皇后,将其位置由第4行调整为第8行,进入列F,发现皇后依然无处安身,再次回溯列E。此时列E已经枚举完所有情况,回溯至列D,将其由第2行移至第7行,再进入列E继续。按此算法流程最终找到如图3所示的解,成功在棋盘里放下了8个“和平共处”的皇后。继续找完全部的解共92个。

    回溯算法求解八皇后问题的原则是:有冲突解决冲突,没有冲突往前走,无路可走往回退,走到最后是答案。为了加快有无冲突的判断速度,可以给每行和两个方向的每条对角线是否有皇后占据建立标志数组。放下一个新皇后做标志,回溯时挪动一个旧皇后清除标志。

    代码如下:

     public static class TestQueen {
    
            // 皇后/棋盘的个数
            private static final int QUEEN_NUM = 8;
    
            // 首先定义一个8 * 8 的棋盘
            private static final int[][] Checkerboard = new int[QUEEN_NUM][QUEEN_NUM];
    
            // 定义一共有多少种放置皇后的算法
            private static int COUNT = 0;
    
            /**
             * 打印棋盘
             */
            public static final void show() {
                System.out.println("第" + (++COUNT) + "次摆法");
                for (int i = 0; i < QUEEN_NUM; i++) {
                    for (int j = 0; j < QUEEN_NUM; j++) {
                        System.out.print(Checkerboard[i][j] + " ");
                    }
                    System.out.println("");
                }
            }
    
    
            public static final boolean check(int row, int col) {
    
                // 判断当前位置的上面是否有皇后
                for (int i = row - 1; i >= 0; i--) {
                    if (Checkerboard[i][col] == 1)
                        return false;
                }
    
                // 判断左上是否有皇后
                for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
                    if (Checkerboard[i][j] == 1)
                        return false;
                }
    
                // 判断右上是否有皇后
                for (int i = row - 1, j = col + 1; i >= 0 && j < QUEEN_NUM; i--, j++) {
                    if (Checkerboard[i][j] == 1)
                        return false;
                }
    
                return true;
            }
    
            /**
             * 从第n行放置皇后
             *
             * @param row
             */
            public static final void play(int row) {
                // 遍历当前行的所有单元格 以列为单元
                for (int i = 0; i < QUEEN_NUM; i++) {
                    // 是否能够放置皇后
                    if (check(row, i)) {
                        Checkerboard[row][i] = 1;
    
                        if (row == QUEEN_NUM - 1) {
                            // 最后行 放置完毕 打印皇后
                            show();
                        } else {
                            // 放置下一行
                            play(row + 1);
                        }
    
                        //回退到当前步骤,把皇后设置为0
                        Checkerboard[row][i] = 0;
                    }
    
                }
            }
    
            public static void main(String[] args) {
                play(0);
            }
        }
    

    运行结果

    2

    展开全文
  • 利用Java解决八皇后问题 概述 八皇后问题,一个古老而著名的问题,是回溯法的典型案例。八皇后问题是在8x8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处在同一行、同一列或同一斜线上,问...

    利用Java解决八皇后问题

    概述

    八皇后问题,一个古老而著名的问题,是回溯法的典型案例。八皇后问题是在8x8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处在同一行、同一列或同一斜线上,问满足这样的要求有多少种摆法。经过计算解出92种结果。

    思路

    在这里插入图片描述

    如图所示的八皇后放置就可以满足题目中的要求,每一个皇后的同一行、用一列和同一斜线上都没有其它皇后。根据摆放的要求,可以假设当放置第一个皇后,可以在它所在的行、列和斜线上进行标记,说明该行、列和斜线已经被该皇后所占领,其它皇后不能被占有,下一个皇后只能处在第一个皇后不被占用的位置,以此类推。

    分析

    在这里插入图片描述

    • 由图可看出,可以把上对角线的斜线分为15组,每一条斜线上的位置i-j所得的值都是一样的,每一条斜线都可以代表一个皇后所占领的位置,由于i-j的值有出现负数,可以把i-j所得的值再加上7,可得如下图

    在这里插入图片描述

    • 这时可以用一个flag1[15]数组去标记这些斜线上的位置是否被皇后所占领。

    在这里插入图片描述

    • 同理,也可以把下对角线的斜线分为15组,每一条斜线上的位置i+j所得的值都是一样的,故用另外一个flag2[15]数组去标记这些斜线上的位置是否被皇后所占领。
    • 对于行和列的情况,可以用一个column[8]数组去标记皇后所对应的列是否被占领,因为每一行只能放置一个皇后,所有就不用对行进行标记是否被占领。
    • 当摆放到第八个皇后时,说明已经摆放好这八个皇后的放置情况了,然后通过回溯继续找到另外一种的摆放的结果,直到没有其它摆放结果为止。

    实现过程

    全局变量

    private static int[] queen = new int[8]; //八皇后的结果
    private static boolean[] column = new boolean[8];    //列
    private static boolean[] upperDiagonal = new boolean[15]; //上对角线
    private static boolean[] lowerDiagonal = new boolean[15]; //下对角线
    private static int count = 0;   //记录结果数量
    

    核心代码

    public static void eightQueens(int i){
        if (i>7){
            //当放置完第8个皇后输出打印八个皇后放置情况
            print();
        }else{
            for (int col = 0; col < 8; col++) {
                //如果该所对应的列和斜线上没有被其它皇后标记占领
                if (!column[col] && !upperDiagonal[i-col+7] && !lowerDiagonal[i+col]){
                    queen[i] = col;     //将第i个皇后放置的列位置存放到数组中
                    column[col] = true;     //标记该皇后所在的列被占领
                    //标记该皇后所在的斜线被占领
                    upperDiagonal[i-col+7] = true;
                    lowerDiagonal[i+col] = true;
                    eightQueens(i+1);   //递归放置下一个皇后
                    //回溯
                    column[col] = false;
                    upperDiagonal[i-col+7] = false;
                    lowerDiagonal[i+col] = false;
                }
            }
        }
    }
    

    打印输出八个皇后放置情况

    private static void print() {
        count++;
        System.out.println("NO:"+count);
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (queen[i]==j){
                    //1代表该位置放置的皇后
                    System.out.print("1  ");
                }else {
                    //0代表该位置不放置
                    System.out.print("0  ");
                }
            }
            System.out.println();
        }
    }
    

    主函数

    public static void main(String[] args) {
        eightQueens(0);
    }
    

    输出结果(部分)

    在这里插入图片描述

    最后一共输出了92种八个皇后的放置情况,得出八个皇后问题的结果。

    展开全文
  • java解决八皇后问题

    2019-09-30 10:01:40
    八皇后问题 八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上...

    八皇后问题

    八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。

    约定: 采用一维数组来存储8x8的棋盘第i个元素代表第i行 元素的值为第几列

    思路:

    • 先放置第一行第一列 再放第二行第二列如果不行就放下一列 以此类推放置 完第8个皇后
    • 如果该列不能放置则下列
    • 如果找到第8个皇后则回溯到7个皇后继续重新放置第7个皇后
    
    public class Queen8Quesion {
    
    
        private  final int max=8;
        private int[] checkerBoard=new int[max];
        private static int rsCount=0;
        private static int count=0;
        public static void main(String[] args) {
            //通过递归回溯来解决八皇后的问题 八个皇后两两不能在同一行同一列同一斜线上
            //思路: 先放置第一行第一列 再放第二行第二列如果不行就放下一列 以此类推放置完第8个皇后
            //如果该列不能放置则下列
            //如果找到第8个皇后则回溯到7个皇后继续重新放置第8个皇后
            //约定:采用一维数组来存储8x8的棋盘第i个元素代表第i行 元素的值为第几列
            Queen8Quesion queen8Quesion = new Queen8Quesion();
            queen8Quesion.playChess(0);
    
    
            System.out.println("判断了 %d 次!"+count);
            System.out.println("结果有 %d 种"+rsCount);
        }
    
    
        public void playChess(int n){
            //递归的出口为已经放置完了8个皇后
            if(n==max){
                showResult();
                return;//结束本次方法 返回到上一个皇后继续摆放
            }else{
                //遍历列
                for (int i = 0; i < max; i++) {
                    checkerBoard[n]=i;
                    //下完之后判断位置是否合法
                    if(judge(n)){
                        //如果不冲突就摆放下一个皇后
                        playChess(n+1);
                    }
                    //如果冲突会执行下一次i++ 放置下一列 体现了回溯
                    //那何为回溯 当递归方法执行完毕后 会继续会到该方法继续执行 比如当n=0时表示放值第1行第一个皇后
                    //开始进入循环放入第一列 判断是否冲突 发现不冲突 就递归执行下一行第二个皇后从第一列开始放置 依次类推
                    //如果冲突就放置下一列 如果8个皇后放置完毕就回溯到第7个皇后继续摆放
                    //结合虚拟机栈思路会更加清晰
                }
            }
        }
        //判断位置是否合法 即位置是否可以放置
        //判断第n个已经放置的皇后是否会冲突
        public boolean judge(int n){
            count++;
            for (int i = 0; i < n; i++) {
                //如果在同一列说明冲突
                // 如果在同一斜线说明冲突 在统一斜线说明斜率相等也就是 y=x,y为行距,x列距
                if(checkerBoard[i]==checkerBoard[n]||Math.abs(n-i)==Math.abs(checkerBoard[n]-checkerBoard[i])){
                    return false;
                }
            }
            return true;
        }
    
        //打印8个皇后摆放的结果
        public void showResult(){
            rsCount++;
            for (int i : checkerBoard) {
                System.out.print(i+" ");
            }
            System.out.println();
        }
    }
    
    

    执行结果

    结果

    • 何为回溯 当递归方法执行完毕后 会继续会到该方法继续执行 比如当n=0时表示放值第1行第一个皇后
    • 开始进入循环放入第一列 判断是否冲突 发现不冲突 就递归执行下一行第二个皇后从第一列开始放置 依次类推
    • 如果冲突就放置下一列 如果8个皇后放置完毕就回溯到第7个皇后继续摆放
    • 结合虚拟机栈思路会更加清晰
    展开全文
  • Java解决八皇后问题,java解决皇后,Java八皇后[JavaJava八皇后[Java]代码package queen;import java.awt.*;import java.awt.event.*;@SuppressWarnings("serial")class equeen extends Frame implements ...
  • Java利用回溯法结合递归操作解决八皇后问题;利用WindowBuilder的GUI,动态展示该问题背景下回溯法的搜索路径[含详细解析]
  • Java解决八皇后问题(回溯法) 啥也不说了,直接看代码吧,代码里面有详解 public class huanghou8 { //定义max个皇后 int max=8; //定义数组array,数组得下标表示第几个皇后,值表示列 int[] array = new int...
  • 采用遗传算法解决八皇后问题,包含以下遗传算法步骤: 选择方式:轮盘赌,繁殖池,竞技选择 交叉方式:顺序交叉,部分匹配交叉 变异方式:交换变异,插入变异,倒序变异 变异概率可选择
  • 主要介绍了java实现八皇后问题示例,八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出
  • 详解八皇后问题(java解决方法)

    万次阅读 多人点赞 2018-11-01 22:36:24
    最近在上java课遇到了一个八皇后的问题,在博客上搜索八皇后问题发现java版的代码很少,同时解释的也很少,这里将详细解释思路与代码,核心思路为迭代,本文章是给新手看的,大佬可以直接跳过,新手看不懂的话算我输...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,444
精华内容 977
关键字:

java解决八皇后问题