遞歸迷宮求解器問題

Question

我正在製作一個遞歸Java迷宮程序，當涉及到調用我的子程序goNorth(),goWest(),goEast()和goSouth()時，我被卡在部件上。基本上我的問題涉及這樣一個事實，即它調用一個子例程，但在該子例程中，它不會接受我的其他else和else語句，因此不會使它接受其他可能性。請協助，我感謝您即將到來的答案。

import java.util.*; 
import java.io.*; 

public class RecursiveMazeSolverv2 { 

    static Scanner in; 
    static int row = 0; 
    static int col = 0; 
    static char maze[][]; 
    static int rowSize = 0; 
    static int colSize = 0; 
    static boolean success = true; 

    public static void main(String[] args) { 

    while (true) { 
     try { 
     in = new Scanner(new File("Maze1.txt")); 
     break; 
     } 
     catch (FileNotFoundException e) { 
     System.out.println("Wrong File"); 
     } 
    } 
    rowSize = Integer.parseInt(in.nextLine()); 
    colSize = Integer.parseInt(in.nextLine()); 

    maze = new char[rowSize][colSize]; 

    String lineOfInput = ""; 
    for (int i = 0; i < maze.length; i++) { 
     lineOfInput = in.nextLine(); 
     for (int j = 0; j < maze.length; j++) { 
     maze[i][j] = lineOfInput.charAt(j); 
     } 
    } 

    displayGrid(); 

    for (int i = 0; i < maze.length; i++) { 
     for (int j = 0; j < maze.length; j++) { 
     if (maze[i][j] == 'S') { 
      maze[i][j]='+'; 
      System.out.println("Starting coordinates: " + i + ", " + j); 
      row = i; 
      col = j; 
     } 
     } 
    } 

if (goNorth(row, col)) 
    displayGrid(); 
else 
    System.out.println("Impossible!"); 
    } 


    static Boolean goNorth(int row, int col) { 
    if (maze[row][col] == '.') { 
     maze[row][col] = '+'; 
     return goNorth(row -1, col); 
    } 

    else if (maze[row][col] == 'G') { 
     return true; 
    } 

    else { 
     success = goNorth(row, col); 
     if (success == false) { 
     success = goWest(row, col -1); 
     } 
     if (success == false) { 
     success = goEast(row, col +1); 
     } 
     if (success == false) { 
     success = goSouth(row +1, col); 
     } 
     if (success == false) { 
     maze[row][col] = '.'; 
     success = false; } 
     return false; 
    } 

    } 
    static Boolean goWest(int row, int col) { 
    if (maze[row][col] == '.') { 
     maze[row][col] = '+'; 
     return goWest(row, col -1); 
    } 

    else if (maze[row][col] == 'G') { 
     return true; 
    } 

    else { 
    success = goWest(row, col); 
     if (success == false) { 
     success = goNorth(row -1, col); 
     } 
     if (success == false) { 
     success = goSouth(row +1, col); 
     } 
     if (success == false) { 
     success = goEast(row, col -1); 
     } 
     if (success == false) { 
     maze[row][col] = '.'; 
     success = false; } 
     return false; 
    } 

    } 

    static Boolean goEast(int row, int col) { 
    if (maze[row][col] == '.') { 
     maze[row][col] = '+'; 
     return goEast(row, col +1); 
    } 

    else if (maze[row][col] == 'G') { 
     return true; 
    } 

    else { 
    success = goEast(row, col); 
     if (success == false) { 
     success = goNorth(row -1, col); 
     } 
     if (success == false) { 
     success = goSouth(row +1, col); 
     } 
     if (success == false) { 
     success = goWest(row, col -1); 
     } 
     if (success == false) { 
     maze[row][col] = '.'; 
     success = false; } 
     return false; 
    } 

    } 


    static Boolean goSouth(int row, int col) { 
    if (maze[row][col] == '.') { 
     maze[row][col] = '+'; 
     return goSouth(row +1, col); 
    } 

    else if (maze[row][col] == 'G') { 
     return true; 
    } 

    else { 
    success = goSouth(row, col); 
     if (success == false) { 
     success = goNorth(row -1, col); 
     } 
     if (success == false) { 
     success = goWest(row, col -1); 
     } 
     if (success == false) { 
     success = goEast(row, col +1); 
     } 
     if (success == false) { 
     maze[row][col] = '.'; 
     success = false; } 
     return false; 
    } 

    } 

    public static void displayGrid() { 
    for (int j = 0; j < maze.length; j++) { 
     for (int k = 0; k < maze.length; k++) { 
     System.out.print(maze[j][k] + " "); 
     } 
     System.out.println(); 
    } 
    } 
} 

對不起，我不能在這裏發佈實際的迷宮，它不會顯示正確。

Answer 1

問題，我看到：

1. 正如其他人躲避到，你不應該讓一切static。沒有進入一個超長和無聊的討論，使所有的東西static意味着你在遞歸調用中設置的值將修改所有調用的值。您正在使用後續遞歸調用中設置的值有效地覆蓋每個遞歸調用。您將希望使這些方法範圍的變量中的大部分變量，以便該值僅在該方法調用的範圍內有效。
2. 遞歸調用的順序不同。您需要每次在同一步驟中執行相同的呼叫：先嚐試北，然後嘗試南，然後嘗試東，然後嘗試西。無論您選擇什麼命令，呼叫都需要按照相同的順序。事實上，我不確定爲什麼你決定爲每個方向分別使用不同的方法......爲什麼不能有一種方法稱爲「移動」，它嘗試去北方，然後遞歸，然後嘗試去南方，然後遞歸，然後嘗試去東和遞歸，然後西和遞歸。你編寫代碼的方式，並不知道代碼將在迷宮中的哪個位置出現，而且很可能你最終會繞着圈子走。
3. 這並不直接與它爲什麼不起作用直接相關，但你真的需要處理你的代碼格式，特別是你的tab鍵。你的代碼看起來像遍佈整個地方。我只能想象，這使得它很難解決它需要的。

編輯 - 舉例

我會盡力做到這一點的方式來指導你不給你複製/粘貼答案，所以這將是僞code'ish。

/** 
* My move recursion 
*/ 
public boolean move(int currRow, int currCol) { 
    // See if we solved it... 
    if (solved) { 
    return true; 
    } 

    // Try to go north first... 
    if (maze[currRow-1][currCol] == '.') { 
    if (move(int currRow-1, currCol)) { 
     // Mark this with the "good" path and return true 
    } 
    } 

    // Try to go east next... 
    if (maze[currRow][currCol+1] == '.') { 
    if (move(int currRow, currCol+1)) { 
     // Mark this with the "good" path and return true 
    } 
    } 

    // Try to go south next... 
    if (maze[currRow+1][currCol] == '.') { 
    if (move(int currRow+1, currCol)) { 
     // Mark this with the "good" path and return true 
    } 
    } 

    // Try to go west... 
    if (maze[currRow][currCol-1] == '.') { 
    if (move(int currRow, currCol-1)) { 
     // Mark this with the "good" path and return true 
    } 
    } 

    return false; 
} 

所以，基本上我們檢查，如果我們 「解決」。如果不是，看看我們是否可以北上。如果可以的話，看下一個通話是否已經解決。重複東，南，西。最終其中一個遞歸調用將達到解決的條件，這將觸發每個遞歸調用來傳遞內部if，這將標記迷宮並返回true，從而創建一個連鎖反應，最終彈出備份調用堆棧直到你完成了遞歸。

事情遞歸注意：

1. 它通常需要一個過程，可以分解成一個或多個可重複的，自主的步驟。這並不意味着它必須是一種方法，但如果它是多種方法，您必須按照相同的順序在方法內執行某些操作。否則，你的邏輯不同步。
2. 當您可以將「步驟」分解爲最小的，最卑鄙的部分時，它通常效果最佳。過於複雜的遞歸方法使得難以進行調試以及大量瘋狂的分支和循環。
3. 你必須有一個非常清晰的「結束」，否則你會緩慢的，直到你吹了堆棧。
4. 「方法級別」的變量/數據/信息和「全局」的應該有非常明顯的區別。就你而言，迷宮是全球性的，成功和現在的位置不是。