首页 > 编程语言 > 详细

递归,回溯算法两大经典案例—迷宫问题和八皇后问题

时间:2019-09-16 23:55:04      阅读:152      评论:0      收藏:0      [点我收藏+]

迷宫问题:

技术分享图片

问题描述:

用二维数组表示一个迷宫,比如1表示墙,0表示空格,设置一个起点和终点,让小球自己从迷宫的起点到终点走出一条路径,并将路径标识为2。

代码实现:

 1 package cn.ftf.digui;
 2 
 3 public class MiGong {
 4     public static boolean findPath(int[][]arr,int i,int j) {
 5         //结束条件
 6         if(arr[6][5]==2) {
 7             return true;
 8         }
 9         if(arr[i][j]==0) {
10             arr[i][j]=2;
11             if(findPath(arr,i+1,j)) {
12                 return true;
13             }else if(findPath(arr,i,j+1)){
14                 return true;
15             }else if(findPath(arr,i-1,j)){
16                 return true;
17             }else if(findPath(arr,i,j-1)){
18                 return true;
19             }else {
20                 arr[i][j]=3;
21                 return false;
22             }
23         }else {
24             return false;
25         }
26     }
27     public static void main(String[] args) {
28         int[][] map=new int[8][7];
29         for(int i=0;i<7;i++) {
30             map[0][i]=1;
31             map[7][i]=1;
32         }
33         for(int j=0;j<7;j++) {
34             map[j][0]=1;
35             map[j][6]=1;
36         }
37         map[3][1]=1;
38         map[3][2]=1;
39         map[5][5]=1;
40         //map[6][5]=1;
41         System.out.println("初始地图:");
42         for(int i=0;i<8;i++) {
43             for(int j=0;j<7;j++) {
44                 System.out.print(map[i][j]+"  ");
45             }
46             System.out.println();
47         }
48         
49         findPath(map,1,1);
50         System.out.println("最终地图:");
51         for(int i=0;i<8;i++) {
52             for(int j=0;j<7;j++) {
53                 System.out.print(map[i][j]+"  ");
54             }
55             System.out.println();
56         }
57     }
58 }

运行结果:

技术分享图片

 

八皇后问题(N皇后问题)

八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n1×n1,而皇后个数也变成n2。而且仅当 n2 ≥ 1 或 n1 ≥ 4 时问题有解。

算法步骤分析:

 技术分享图片

 

 代码实现:

 1 package cn.ftf.queue8;
 2 
 3 public class Queue8 {
 4     private static int max=8;
 5     private static int[] arr=new int[max];
 6     private static int count=1;
 7     
 8     //每生成一种解法,将这种解法打印出来 
 9     private static void print() {
10         for(int i=0;i<max;i++) {
11             System.out.print(arr[i]+"  ");
12         }
13         System.out.println("这是第"+(count++)+"种解法!");
14     }
15     
16     //判断这个棋子是否与前面的冲突
17     private static boolean judge(int i) {
18         for(int j=0;j<i;j++) {
19             if(arr[j]==arr[i]||Math.abs(arr[j]-arr[i])==Math.abs(j-i)) {
20                 return false;
21             }
22         }
23         return true;
24     }
25     
26     //挨个的放棋子
27     private static void put(int i) {
28         if(i==max) {
29             print();
30             return;
31         }else {
32             for(int j=0;j<max;j++) {
33                 arr[i]=j;
34                 if(judge(i)) {
35                     put(i+1);
36                 }
37             }
38         }
39     }
40     
41     public static void main(String[] args) {
42         put(0);
43     }
44 }

运行结果:

技术分享图片

共92种解法!

 

 

 

 

递归,回溯算法两大经典案例—迷宫问题和八皇后问题

原文:https://www.cnblogs.com/fangtingfei/p/11524777.html

(3)
(3)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!