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();
 }
}