Java通过递归算法解决迷宫与汉诺塔及八皇后问题

//一个7列8行的迷宫

//分析

//1.我们用一个二维数组来表示迷宫

//2.定义一个findWay方法来找路径，返回值为布尔类型，

//3.若找到路则返回true，否则返回false。

//4.我们用1来表示障碍物

//5.我们初始化老鼠当前坐标(1,1)

//6.用0表示能走，1表示不能走，2表示走过能走，3表示走过但走不通

//7.当map[6][5]=2时则说明找到了出迷宫的路，否则继续找路

//8.我们定义一个试探走的规则，我们假设 下->右->上->左

public class MiGong{

    public   static void main(String [] args){

    //迷宫初始化

    int [][] map = new int [ 8 ][ 7 ];

    for ( int i = 0 ; i < 7 ; i++){

    map[ 0 ][i] = 1 ;

    map[ 7 ][i] = 1 ;

    }

  for ( int j = 0 ; j < 8 ; j++){

    map[j][ 0 ] = 1 ;

    map[j][ 6 ] = 1 ;

    }

    map[ 3 ][ 1 ]= 1 ;

    map[ 3 ][ 2 ]= 1 ;

    for ( int k = 0 ; k < map.length; k++) {

     for ( int m = 0 ; m < map[k].length; m++){

         System.out.print(map[k][m] + " " );

     }

     System.out.println();

    }

    t way = new t();

    way.findWay(map, 1 , 1 );

    System.out.println( "=====找到路径后的地图=====" );

     for ( int k = 0 ;k < map.length; k++) {

       for ( int m = 0 ;m < map[k].length; m++){

          System.out.print(map[k][m] + " " );

       }

       System.out.println();

    }

}

}

class t{

     public boolean findWay( int [][] map , int x , int y){

      if (map[ 6 ][ 5 ]== 2 ){ //递归出口若终点处的值为2则表明能找到一条路

       return true ;

      } else {

       if (map[x][y]== 0 ){ //首先若当前位置为0，则表明可以走

          map[x][y]= 2 ; //我们假设选这条路可以走通，将当前位置赋为2

          //然后按照我们的试探规则依次试探下->右->上->左

          if (findWay(map, x+ 1 , y)) //递归调用findway函数如果下可以走则返回true

             return   true ;

          else if (findWay(map, x, y+ 1 )) //否则还继续看右边能不能走

               return true ;

          else if (findWay(map, x- 1 , y)) //上

                return true ;

          else if (findWay(map, x, y- 1 )) //左

                return true ;

          else {

                map[x][y]= 3 ;

                return false ;

              }     

       } else // map[x][y]=1,2,3

           return false ;

   }

  }

}

import java.util.Scanner;

public class HanoiTower{

     public static void main(String []args ){

     System.out.println( "请输入你要移动的盘数：" ); 

     tower m = new tower();

Scanner input = new Scanner(System.in);

     int num = input.nextInt();

     m.moveWay(num, 'A' , 'B' , 'C' );

     }

}

class tower{

     //num表示要移动的盘的个数，a,b,c分别表示a塔，b塔，c塔

     public void moveWay( int num, char a, char b, char c){

         if (num == 1 ){ //如果只有一个盘，直接将其从a移动到c

             System.out.println(a + "->" + c);

         }

         else { //如果有多个盘将最后一个盘以上的盘看成一个整体，借助c，移动到b，然后将最后一个盘移到c

             moveWay(num- 1 , a, c, b);

             System.out.println(a + "->" + c);

             //然后再将b的所有盘，借助a，移动到c

             moveWay(num- 1 , b, a, c);

         }

     }

}

public class Queen8{

//第一个皇后先放在第一行第一列

//第二个放在第二行第一列，然后判断是否发生冲突

//如果冲突，则继续放第二列，第三列，依次直到找到不发生冲突的位置

//第三个皇后，还是按照第二个一样依次找直到第八个皇后也能放在一个不发生冲突的地方，就算找到一个可行解。

//当得到一个可行解时，回退到上一个栈开始回溯，既可以得到第一个皇后放在第一列的所有可行解

//然后回头继续第一个皇后放在第二列，重复前面的操作

//用一个一维数组来表示皇后放置的位置

//列如arry[1]=3,表示第二个皇后放在第二行第四列

    int max = 8 ;

    int [] arry = new int [max];

    static int count = 0 ;

  public static void main(String[]args){

     Queen8 queen8 = new Queen8();

     queen8.locate( 0 );

     System.out.print( "摆法一共有：" + count + "种" );

  }

// 依次放入皇后，并判断是否冲突

public void locate( int n){

     if (n == max){

         display();

         return ;

     }

     for ( int i = 0 ; i < max; i++){

     //先把皇后n放到第一列

      arry[n] = i;

      if (judge(n)){ //不冲突则继续放置第n+1个皇后

         locate(n+ 1 );

      }

      //如果冲突则继续往后一列放置

     }

}

  public boolean judge( int n){

     for ( int i = 0 ; i < n; i++){

         //arry[i]==arry[n]表示在同一列

         //Math.abs(i-n)==Matn.abs(arry[i]-arry[n])表示在同一斜线

         if (arry[i] == arry[n] || Math.abs(i - n) == Math.abs(arry[i] - arry[n])){

             return false ;

         }

     }

     return true ;

  }

  public void display(){

     count++;

     for ( int i = 0 ; i < arry.length; i++){

     System.out.print(arry[i]+ " " );

     }

     System.out.println();

  }

}