八皇后问题
八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于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的棋盘上,并且使皇后彼
ofc
N 皇后 II
official
966
leetcode第52题(困难)原链接:https://leetcode-cn.com/problems/n-queens-ii/题目描述n皇后问题研究的是如何将n个皇后放置在n×n的棋盘上,并且使
blog
数据结构-图的着色问题
数据结构与算法
12872
觉图的着色问题类似与八皇后问题,使用回溯算法(试探法)解决算法描述state[n]存储n个顶点的着色方案,可以选择的颜色为1到m。当t=1时,对当前第t个顶点开始着色:若tn,则已求得一个解,输出着色方
blog
算法-渗透问题
数据结构与算法
7037
问题描述:渗透问题,给一个n*m的矩阵,0为空白,1为白纸,2为墨水,墨水每经过每一秒会将上下左右相邻的白纸染成黑色,然后继续渗透,判断此图中的白纸最终是否能够全部被墨水染上色,若能需要输出所有白纸
blog
汉诺塔问题
数据结构与算法
5279
。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。packageproblem;/***汉诺塔问题*@authorLENOVO**/publicclassHanoi{publicv
blog
迷宫问题-js实现
数据结构与算法
4087
迷宫问题!DOCTYPEhtmlhtml head metacharset="UTF-8" title/title script varflag=true; window.onload
blog
算法-求和问题
数据结构与算法
12625
问题描述给定一个int类型一维数组a[],和一个int类型的数值b。编写一个程序,判断数组中有没有两个数(a[i],a[j])的和等于b,如果存在,返回两个数在a数组中的下表
blog
温故01背包问题
数据结构与算法
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
加密算法
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。