精华内容
下载资源
问答
  • 回溯算法n皇后问题java
    千次阅读
    2020-06-07 11:24:26

    n 皇后问题

    问题分析

    • 在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后,任何2个皇后不放在同一行或同一列或同一斜线上。

    • x[i] 表示皇后i 放在棋盘的第i 行的第x[i] 列

      • 不能在同一行
      • 不能在同一列 x[i] 互不相同
      • 不能在同一斜线
        • 斜率为1 和值相等
        • 斜率为-1 差值相等
        • 若两个点 (i, j) (k, l), 则有
          • i - j = k - l => i - k = j - l
          • i + j = k + l => i - k = l -j
        • 即 |i - k| = |j - l| 成立即可

    Java 源代码

    /*
     * 若尘
     */
    package nqueen;
    
    /**
     * n 皇后问题
     * @author ruochen
     * @version 1.0
     */
    public class NQueen {
    
    	/** 皇后个数  */
    	static int n;
    	/** 当前解 */
    	static int[] x;
    	/** 当钱已找到的可行方案数 */
    	static long sum;
    	
    	public static void main(String[] args) {
    		nQueen(5);
    		System.out.println("可行方案个数为: " + sum);
    	}
    	
    	/**
    	 * 初始化及返回可行解个数
    	 * @return 可行解个数
    	 */
    	public static long nQueen(int nn) {
    		n = nn;
    		sum = 0;
    		x = new int[n + 1];
    		for (int i = 0; i <= n; i++) {
    			// 初始化
    			x[i] = 0;
    		}
    		backTrack(1);
    		return sum;
    	}
    	
    	/**
    	 * 可行性约束
    	 * @param k
    	 * @return 是否可行
    	 */
    	public static boolean place(int k) {
    		
    		for (int j = 1; j < k; j++) {
    			// 对应公式 |i - k| = |j - l| && 列号不能相同 
    			if ((Math.abs(k - j) == Math.abs(x[j] - x[k])) || x[j] == x[k]) return false;
    		}
    		return true;
    	}
    	
    	/**
    	 * 回溯搜索
    	 * @param i
    	 */
    	public static void backTrack(int t) {
    		if (t > n) {
    			// 已经找到一种可行解
    			long temp = sum + 1;
    			System.out.print("第" + temp + "种可行解为: ");
    			for (int k = 1; k <= n; k++) {
    				System.out.print(x[k] + " ");
    			}
    			System.out.println();
    			sum++;
    		} else {
    			for (int i = 1; i <= n; i++) {
    				x[t] = i;
    				if (place(t)) backTrack(t + 1);
    			}
    		}
    	}
    }
    
    
    第1种可行解为: 1 3 5 2 4 
    第2种可行解为: 1 4 2 5 3 
    第3种可行解为: 2 4 1 3 5 
    第4种可行解为: 2 5 3 1 4 
    第5种可行解为: 3 1 4 2 5 
    第6种可行解为: 3 5 2 4 1 
    第7种可行解为: 4 1 3 5 2 
    第8种可行解为: 4 2 5 3 1 
    第9种可行解为: 5 2 4 1 3 
    第10种可行解为: 5 3 1 4 2 
    可行方案个数为: 10
    
    更多相关内容
  • 问题描述 在一个N*N的棋盘上放置N皇后,每行一个并使其不能互相攻击(同一...// n 皇后问题 public class queen { public static List<List<Integer>> ResList=new ArrayList<>(); //结果列表 p

    问题描述

    在一个N*N的棋盘上放置N个皇后,每行一个并使其不能互相攻击(同一行、同一列、同一斜线上的皇后都会自动攻击),问一共有多少种放法?

    代码

    import java.util.ArrayList;
    import java.util.List;
    
    // n 皇后问题
    public class queen {
    
        public static List<List<Integer>> ResList=new ArrayList<>();    //结果列表
        public static int num=8;                                        //皇后个数
    
        public static void main(String[] args) {
            List<Integer> list=new ArrayList<>();   //已选好的路径
            backtrack(0,list);    //从第一行开始放起
            for(List<Integer> l:ResList)
                System.out.println(l);
            System.out.println("一共有"+ResList.size()+"种答案");
        }
    
        private static void backtrack(int n, List<Integer> list) {    // n表示当前行数
                if(list.size()==num){
                    ResList.add(new ArrayList<>(list));
                    return ;
                }
                for(int i=0;i<num;i++){     //每行从第一列开始试探放皇后
                    if(!judge(i,n,list))
                        continue;
                    list.add(i);
                    backtrack(n+1,list);   //放置下一行
                    list.remove(list.size()-1);  //返回寻找新的路线
                }
        }
    
        private static boolean judge(int i, int n, List<Integer> list) {    // i表示当前第n行的列坐标
            for(int j=0;j<n;j++){                                           //判断是否和前面的蜘蛛在同一列,或者同一斜线上
                if(list.get(j)==i || Math.abs(n-j)==Math.abs(i-list.get(j)))
                    return false;
            }
            return true;
        }
    }
    
    

    运行结果

    展开全文
  • 回溯算法 - Java实现N皇后问题

    回溯算法 - Java实现N皇后问题

    1.回溯算法

    1.1 回溯算法的介绍

    • 回溯算法实际上一个类似枚举的深度优先搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回(也就是递归返回),尝试别的路径

    • 回溯的处理思想,有点类似枚举(列出所有的情况)搜索。我们枚举所有的解,找到满足期望的解。为了有规律地枚举所有可能的解,避免遗漏和重复,我们把问题求解的过程分为多个阶段。每个阶段,我们都会面对一个岔路口,我们先随意选一条路走,当发现这条路走不通的时候(不符合期望的解),就回退到上一个岔路口,另选一种走法继续走

    1.2 N皇后问题的介绍

    • n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击
      在这里插入图片描述

    2.Java实现N皇后问题

    package com.lagou.backMethod;
    
    /**
     * @author 云梦归遥
     * @date 2022/5/22 9:49
     * @description 回溯算法 - N皇后问题
     */
    public class NQueens {
        /**
         * @param n     表示n * n 的格子
         * @param row   当前是多少行
         * @param res   用一个数组,记录每一行的皇后所在的列
         * @param count 结果总数
         * @return
         */
        public int nQueen(int n, int row, int[] res, int count) {
            if (row == n) {
                //打印
                print(n, res);
                count++;
                System.out.println("-----------");
                return count;
            }
            for (int col = 0; col < n; col++) {
                //先尝试着把皇后放在这一列
                res[row] = col;
                //判断和上面行的皇后是否冲突
                if (isOk(row, col, res)) {
                    //迭代,下一行
                    count = nQueen(n, row + 1, res, count);
                }
            }
            return count;
        }
    
        private boolean isOk(int row, int col, int[] res) {
            for (int i = 0; i < row; i++) {
                //判断上面每行皇后所在列, 如果和当前列相同则为false
                if (res[i] == col) {
                    return false;
                }
                //判断撇和捺方向, 是两个斜率为1和-1的直线, 则他们两个坐标 |y2 - y1| == |x2 - x1|
                if (row - i == col - res[i] || row - i == res[i] - col) {
                    return false;
                }
            }
            return true;
        }
    
        private void print(int n, int[] res) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (res[i] == j) {
                        System.out.print("Q");
                    } else {
                        System.out.print("*");
                    }
                    System.out.print(" ");
                }
                System.out.println();
            }
        }
    }
    

    进行测试

    package com.lagou.backMethod.test;
    
    import com.lagou.backMethod.NQueens;
    
    /**
     * @author 云梦归遥
     * @date 2022/5/22 11:21
     * @description
     */
    public class NQueensTest {
        public static void main(String[] args) {
            NQueens nQueens = new NQueens();
            int n = 8;
            int nQueen = nQueens.nQueen(n, 0, new int[n], 0);
            System.out.println("nQueen = " + nQueen);
        }
    }
    

    在这里插入图片描述

    3.总结

    • 时间复杂度
      • N皇后问题的时间复杂度为: O(n ! ),实际为 n ! / 2
    • 优缺点
      • 优点:
        • 回溯算法的思想非常简单,大部分情况下,都是用来解决广义的搜索问题,也就是,从一组可能的解中,选择出一个满足要求的解。回溯算法非常适合用递归来实现,在实现的过程中,剪枝操作是提高回溯效率的一种技巧。利用剪枝,我们并不需要穷举搜索所有的情况,从而提高搜索效率
      • 劣势:
        • 效率相对于低(动态规划)
    展开全文
  • N皇后问题(n-queen problem)是一个经典的组合优化问题,也是一个使用回溯法(backtracking)的典型例子。回溯法是一种系统地搜索问题解的方法。 此文档包含算法分析、代码实现、演示程序、演示界面。
  • 这是 Java 中著名的 N Queens 问题的实现。 这使用了递归回溯的概念。 此类使用辅助函数 place(),如果可以将皇后放置在给定的坐标中,则该函数返回 true。 positionInRow - 该数组将保存放置的皇后的列值,其中...
  • N皇后问题java】【回溯法】N皇后问题概述N皇后问题java代码解析 N皇后问题概述 要想解决n皇后问题,首先要明白什么是n皇后问题。 在本篇文章中,借助 leetcode 51.N皇后问题 进行解析。 N皇后问题题目: n 皇后...

    N皇后问题概述

    要想解决n皇后问题,首先要明白什么是n皇后问题。
    在本篇文章中,借助 leetcode 51.N皇后问题 进行解析。

    N皇后问题题目:

    n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击
    给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

    每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位
    在这里插入图片描述
    由上述题目的描述,简而言之,就是:

    在一个棋盘上,一个皇后(棋子)的 同一列、同一行、以皇后为中心的两条对角线 都不能有任何棋子,求所有可能的情况,这就是N皇后问题。

    N皇后问题java代码解析

    由于我使用了回溯法解决了N皇后问题,所以本篇文章详细讲述如何用回溯法解决n皇后问题
    本文仅仅代表作者的思路,可能有大佬的思路更好一些,欢迎大家发表想法。
    在阅读本文之前,建议大家首先了解回溯法,本文会尽量让大家了解回溯法的解题技巧。

    首先,N皇后问题的回溯代码大致可以分为调用函数(这里就不使用java方法的概念了,感觉函数更顺口一点)、回溯算法判断选择三个方法。

    调用函数

    顾名思义,调用函数就是调用回溯算法解决问题的函数,该函数篇幅很短,主要用于定义路径、调用回溯函数、返回结果三个作用。

    class Solution {
    	//res表示result,保存最后的结果
        List<List<String>> res = new ArrayList<>();
        
        //调用函数
        public List<List<String>> solveNQueens(int n) {
            //记录正确的结果
            ArrayList<StringBuilder> track = new ArrayList<>();
            //回溯算法
            backtrack(n, 0, track);
            //返回结果
            return res;
        }
    }
    

    解释两点:

    • 返回类型为List<List<String>>,是因为返回值是一个集合,集合中的每个元素都是一种正确的解法,而每一种解法都是一个List<String>类型,如:
      [“.Q…”,“…Q”,“Q…”,“…Q.”],这就是一个棋盘,一个正确的结果。
    • 记录正确的结果时,我使用了List<StringBuilder>而不是List<String>,是因为将 ‘.’ 修改为 ‘Q’ 时,StringBuilder 更简单一点。

    回溯算法

    /**
    * 回溯算法
    * @param n		   N皇后问题的 N
    * @param row       n*n 棋盘上的第几行
    * @param track     路径(结果)
    */
    public void backtrack(int n, int row, List<StringBuilder> track) {
            //触发结束条件
            if(track.size() == n) {
                List<String> list = chg(track);
                res.add(list);
                return;
            }
            StringBuilder sb = new StringBuilder();
            for(int i = 0;i < n;i++) {
                sb.append(".");
            }
            for(int i = 0;i < n;i++) {
                //排除不合法的选择
                if(!isValid(n, track, row, i)) {
                    continue;
                }
                //做选择
                sb.setCharAt(i, 'Q');
                track.add(sb);
                //进入下一层决策树
                backtrack(n, row + 1, track);
                //取消选择
                sb.setCharAt(i, '.');
                track.remove(track.size() - 1);
            }
        }
    

    分析:

        //触发结束条件
        if(track.size() == n) {
            List<String> list = chg(track);
            res.add(list);
            return;
        }
        这是回溯算法必须要有的,如果没有条件,那么回溯算法将会一直递归;n皇后问题的条件是:
        当 n * n 大的棋盘上放置了 n 个皇后时,这种情况正确,递归结束并加入最终结果中。(chg函数是将 List<StringBuilder> 类型转换为 List<String> 类型)
    
    	//sb 是棋盘中的某一行。
    	StringBuilder sb = new StringBuilder();
        //进行初始化(“.”表示没有放棋子)
        for(int i = 0;i < n;i++) {
            sb.append(".");
        }
        
    
    	//从第 0 列开始,第 n 列结束
    	for(int i = 0;i < n;i++) {
            //排除不合法的选择
            if(!isValid(n, track, row, i)) {
                continue;
            }
            //尝试(尝试将第 row 行的第 i 列放置皇后)
            sb.setCharAt(i, 'Q');
            track.add(sb);
            //进入下一层决策树(进入下一行继续尝试)
            backtrack(n, row + 1, track);
            //取消选择(将皇后取消,并删除该行)
            sb.setCharAt(i, '.');
            track.remove(track.size() - 1);
        }
    
    

    判断选择

    public static boolean isValid(int n, List<StringBuilder> track, int row, int col) {
            //检查列中是否有皇后互相冲突
            for(int i = 0;i < row;i++) {
            	//如果上方有‘Q’,不能放置,返回结果false。
                if(track.get(i).charAt(col) == 'Q') {
                    return false;
                }
            }
            //检查右上方是否有皇后互相冲突
            for(int i = row - 1, j = col + 1;i >= 0 && j < n;i--, j++) {
                if(track.get(i).charAt(j) == 'Q') {
                    return false;
                }
            }
            //检查左上方是否有皇后互相冲突
            for(int i = row - 1, j = col - 1;i >= 0 && j >= 0;i--, j--) {
                if(track.get(i).charAt(j) == 'Q') {
                    return false;
                }
            }
            return true;
        }
        
    	//将 List<StringBuilder> 转换为 List<String>,可能多此一举,看看就好
    	public static List<String> chg(List<StringBuilder> track) {
            List<String> list = new ArrayList<>();
            for(int i = 0;i < track.size();i++) {
                list.add(new String(track.get(i)));
            }
            return list;
        }
    

    到这里,n皇后的 java 代码部分就结束了。回溯题目大同小异,这里放一下 backtrack 的大致框架:

    public static void backtrack(int n, List<StringBuilder> track) {
            //触发结束条件(结束递归)
            if(......) {
                //向结果中添加一种解决方案
                res.add(list);
                //返回
                return;
            }
    
            for(int i = 0;i < n;i++) {
                //排除不合法的选择
                if(...) {
                    continue;
                }
    
                //做选择
                
                track.add(...);
    
                //进入下一层决策树
                backtrack(n, track);
    
                //取消选择
                track.remove(track.size() - 1);
            }
    
        }
    

    大致框架就这样子,但是要根据实际情况灵活变通。
    至此,n 皇后问题就解决啦,感谢观看!

    展开全文
  • 回溯法与N皇后问题JAVA实现

    万次阅读 多人点赞 2018-04-17 13:50:51
    提出问题皇后问题:在8*8格的国际象棋上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。如何解决这个问题?一种常用且有效的方法是回溯法,是用树形结构...
  • 回溯算法N皇后问题

    2021-03-17 22:33:00
    ❞如果对回溯法理论还不清楚的同学,可以先看这个视频:n 皇后问题研究的是如何将 n皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互***。上图为 8 皇后问题的一种解法。给定一个整数 n,返回所有不同的 n ...
  • java N皇后 回溯

    2021-08-13 16:04:13
    java N皇后问题 回溯法 1.什么是N皇后问题 N皇后问题由八皇后问题衍生而来,那么什么又叫作八皇后问题呢? 八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848...
  • java语言,回溯算法求解N皇后问题
  • 回溯法解决N皇后问题-java

    千次阅读 2022-03-10 11:38:33
    参照LeetCode第51题的题干,N皇后是指将N个皇后放置在NXN的棋盘上,并且皇后之间不可以互相攻击,即其中任意两个皇后不能在同一行、同一列或者同一条斜线上。 四皇后的放置情况示例如下: 采用回溯法解决该问题...
  • 回溯查找是一种暴力查找方法,查找的过程中用约束的条件进行判断,进行回溯。八皇后就是不能处于同列对角,进行约束判断。 package recursion; import java.util.ArrayList; public class Queen8 { int[] res =...
  • /*by wbin 2015/12/18实现n皇后问题回溯法过程,以java图形界面展示,代码写得略丑,见谅.*/import java.awt.Color;import java.awt.Font;import java.awt.GridLayout;import java.awt.Label;import javax.swing....
  • n皇后问题 研究的是如何将 n个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。 给你一个整数 n ,返回所有不同的n皇后问题 的解决方案。 每一种解法包含一个不同的n 皇后问题 的棋子放置方案,该方案...
  • 递归-八皇后问题(回溯算法) 八皇后问题介绍 八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击...
  • 回溯法解n皇后问题 n皇后问题描述是:将n个皇后放在n*n的棋盘上,使得任意两个皇后不在同一行,同一列和同一斜线上,找出解的总数,并输出每个解。(.表示不放皇后,Q表示放置皇后) 我的思路:根据题意可以明显得出,...
  • NQueens_Backtracking 回溯算法解决N皇后问题
  • 回溯算法解八皇后问题java版)

    万次阅读 多人点赞 2016-03-21 12:07:30
     下面用java版的回溯算法来解决八皇后问题。  八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相...
  • 使用回溯算法求解N皇后问题

    千次阅读 2019-11-29 13:21:17
    文章目录N皇后问题描述回溯算法简介回溯算法问题的要求回溯算法的思想回溯算法的模板使用回溯算法求解N皇后问题 N皇后问题描述 在一个N * N的国际象棋棋盘上需要放置N个皇后,放置时要保证这些皇后不能攻击彼此,...
  • 今天在刷LeetCode时,遇到了一个N皇后问题问题如下: n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击,即同一横行、数列、斜线不能出现两个皇后。需要输出所有的摆放...
  • //递归-八皇后问题回溯算法) /** * 八皇后问题算法思路分析 1)第一个皇后先放第一行第一列 * 2)第二个皇后放在第二行第一列,然后判断是否OK,如果不OK,继续放在第二列,第三列,依次把所有列放完,找到一个...
  • 本文实例讲述了PHP基于回溯算法解决n皇后问题的方法。分享给大家供大家参考,具体如下:这里对于n皇后问题就不做太多的介绍,相关的介绍与算法分析可参考前面一篇C++基于回溯法解决八皇后问题。回溯法的基本做法是...
  • 皇后问题
  • 回溯法解N皇后问题

    2021-11-28 15:24:24
    算法经典问题——N皇后问题
  • 皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即:任意两个皇后都不能处于同一行、同一列...
  • 回溯算法求解N皇后问题 java
  • n问题回溯算法 java

    2009-12-24 05:58:58
    回溯法实现n皇后问题,并输出每种放法的皇后位置
  • /***Follow up for N-Queens problem.Now, instead outputting board configurations, return the total number of distinct solutions.* @author Zealot* @date 2015年7月23日 下午6:14:49*/public...
  • N皇后问题 这是一个典型的回溯问题 也可以称为棋盘问题,我们由题目知道的约束条件 1:左上角和右上角不能连续放 2:同一行和同一列不能放 然后做回溯题目的第一步 画N叉树 然后可以看出 1:递归深度为行 循环遍历...

空空如也

空空如也

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

回溯算法n皇后问题java