|
目录
 今日良言：花有重开日，人无再少年
一.迷宫问题
 1.问题描述
2.思路分析
3.效果展示
4.完整代码
二、八皇后问题
1.问题描述
2.思路分析
3.效果展示
4.完整代码
今日良言：花有重开日，人无再少年
一.迷宫问题
1.问题描述
给定一个迷宫，指明了起点和终点，找出从起点出发到终点的有效可行路径，就是迷宫问题。
我们这里创建 8 x 7 的迷宫，第一列以及最后一列，第一行以及最后一行都是障碍物墙，在迷宫中间 下标 [3,1] 和[3,2] 也设置两个障碍物，现在要求小球从起点 [1,1]开始走，终点是 [6,5],按照：下->右->上->左的行走策略，找出小球到达 [6,5] 的路径。 当然这个行走策略有很多种，你可以选自己喜欢的一种进行操作。
2.思路分析
迷宫问题是回溯算法的一种。我们想到的解决方法自然与回溯相关，首先，我们创建好迷宫，如下图：小球没有走过的位置为0,1是墙
迷宫设置好后，我们需要创建一个方法setWay 来让小球开始走，该方法有三个参数，第一个参数是二维数组构成的迷宫map，第二、三个参数是小球开始走的行、列。 我们将小球走过可以到达终点的路径数据设置成2，无法到达终点的路径数据设置成3。首先判断小球是否到达了终点，如下语句，当 [6,5] == 2 时说明到达了终点。
我们判断 [i,j] 这个下标是否可以走的时候，判断条件是 map[i,j] 是否等于0 ，默认值是0，如果不是0的话，说明这个点已经走过了，直接返回false即可，直接如果是的话，就将 map[i,j] 设置成2 继续按照：下->右->上->左的行走策略移动，当发现下右上左都无法移动时，将该点设置成 3，然后回溯到上一个点，继续进行下一步的移动。如下代码：
3.效果展示
我们就按照上面设置的迷宫来走，最终效果如下：
上述是小球可以到达终点，下面我们多设置几个障碍物，让小球无法到达终点
4.完整代码
public class MiGong {
public static void main(String[] args) {
// 先创建8*7的地图
int[][] arr = new int[8][7];
// 为上下增加墙
for (int i = 0; i < 7; i++) {
arr[0][i] = 1;
arr[7][i] = 1;
}
// 为左右增加墙
for (int i = 1; i < 8;i++) {
arr[i][0] = 1;
arr[i][6] = 1;
}
arr[3][1] = 1;
arr[3][2] = 1;
arr[1][2] = 1;
arr[2][2] = 1;
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 7; j++) {
System.out.print(arr[i][j]+" ");
}
System.out.println();
}
// 地图设置好后就开始让小球走迷宫
setWay(arr,1,1);
System.out.println("小球行走过后的地图");
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 7; j++) {
System.out.print(arr[i][j]+" ");
}
System.out.println();
}
}
/**
* 利用回溯算法来给小球找路
* @param map 地图
* @param i 小球开始横坐标
* @param j 小球开始纵坐标
* @return 找到通路就返回
*/
public static boolean setWay(int[][] map,int i,int j) {
// 当小球可以到达6 5坐标是说明成功
if (map[6][5] == 2) {
System.out.println("小球到达终点");
return true;
}
// 如果当前这个点还没有走过
if (map[i][j] == 0) {
// 这个点没有走过的话，就从该点开始走，设置成2
// 假设这个点可以走
map[i][j] = 2;
// 规定小球的行驶路线是：下-》右-》上-》左
if (setWay(map,i+1,j)) { // 向下走
return true; // 说明这个点可以走
} else if (setWay(map,i,j+1)) { // 向右走
return true;
} else if (setWay(map,i-1,j)) { // 向上走
return true;
} else if (setWay(map,i,j-1)) { // 向左走
return true;
} else {
// 说明当前这个点不能走
map[i][j] = 3;
return false;
}
} else {
// 说明这个点已经走过了
return false;
}
}
}
二、八皇后问题
1.问题描述
这里引一下官方描述：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。计算机发明后，有多种计算机语言可以编程解决此问题。
2.思路分析
分析问题，理论上我们应该创建一个二维数组来解决这个问题，实际上，我们可以只创建一个长度为8的一维数组arr来解决这个问题。 arr 的下标代表的是每一行，arr[i] 值代表的是列。首先我们创建8个皇后，以及arr数组：
静态变量 count用于统计共多少种解法。
然后我们创建一个方法来check来放置皇后，该方法只有一个参数n （代表的是放置的第几个皇后） 因为我们是从0号下标开始放，当 n == 8 时，说明8个皇后已经放置完了，结束回溯。 有了判断条件后，我们就要开始放皇后了，我们需要的是，得到所有的解法，所以说，我们从第一列开始放皇后。当然，我们需要检验在当前列放下皇后以后是否和之前已经放过的皇后位置冲突，所以我们还需要一个方法检验该皇后位置的合法性，如下代码：
如果当前位置合法，那么就继续放下一个皇后，如果当前位置不合法，那么就继续换另外一个列，如果这个皇后在所有列的位置都不合法，那么上一个皇后的位置不合法，让其继续放置在后一列中，这个过程实现了回溯。如下代码：
3.效果展示
我们这里调最后两种解法实践一下：
4.完整代码
public class Queue8 {
// 皇后的数量
int max = 8;
// 使用一个一维数组来记录 下表i就代表第几行 arr[i] = val val就代表第几列
int[] arr = new int[max];
static int count;
private void print() {
count++;
for (int i = 0; i < max; i++) {
System.out.print(this.arr[i]+" ");
}
System.out.println();
}
public static void main(String[] args) {
Queue8 queue = new Queue8();
queue.check(0);
System.out.println("共"+count+"种解法");
}
/**
* 放置皇后
* @param n 第n个皇后
*/
public void check(int n) {
if (n == 8) { // n=8 说明皇后都已经放好了
print();
return;
}
// 开始放皇后
for (int i = 0; i < max; i++) {
// 每次将第n个皇后放到第 i 列
arr[n] = i;
// 判断将第n个皇后放到第 i 列时，是否冲突
if (judge(n)) {
// 此时说明不冲突 继续放下一个皇后
check(n+1);
}
}
}
/**
* 检查皇后放的位置是否合法
*/
public boolean judge(int n) {
// 判断第n个皇后和前面 n-1个 皇后放置的位置是否冲突
for (int i = 0; i < n; i++) {
// arr[i] == arr[n] 判断第n个皇后是不是和前面第n-1个皇后在一列
// Math.abs(n-i) == Math.abs(arr[n] - arr[i]) 判断第n个皇后 是不是和前n-1个在同一斜线
if (arr[i] == arr[n] || Math.abs(n-i) == Math.abs(arr[n] - arr[i])) {
return false;
}
}
return true;
}
}
|