Java递归实现迷宫问题和八皇后
Java递归
- 递归
- 1.概念
- 2.规则
- 迷宫问题
- 1.思路分析
- 2.代码实现
- 3.运行结果
- 八皇后问题
- 1.概念
- 2.思路分析
- 3.代码实现
- 4.结果
递归
1.概念
简单来说：递归就是方法自己调用自己，每次调用时传入不同的变量，递归有助于编程者解决复杂的问题，同时可以让代码变得简洁
2.规则
-
每当方法被调用，就会开辟一个独立空间
-
方法的变量是独立的，不会相互影响的
-
如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据
-
递归必须向退出递归的条件逼近，否则就是无限递归，出现 StackOverflowError
-
当一个方法执行完毕，或者遇到 return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕
迷宫问题
1.思路分析
1、如果小球能到map[6][5]那么就代表通关的路找到了
2、规则：
- 当map[i][j] = 0 表示这个点没走过
- 当map[i][j] = 1 表示这个点不能走被挡住了
- 当map[i][j] = 2 表示可以走
- 当map[i][j] = 3 表示该位置已经走过，但是走不通
3、走的时候需要一个策略，下->右->上->左
2.代码实现
package com.sky.recursion;
/**
* @author 尹稳健~
* @version 1.0
* @time 2022/8/30
*/
public class MiGong {
public static void main(String[] args) {
//初始化地图
int row = 8;
int column = 7;
int[][] map = getMap(row, column);
// 设置挡板
map[3][1] = 1;
map[3][2] = 1;
map[1][2] = 1;
map[2][2] = 1;
System.out.println("===========开始跑图===========");
getWay(map,1,1);
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[i].length; j++) {
System.out.print(map[i][j]+" ");
}
System.out.println();
}
}
/**
* 初始化地图 , 二维数组中为 1 说明被挡住了
* @param row 有多少行
* @param column 有多少列
* @return
*/
public static int[][] getMap(Integer row,Integer column){
int[][] map = new int[row][column];
for (int i = 0; i< row; i++){
map[i][0] = 1;
map[i][6] = 1;
}
for (int i = 0; i < column; i++) {
map[0][i] = 1;
map[7][i] = 1;
}
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[i].length; j++) {
System.out.print(map[i][j]+" ");
}
System.out.println();
}
return map;
}
/**
* 找到出迷宫的路
* 说明：
* 1、如果小球能到map[6][5]那么就代表通关的路找到了
* 2、规则：当map[i][j] = 0 表示这个点没走过
* 当map[i][j] = 1 表示这个点不能走被挡住了
* 当map[i][j] = 2 表示可以走
* 当map[i][j] = 3 表示该位置已经走过，但是走不通
* 3、走的时候需要一个策略，下->右->上->左
* @param map 地图
* @param i 坐标起点
* @param j 坐标起点
* @return true代表找到了，false代表没找到
*/
public static boolean getWay(int[][] map,int i, int j){
// 到达终点
if (map[6][5] == 2){
return true;
}else{
// 当该点等于0时，说明这个点还没走过，我们可以假设他走的通
if (map[i][j] == 0){
// 假设当前点可以走
map[i][j] = 2;
// 先向下走
if (getWay(map,i+1,j)){
return true;
// 向右走
}else if (getWay(map,i,j+1)){
return true;
// 向上走
}else if (getWay(map,i-1,j)){
return true;
// 向左走
}else if (getWay(map,i,j-1)){
return true;
}else{
// 上下左右都走不通
map[i][j] = 3;
return false;
}
}else{
// 当判断到达这里时，说明该点是 1 或 2 或 3
return false;
}
}
}
}
3.运行结果
1 1 1 1 1 1 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1
===========开始跑图===========
1 1 1 1 1 1 1
1 2 0 0 0 0 1
1 2 2 2 0 0 1
1 1 1 2 0 0 1
1 0 0 2 0 0 1
1 0 0 2 0 0 1
1 0 0 2 2 2 1
1 1 1 1 1 1 1
八皇后问题
1.概念
八皇后问题（英文：Eight queens），是由国际象棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。
问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。
2.思路分析
- 将第一个皇后放在第一行第一列
- 将第二个皇后放在第二行第一列，判断是否会和其他皇后在同一行或同一列或在同一斜线，如若在，那么将其放在第二列、第三列依次。。。直到不相互攻击
- 将第三个皇后放在第三行第一列，判断是否会和其他皇后相互攻击，如果相互攻击，将其放在第二列，第三列、第四列等等，以此类推，在摆放的过程中，有可能会改动前面所放皇后的为止（回溯）
- 当得到一个正确的解时，就会回溯到上一行，由此来找出第一个皇后在第一行第一列的所有解
- 再将抵押给皇后放在第一行第二列，并重复以上步骤
- 注意：
- 棋盘本身应该时二维数组组成，但因为皇后所在的行数时固定的，那么可以简化为一个一维数组，其中的值表示皇后所在的列
- 数组下表代表皇后所在行数+1，所以判断是否时，只需要判断是否在同一列和同一斜线即可
- 是否同列：值是否相同
- 是否同一斜线： 行号 - 行号 是否等于 列号 - 列号 ，且列号相减要取绝对值
3.代码实现
package com.sky.recursion;
/**
* @author 尹稳健~
* @version 1.0
* @time 2022/8/30
*/
public class Queue8 {
/** 统计有多少种摆法 */
static int num = 0;
/** 一共八个皇后 */
static int max = 8;
/** 摆放位置 索引下标 + 1 代表 第几行 索引值代表 第几列 */
static int[] arr = new int[max];
public static void main(String[] args) {
check(0);
System.out.println("一共有"+num+"种");
}
/** 打印 */
public static void print(){
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+"");
}
System.out.println();
num ++;
}
/** 判断当前皇后是否会和之前按的皇后相互攻击 */
public static boolean judge(int position){
for (int i = 0; i < position; i++) {
/**
* 如果两个皇后在同一列就冲突
* 同一斜线也冲突，索引下标代表行
* 行号 - 行号 == 列号 - 列号 那么就是在同一斜线上
*/
if (arr[i] == arr[position] || position-i == Math.abs(arr[position] - arr[i])){
return false;
}
}
return true;
}
/** 检查皇后应放的位置 */
public static void check(int queue){
// 如果达到8那么就代表已经填满了
if (queue == max){
print();
return;
}
// 把皇后放在每一列上，判断是否会和之前放置的起冲突
for (int i = 0; i < max; i++) {
// 每次都是从第queue行第一列开始
arr[queue] = i;
if (judge(queue)){
// 不冲突，放下一个皇后
check(queue+1);
}
// 如果冲突了，那么就会往后移一位，就相当于列+1，如果后面的行都冲突就会回溯
}
}
}
4.结果
一共92种