精华内容
下载资源
问答
  • 四皇后问题java
    2022-01-26 23:20:02

    思路分析: 把第一个皇后放到第一行第一列

            (1)把第二个皇后放到第二行第一列,进行判断,如果不行,放在第二列,进行判断,如果不行,放在 第三列,进行判断,一次把所有列进行尝试,直至找到合适位置

            (2)把第三个皇后放到第三行第一列,同步骤2

            (3)........

            (4)直至第8个皇后也能放到合适位置,此时第一个符合要求摆法便找到。

            (5)当得到一个正确解时,在栈回退到上一个栈时,就会开始回溯。把第一个皇后在第一行第一列的所 有解都找到

            (6)继续把第一个皇后放到第一行第二列,继续执行上述步骤

    结果表示:用一个数组来表示摆法,比如arr[8]={0,4,5,7,6,1,2,3},下标对应的是第几行, 数值对应的是第几列。

    arr[i]=j 第i+1个皇后,放在了第i+1行第j+1列

    代码实现:

    
    public class Queen {
        //定义一个max,表示一下共有多少个皇后,同理可求n个皇后
        int max = 8;
        //定义一个数组,报错皇后放置的位置
        int[] array = new int[max];
        //定义一个变量,保存共有多少中摆法
        static int count = 0;
    
        public static void main(String[] args) {
            Queen queen=new Queen();
            queen.queen8(0);
            System.out.println("共有"+count+"种摆法");
        }
        //放置n个皇后,递归
        private void queen8(int n) {
            //递归终止条件
            if (n == max) {//8个皇后放好了
                print();
                return;
            }
            //依次放入皇后,判断是否冲突
            for (int i = 0; i < max; i++) {
                //把当前这个皇后,放到该行的第1列
                array[n] = i;
                if (judge(n)) {
                    //如果不冲突,放下一个皇后
                    queen8(n + 1);
                }
                //如果冲突,放下一列
            }
        }
        private void print(){
            count++;
            for (int i = 0; i <array.length ; i++) {
                System.out.print(array[i]+" ");
            }
            System.out.println();
        }
        //判断是否冲突
        private boolean judge(int n) {
            //判断当前皇后与前面的n-1个是否冲突
            for (int i = 0; i < n; i++) {
                //任意两个皇后都不能处于同一行,同一列或者同一写线上
                //判断是否在同一行  没有必要n++
                //判断是否同一列 array[i]==array[n]
                //是否同一斜线 Math.abs(n-i)==Math.abs(array[n]-array[i]
                if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
                    return false;
                }
            }
            return true;
        }
    }
    
    

    更多相关内容
  • 4-皇后拼图4皇后问题的可视化 - 用JAVA实现四皇后问题包括将皇后放在一个 4 x 4 的棋盘上,以便没有两个皇后可以互相捕获。 也就是说,不允许将两个皇后放在同一行、同一列或同一对角线上。
  • Java四皇后问题(递归实现) 文章目录前言一、八皇后问题是什么?二、修改后的Java代码参考 前言 这里对《算法设计与分析》-王幸民 张晓霞-2018年版-人民邮电出版社 这本书中的P152的第6章 回溯算法 6.5 典型问题...

    Java的四皇后问题(递归实现)


    前言

    这里对《算法设计与分析》-王幸民 张晓霞-2018年版-人民邮电出版社 这本书中的P152的第6章 回溯算法 6.5 典型问题的C++程序中的2.n皇后问题(递归实现)的C++代码修改为Java,写文章记录。

    一、八皇后问题是什么?

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

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

    参考自:百度百科《八皇后问题》

    二、修改后的Java代码

    代码如下(示例):

    //@Author : NWJTMSZJSZ
    //@File : Queen.java
    //@Software : Eclipse
    
    public class Queen {
    	int n; // 皇后个数
    	int x[]; // 当前解
    	int sum; // 当前已找到的可行方案数
    
    	static int nQueen(int n) {
    		Queen X = new Queen();
    		X.n = n;
    		X.sum = 0;
    		int[] p = new int[n + 1];
    
    		for (int i = 0; i <= n; i++) {
    			p[i] = 0;
    		}
    
    		X.x = p;
    		X.Backtrack(1);
    		// delete []p;
    		// 在释放堆栈中c++基本数据(包括int,char.....结构体等)的存储空间时,不管是否是数组用delete都不会有错!而且能正常释放所有内存,不会导致内存泄露!
    		// 同时C语言中对象数组不能用delete,只能用delete[]。但是Java语言中就不需要释放数组的内存。
    		return X.sum;
    	}
    
    	void Backtrack(int t) {
    	// t拓展的是行
    		if (t > n) {
    			sum++;
    			for (int i = 1; i <= n; i++) {
    				System.out.print(x[i] + " ");
    			}
    			System.out.println();
    		} else {
    		    // 探索第t行的每一列是否有元素满足要求
    			for (int i = 1; i <= n; i++) {
    				x[t] = i;
    				if (Place(t)) {
    					Backtrack(t + 1);
    				}
    			}
    		}
    
    	}
    
    	boolean Place(int k) {
    		for (int j = 1; j < k; j++) {
    			if ((Math.abs(k - j) == Math.abs(x[j] - x[k])) || (x[j] == x[k])) {
    				return false;
    			}
    		}
    		return true;
    	}
    
    	public static void main(String[] args) {
    		int n = 4, m;
    		System.out.println(n + "皇后问题的解为:");
    		m = nQueen(n);
    		System.out.print(n + "皇后问题共有");
    		System.out.println(m + "个不同的解!");
    	}
    
    }
    

    参考

    《算法设计与分析》-王幸民 张晓霞-2018年版-人民邮电出版社 这本书中的P152的第6章 回溯算法 6.5 典型问题的C++程序中的2.n皇后问题(递归实现)的C++代码
    https://www.ptpress.com.cn/shopping/buy?bookId=96b526c3-bc61-472b-9677-09b6d4966386

    展开全文
  • 文章目录回溯算法基本思路代码格式四皇后问题判断该位置是否可存放皇后Q打印数组初始化数组回溯算法main测试测试结果 回溯算法 基本思路 回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题...

    回溯算法

    基本思路

    回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。

    代码格式

    private void backtrack("原始参数") {
        // 终止条件(递归必须要有终止条件)
        if ("终止条件") {
            // 一些逻辑操作(可有可无,视情况而定)
            return;
        }
    
        for (int i = "for循环开始的参数"; i < "for循环结束的参数"; i++) {
            //一些逻辑操作(可有可无,视情况而定)
    
            //做出选择
    
            //递归
            backtrack("新的参数");
            //一些逻辑操作(可有可无,视情况而定)
    
            //撤销操作
        }
    }
    

    四皇后问题

    其实最经典的是八皇后问题,但是分析起来比较麻烦,所以就通过四皇后来透析一些有关皇后问题,麻雀虽小,五脏俱全嘛。

    • 思路:
      1.指定一个位置
      2.指定第二个位置时,判断该位置是否可放,可放进行下一行,否则回到步骤1
      3.直到最后一行有可放位置

    在全局定义一个static int 类型的count变量用于记录有多少中不同的存放类型。

    判断该位置是否可存放皇后Q

       /**
         * 判断该位置是否可存放皇后
         * @param queen 数组
         * @param row 行
         * @param col 列
         * @return
         */
        private boolean isVaild(char[][] queen, int row, int col) {
    
            // 先判断上面是否有没有已经置Q的位置
            for(int i=row-1;i>=0;i--) { //此位置的上面,列不变向上找行
                if(queen[i][col]=='Q') {  //一旦发现
                    return false;  //此位置不能放
                }
            }
            // 在判断右上的位置是否有Q
            for(int i=row-1 ,j=col+1;i>=0 &&j<queen[0].length;i--,j++) { //此位置的右上方行要减1,列要加1
                if(queen[i][j]=='Q') {
                    return false;
                }
            }
            // 最后判断左上的位置是否有Q
            for(int i =row-1,j=col-1;i>=0&&j>=0;i--,j--) { //此位置的左上方行要减一列也要减一
                if(queen[i][j] =='Q') {
                    return false;
                }
            }
            // 如果都没找到,那么说明没有,此位置是可以存放的
            return true;
        }
    

    打印数组

     /**
         * 打印数组
         * @param queen
         */
        private void printQueen(char[][] queen) {
            for(int i = 0 ; i < queen.length ; i ++ ){
                for(int j = 0 ; j < queen.length ; j++){
                    System.out.print(queen[i][j]);
                }
                System.out.println();
            }
        }
    

    初始化数组

       /**
         * 初始化数组
         * @param queen
         */
        private void initializeQueen(char[][] queen) {
            for(int i = 0 ; i < queen.length ; i ++ ){
                for(int j = 0 ; j < queen.length ; j++){
                    queen[i][j]='A';
                }
            }
        }
    

    回溯算法

    
        /**
         * 求二维数组中皇后存放方法
         * @param queen 数组
         * @param row 行
         */
        public void queen(char[][] queen, int row) {
            // 结束条件:即当cow为数组的长度时结束
            if (row == queen.length) {
                count++;
              //自己写的一个公共方法,打印二维数组的,
               printQueen(queen);
              System.out.println();
              return;
            }
            for (int col = 0; col < queen.length; col++) {
               //验证当前位置是否可以放皇后
               if (isVaild(queen, row, col)) {
                   //如果在当前位置放一个皇后不冲突,就在当前位置放一个皇后
                   queen[row][col] = 'Q';
                   //递归,在下一行继续……
                   queen(queen, row + 1);
                   //撤销当前位置的皇后
                   queen[row][col] = 'A';
               }
            }
        }
       
    

    main测试

     /**
         * main方法测试
         * @param args
         */
        public static void main(String[] args) {
            char [][] chars = new char[4][4];
            Queen q = new Queen();
            q.initializeQueen(chars);
            q.queen(chars,0);
            System.out.println("总共有:"+count+"种不同的放置方法!");
        }
    }
    

    测试结果

    AQAA
    AAAQ
    QAAA
    AAQA
    
    AAQA
    QAAA
    AAAQ
    AQAA
    
    总共有:2种不同的放置方法!
    
    展开全文
  • public class FourQueen { /** * * n 皇后问题 * 在n×n格的国际象棋上摆放n个皇后,使其不能互相攻击, ... //四皇后问题:4*4放皇后 private static final int N = 4; private int[] x = new...
    public class FourQueen {
    	/**
    	 * 
    	 * n 皇后问题
    	 * 在n×n格的国际象棋上摆放n个皇后,使其不能互相攻击,
    	 * 即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
    	 *
    	 */
    	 //四皇后问题:4*4放四个皇后
    	private static final int N = 4;
    	private int[] x = new int[N];
    	
    	int sum = 0;
    //回溯查找	
    void backTack(int n) {
    
    		if(n == N) {
    			for (int i = 0; i < x.length; i++) {
    				System.out.print("x["+i+"] = " +x[i] + ",");
    			}
    			System.out.println();
    			sum ++;
    		}
    		else {
    			for (int i = 0; i < N; i++) {
    				x[n] = i;
    				if(isPlace(n)) {//如果第n行可以放,继续看n + 1行
    					backTack(n + 1);
    				}
    			}
    		}
    	}
    //在i行可否放置皇后  0<=i<=n
        private boolean isPlace(int i) {
    	
    	for (int j = 0; j < i; j++) {
    		if(Math.abs(i - j) == Math.abs(x[i] - x[j])  || x[i] == x[j])  {
    			return false;
    		}
    	}
    	return true;
    }
    
    	public static void main(String[] args) {
            FourQueen queen = new FourQueen();
    		
    		queen.backTack(0);
    		
    		System.out.println(queen.sum);
    
    	}
    
    }
    
    
    展开全文
  • 皇后问题java实现

    2018-03-22 20:04:14
    皇后java实现。八皇后问题是经典的回溯算法的应用,8x8的棋盘我们可以按行或者按列确定皇后的位置,比如我这边是按行安排皇后的位置,那么堆栈里存放的则是其所在列数。
  • 将 n 个皇后摆放在一个 n x n 的棋盘上,使得每一个皇后都无法攻击到其他皇后,N皇后问题是一个典型的约束求解问题,利用递归机制,可以很快的得到结果,本文将详细介绍,需要了解的朋友可以参考下
  • 主要介绍了java实现八皇后问题示例,八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出
  • n皇后问题java

    2021-09-23 22:02:37
    n皇后问题是一个典型的回溯算法的题目,就是在n*n的面板上,放n个皇后,每个皇后会攻击同一列和同一行还有两个斜边上的元素,问你放的方法,返回形式是一个List嵌套List,每个List里都是一种解决方案,每一个解决...
  • 主要介绍了如何基于java语言实现八皇后问题,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
  • 皇后问题,是一个古老而著名的问题,是回湖算法的典型案例。该问题是国际西洋棋棋手马克斯•贝瑟尔于 1848年提出:在8X8格的田际象棋上摆放八个皇后,使其不能互相攻击,即:任意两个皇后都不能处于同一行、 同一...
  • Java求解N皇后问题

    2022-05-04 09:56:20
    设计一种算法,打印 N 皇后在 N × N 棋盘上的各种摆法,...解释: 4 皇后问题存在如下两个不同的解法。 [ [“.Q…”, // 解法 1 “…Q”, “Q…”, “…Q.”], [“…Q.”, // 解法 2 “Q…”, “…Q”, “.Q…”] ] cl
  • 8皇后问题:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。递归,JAVA语言
  • n皇后问题java

    2013-11-21 22:23:50
    n皇后问题的没有同义的解。用java语言实现n-queens算法
  • Java解决八皇后问题

    千次阅读 2021-10-11 11:37:48
    视频链接:韩水平老师的Java数据结构与算法——8皇后问题 八皇、N皇后问题皇后问题介绍: 八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于 1848 年提出:...
  • 皇后问题java

    2015-02-06 10:06:55
    经典八皇后问题,结构简单,算法不是最优的
  • 首先把judge()写出来 ...//定义一个数组array保存皇后放置位置的结果,比如arr={0,4,7,5,2,6,1,3} 这种也很好理解,就是皇后在第一行的第一个位置,在第二行的第5个位置,第三行的第八个位置...... ..
  • 8皇后问题java版的图形界面演示,swing做的可运行jar文件。看了回朔算法,简洁的让人震撼,很有感触,就做了个图形演示界面。
  • 皇后问题JAVA程序
  • N皇后问题-java实现

    2017-02-17 00:18:33
    可以相比传统N皇后解决增加了运行速度,因为采用二进制进行皇后位置运算,其中图片位置以及图片请自行替换。
  • 皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即:任意两个皇后都不能处于同一行、同一列或...
  • 主要介绍了Java基于循环递归回溯实现八皇后问题算法,结合具体实例形式分析了java的遍历、递归、回溯等算法实现八皇后问题的具体步骤与相关操作技巧,需要的朋友可以参考下
  • JAVA N皇后问题 分支限界法 界面~
  • N皇后问题(n-queen problem)是一个经典的组合优化问题,也是一个使用回溯法(backtracking)的典型例子。回溯法是一种系统地搜索问题解的方法。 此文档包含算法分析、代码实现、演示程序、演示界面。
  • N皇后问题java

    千次阅读 2022-02-15 20:44:52
    n皇后问题是一个以国际象棋为背景的问题:在n×n的国际象棋棋盘上放置n个皇后,使得任何一个皇后都无法直接吃掉其他的皇后,即任意两个皇后都不能处于同一条横行、纵行或斜线上。 我们通过回溯的方法将所有可能的...
  • Java实现八皇后问题

    千次阅读 多人点赞 2022-03-12 21:08:47
    快速理解八皇后问题

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,686
精华内容 3,874
关键字:

四皇后问题java