n皇后问题 回溯法java_Java解决N皇后问题

n皇后问题 回溯法java_Java解决N皇后问题问题描述:   要求在一个n×n的棋盘上放置n个皇后,使得它们彼此不受攻击。   按照国际象棋的规则,一个皇后可以攻击与之同一行或同一列或同一斜线上的任何棋子。   因此,n皇后问题等价于:要求在一个n×n的棋盘上放置n个皇后,使得任意两个皇后不在同一行或同一列或同一斜线上。一个皇后的攻击范围:                                    n皇后的解空间—完全n叉树…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

问题描述:

    要求在一个n×n的棋盘上放置n个皇后,使得它们彼此不受攻击。

    按照国际象棋的规则,一个皇后可以攻击与之同一行或同一列或同一斜线上的任何棋子。

    因此,n皇后问题等价于:要求在一个n×n的棋盘上放置n个皇后,使得任意两个皇后不在同一行或同一列或同一斜线上。

一个皇后的攻击范围:

                                    n皇后问题 回溯法java_Java解决N皇后问题


n皇后的解空间—完全n叉树:

                        n皇后问题 回溯法java_Java解决N皇后问题

    要找出“四皇后”问题的解,最可靠的方法就是把各种情况都分析一遍,将符合条件的解找出来。但这样做十分地费时间。

采用回溯算法进行求解,在搜索的过程中,将不满足条件要求的分支树剪去,可以有效地降低算法的时间复杂度

首先定义一个Location类,用来表示棋盘上(实际上就是一个二维数组)点的位置:

static class Location{
		int x;//对应棋盘的行
		int y;//对应棋盘的列
		
		Location(int x,int y){
			this.x = x;
			this.y = y;
		}
		
                //重写toString函数用来输出点的信息
		public String toString() {
			return "(" + x + "," + y + ")";
		}
	}

然后就是判断两个皇后放置的位置是否冲突,需要判断是否在同一行、同一列和同一斜线上,这里所有的符合要求的皇后都放置在一个Location链表中,如果要新加入一个皇后,就必须要与当前链表中所有的皇后都进行冲突比较,如果冲突就放弃这个方案;如果不冲突,继续下一步,直到N个皇后都存在于链表中,才算得到了一个解:

/**
     * 判断位置为loc的皇后是否合法
     */
    private static boolean isLegalLoc(LinkedList<Location> list, Location loc) {
        for(Location each : list){
            if(loc.x == each.x || loc.y == each.y)  //判断是否在同一行或同一列
                return false;
            else if (Math.abs(loc.x - each.x) == Math.abs(loc.y - each.y))  //判断是否在同斜线上
                return false;
        }
        return true;
    }

核心算法:

	/**
     * 主要函数,用回溯法。
     */
    private static void NQueen(LinkedList<Location> list, int x, int y) {   

        if(list.size() == SIZE){  //当list元素个数为SIZE时,表示SIZE个皇后都摆放完毕,打印后即可退出函数。
            printLocation(list);  //打印皇后摆放方式
            return ;
        }

        for(int i = x ; i < SIZE ; i++){
            Location loc = new Location(i, y);
            if(isLegalLoc(list, loc)){
                list.offer(loc);  //将第y行的皇后摆放好
                NQueen(list, 0, y+1);  //开始摆放y+1行的皇后,同样从第0列开始摆放
                list.pollLast();  //每次摆放完一个皇后后,都要将其撤回,再试探其它的摆法。
            }                   
        }           
    }

由于皇后的攻击范围的特性,在这个算法执行时,只用考虑一行或者一列的情况就行,即要么使x=0固定,让y从0到n-1进行;要么反过来让y=0固定,让x从0到n-1进行。这样可以省去很多不必要的比较。

全部代码(其中还包括将N皇后问题的解显示输出的函数):

package quene;

import java.util.LinkedList;
import java.util.Scanner;

public class Com_quene {

	private static int SIZE = 0;//皇后的个数
	private static int count = 0;//记录摆放的方式数
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner input = new Scanner(System.in);
		System.out.println("请输入你要解决几个皇后的问题");
		SIZE = input.nextInt();
		input.close();
		 LinkedList<Location> list = new LinkedList<Location>();
	     NQueen(list, 0, 0);  //从棋盘的第0行第0列开始
	     System.out.println(SIZE + "皇后共有 " + count + "种摆放方式");

	}
	static class Location{
		int x;//对应棋盘的行
		int y;//对应棋盘的列
		
		Location(int x,int y){
			this.x = x;
			this.y = y;
		}
		
		public String toString() {
			return "(" + x + "," + y + ")";
		}
	}
	
	/**
     * 主要函数,用回溯法。
     */
    private static void NQueen(LinkedList<Location> list, int x, int y) {   

        if(list.size() == SIZE){  //当list元素个数为SIZE时,表示SIZE个皇后都摆放完毕,打印后即可退出函数。
            printLocation(list);  //打印皇后摆放方式
            return ;
        }

        for(int i = x ; i < SIZE ; i++){
            Location loc = new Location(i, y);
            if(isLegalLoc(list, loc)){
                list.offer(loc);  //将第y行的皇后摆放好
                NQueen(list, 0, y+1);  //开始摆放y+1行的皇后,同样从第0列开始摆放
                list.pollLast();  //每次摆放完一个皇后后,都要将其撤回,再试探其它的摆法。
            }                   
        }           
    }

	
	/**
     * 判断位置为loc的皇后是否合法
     */
    private static boolean isLegalLoc(LinkedList<Location> list, Location loc) {
        for(Location each : list){
            if(loc.x == each.x || loc.y == each.y)  //判断是否在同一行或同一列
                return false;
            else if (Math.abs(loc.x - each.x) == Math.abs(loc.y - each.y))  //判断是否在同斜线上
                return false;
        }
        return true;
    }

    /**
     * 打印皇后摆放方式
     * @param list
     */
    private static void printLocation(LinkedList<Location> list) {
    	String[][] show = new String[SIZE][SIZE];
    	for(int i = 0;i<SIZE;i++) {
    		for(int j = 0;j<SIZE;j++) {
    			show[i][j] = "0";
    		}
    	}
    	for(Location each : list){
            System.out.print(each.toString() + "\t");
            show[each.x][each.y] = "1";
        }
        System.out.println();
        
        for(int i =0;i<SIZE;i++) {
        	for(int j=0;j<SIZE;j++) {
        		System.out.print(show[i][j] + " ");
        	}
        	System.out.println();
        }
        System.out.println();

        count ++;
    }


}

四皇后问题解的示例:

n皇后问题 回溯法java_Java解决N皇后问题

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/187510.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • SPI 协议详解_cifs协议

    SPI 协议详解_cifs协议SPI协议详解1、SPI简介2、SPI四线3、SPI四种工作模式4、SPI时序图1、SPI简介SPI全称是SerialPerripheralInterface,也就是串行外围设备接口。SPI是Motorola公司推出的一种同步串行接口技术,是一种高速、全双工的同步通信总线,SPI时钟频率相比I2C要高很多,最高可以工作在上百MHz。SPI以主从方式工作,通常是有一个主设备和一个或多个从设备,一般SPI需要4根线,但是也可以使用三根线(单向传输)2、SPI四线

    2022年10月15日
  • 三菱modbusrtu通讯协议报文_modbus通讯协议详解

    三菱modbusrtu通讯协议报文_modbus通讯协议详解点击箭头处“工业之家”,选择“关注公众号”!modbus通讯协议详解Modbus协议可以说是工业自动化领域应用最为广泛的通讯协议,因为它的开放性、可扩充性和标准化使它成为一个通用工业标准。有了它,不同厂商的产品可以简单可靠的接入网络,实现系统的集中监控,分散控制功能。目前Modbus规约主要使用的是ASCII,RTU,TCP等,并没有规定物理层。目前Modbus常用的接口形式主要有R…

  • elasticsearch数据库搭建 window版

    elasticsearch数据库搭建 window版说明:安装elasticsearch之前必须安装好jdk运行环境1.首先下载安装包:这是官网最新安装包:https://artifacts.elastic.co/downloads/elasticsearch/elasticsearch-7.5.1-windows-x86_64.zip2.直接解压到想要安装的目录即可 3.配置文件打开config下的elasticsearch.yml…

  • SRC挖掘—web不安全的直接对象引用 (IDOR)漏洞-3day

    SRC挖掘—web不安全的直接对象引用 (IDOR)漏洞-3day什么是IDOR?当应用程序根据用户提供的输入提供对对象的直接访问时,就会发生不安全的直接对象引用(IDOR)。由于此漏洞,攻击者可以绕过授权并直接访问系统中的资源,例如数据库记录或文件。不安全的直接对象引用允许攻击者通过修改用于直接指向对象的参数值来绕过授权并直接访问资源。这些资源可以是属于其他用户的数据库条目、系统中的文件等等。这是因为应用程序接受用户提供的输入并使用它来检索对象而没有执行足够的授权检查。(来源:OWASP)让我们看一个例子。想象一下,您正在使用一个文档共享平台。您可以上传..

  • ie9的兼容视图设置_ie9兼容性视图设置找不到

    ie9的兼容视图设置_ie9兼容性视图设置找不到ie9比ie8又向W3C标准靠近了一步,可能会导致原有的网页显示变乱;如果出现这种情况,选择ie9兼容性视图,网页显示就会正常。ie9分别有,为当前网页设置兼容性和为所有网站设置兼容性视图两种,下面分别说明:一、为当前网页设置兼容性视图1、快捷步骤:按alt键——工具——兼容性视图(V);或者按alt键——工具——按F12——浏览器模式(B):IE9——Internet…

  • 订单支付功能测试

    订单支付功能测试支付金额1.小于最小值,如:小于0.012.大于最大值/金额上限3.无实际意义金额,如0元4.格式错误(负数、非数字)5.余额小于实际需要支付的金额6.超过第三方支付接口当日消费/单笔消费金额支付接口第三方接口,微信/支付宝/网银系统/post机终端服务→可以参照:https://mp.csdn.net/postedit/100169648…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号