八皇后问题

硅谷探秘者 7833 0 0


八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。

1.方案1:用二维数组表示棋盘,回溯搜索

/**
 * 回溯,深度优先搜索,递归
 * @author LENOVO
 *
 */
public class 八皇后问题 {
	public static boolean visit[][]=new boolean[8][8];//标记棋盘数组
	public static int c=0;//记录答案
	public static void main(String[] args) {//主函数
		dfs(0);
		System.out.println("答案:"+c);
	}
	public static void dfs(int y) {//y表示放第y个皇后,dfs搜索
		if(y>=8) {//如果八个皇后已放满
			c++;
			System.out.println("--------------------------第"+c+"个答案----------------------");
			System.out.println();
			for(int i=0;i<8;i++) {
				for(int j=0;j<8;j++) {
					System.out.print((visit[i][j]?"1":"0")+"\t");
				}
				System.out.println();
			}
			return;
		}
		for(int i=0;i<=7;i++) {//循环遍历8列
		        //可以放否,可以,继续递归搜索,否则回归
			if(hang(i)&&lie(y)&&xiangxian1(i,y)&&xiangxian4(i,y)) {
				visit[i][y]=true;
				dfs(y+1);
				visit[i][y]=false;
			}
		}
	}
	public static boolean hang(int x) {//判断行
		for(int i=0;i<8;i++) {
			if(visit[x][i]) {
				return false;
			}
		}
		return true;
	}
	public static boolean lie(int y) {//判断列
		for(int i=0;i<8;i++) {
			if(visit[i][y]) {
				return false;
			}
		}
		return true;
	}
	public static boolean xiangxian1(int x,int y) {//    \ 二四象限
		if(x>y) {
			x=x-y;y=0;
		}else if(x<y) {
			y=y-x;x=0;
		}else {
			x=0;y=0;
		}
		for(;x<8&&y<8;) {
			if(visit[x++][y++]) {
				return false;
			}
		}
		return true;
	}
	public static boolean xiangxian4(int x,int y) {//   / 一三象限
		int i=x,j=y;
		while(i<8&&j>=0) {
			if(visit[i++][j--]) {
				return false;
			}
		}
		while(x>0&&y<8) {
			if(visit[x--][y++]) {
				return false;
			}
		}
		return true;
	}
}

2.方案2,用一维数组代表二维数组的棋盘,一维数组的下表代表行,一维数组的值代表列,然后回溯搜索

public class Queen {	
	static int chessboard[];
	static int count=0;
	public static void main(String[] args) {
		chessboard =new int[]{-1,-1,-1,-1,-1,-1,-1,-1,-1};
		change(1);
		System.out.println(count);
	}
	public static boolean judge(int pointi,int pointj){//判断某个皇后是否与已有皇后冲突
		System.out.println(pointi+"  "+pointj);
	    for(int i=1;i<pointi;i++){
	    	System.out.println("    "+(pointi-i)+":"+(pointj-chessboard[i]));
	        if(pointj==chessboard[i])return false;//同一列
	        if((pointi-i)==(pointj-chessboard[i]))return false;//同一主对角线
	        if((pointi-i)+(pointj-chessboard[i])==0)return false;//同一副对角线
	    }
	    return true;
	}
	public static void change(int row){//在第row行找能放皇后的位置
	    for(int i=1;i<9;i++){//从1~8遍历这一行的八个空位
	        if(judge(row,i)){ //如果可以放这个位置就记录下第row个皇后的位置
	            chessboard[row]=i;
	            if(row==8){//如果八个皇后都放满了统计一下
	                count++;
	                return;
	            }
	            change(row+1);//还有皇后没放递归放下一个皇后
	        }
	    }
	    chessboard[--row]=-1;//如果这一行没有可放的位置说明上一行皇后放的位置不行,
	                        //要为上一个皇后寻找新的可放位置
	    return;
	}
}



评论区
请写下您的评论...
暂无评论...
猜你喜欢
ofc N
official 888 leetcode第51(困难)原链接:https://leetcode-cn.com/problems/n-queens/目描述n研究的是如何将n个放置在n×n的棋盘上,并且使
official 966 leetcode第52(困难)原链接:https://leetcode-cn.com/problems/n-queens-ii/目描述n研究的是如何将n个放置在n×n的棋盘上,并且使
数据结构与算法 12872 觉图的着色类似与,使用回溯算法(试探法)解决算法描述state[n]存储n个顶点的着色方案,可以选择的颜色为1到m。当t=1时,对当前第t个顶点开始着色:若tn,则已求得一个解,输出着色方
数据结构与算法 7037 描述:渗透,给一个n*m的矩阵,0为空白,1为白纸,2为墨水,墨水每经过每一秒会将上下左右相邻的白纸染成黑色,然继续渗透,判断此图中的白纸最终是否能够全部被墨水染上色,若能需要输出所有白纸
数据结构与算法 5279 。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。packageproblem;/***汉诺塔*@authorLENOVO**/publicclassHanoi{publicv
数据结构与算法 4087 迷宫!DOCTYPEhtmlhtml head metacharset="UTF-8" title/title script varflag=true; window.onload
数据结构与算法 12625 描述给定一个int类型一维数组a[],和一个int类型的数值b。编写一个程序,判断数组中有没有两个数(a[i],a[j])的和等于b,如果存在,返回两个数在a数组中的下表
数据结构与算法 6225 01背包是动态规划算法的一个经典例目: 在n种物品中选取若干件(每种物品只有一件只能选择一次) 放在空间为W的背包里,每种物品的体积为wigth[1],wigth[2],wigth[3
归档
2018-11  12 2018-12  33 2019-01  28 2019-02  28 2019-03  32 2019-04  27 2019-05  33 2019-06  6 2019-07  12 2019-08  12 2019-09  21 2019-10  8 2019-11  15 2019-12  25 2020-01  9 2020-02  5 2020-03  16 2020-04  4 2020-06  1 2020-07  7 2020-08  13 2020-09  9 2020-10  5 2020-12  3 2021-01  1 2021-02  5 2021-03  7 2021-04  4 2021-05  4 2021-06  1 2021-07  7 2021-08  2 2021-09  8 2021-10  9 2021-11  16 2021-12  14 2022-01  7 2022-05  1 2022-08  3 2022-09  2 2022-10  2 2022-12  5 2023-01  3 2023-02  1 2023-03  4 2023-04  2 2023-06  3 2023-07  4 2023-08  1 2023-10  1 2024-02  1 2024-03  1 2024-04  1 2024-08  1
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议 keepalived minio mysql ensp 网络基础 xxl-job rabbitmq haproxy srs 音视频 webrtc javascript 加密算法
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。