java - 迷宫 2D 递归算法死胡同问题

Question

我一直在尝试制作一个可以递归解决迷宫的程序(应该适用于任何迷宫)。该算法的大部分递归都有效，但是当迷宫检查死胡同以及重新路由以找到解决方案(终点)的方法时，代码不起作用。我尝试了多种调试方法，但并没有让我走得太远；我要么收到 StackOverflowError，要么算法会回溯一个位置。

注意二维数组的“字符指示符”:

• '*' = 墙壁
• '#' = 开始
• '$' = 结束
• ' ' = 可能的路径/不是墙壁
• '@' = 路径
• '~' = 死胡同

期望的输出:

Presolved maze:
* * * * * * * * * * 
* # * * * * * * * * 
*   *           * * 
*   *       *   * * 
*       *   *   * * 
* * *       *   * * 
* *     *   *   * * 
* *     *   *     * 
* * * * * * *     * 
*               $ * 
* * * * * * * * * * 

Maze solution:

* * * * * * * * * * 
* # * * * * * * * * 
* @ * @ @ @ @ @ * * 
* @ * @ ~ ~ * @ * * 
* @ @ @ * ~ * @ * * 
* * * ~ ~ ~ * @ * * 
* * ~ ~ * ~ * @ * * 
* * ~ ~ * ~ * @ @ * 
* * * * * * * ~ @ * 
* ~ ~ ~ ~ ~ ~ ~ $ * 
* * * * * * * * * *

以下是仅回溯一个位置的代码:

在此版本中，我尝试在找到可以回溯的位置并返回该位置以回溯并找到解决方案后递归调用

import java.util.*;
public class mazeOG {
    public static void main(String[] args) {
        allocateMaze();
    }
    
    public static void allocateMaze() {
        char[][] mazeArr = {{'*','*','*','*','*','*','*','*','*','*'},//0
                            {'*','#','*','*','*','*','*','*','*','*'},//1
                            {'*',' ','*',' ',' ',' ',' ',' ','*','*'},//2
                            {'*',' ','*',' ',' ',' ','*',' ','*','*'},//3
                            {'*',' ',' ',' ','*',' ','*',' ','*','*'},//4
                            {'*','*','*',' ',' ',' ','*',' ','*','*'},//5
                            {'*','*',' ',' ','*',' ','*',' ','*','*'},//6
                            {'*','*',' ',' ','*',' ','*',' ',' ','*'},//7
                            {'*','*','*','*','*','*','*',' ',' ','*'},//8
                            {'*',' ',' ',' ',' ',' ',' ',' ','$','*'},//9
                            {'*','*','*','*','*','*','*','*','*','*'}};//10
        
        //setting row and col to 0 for display method
        int row = 0;
        int col = 0;
        System.out.println("Presolved maze:");
        displayMaze(mazeArr, row, col); //displays presolved maze
        row = 1;
        col = 1;
        boolean isSolved = false;
        System.out.println("\nMaze solution:");
        algorithm(mazeArr, row, col, isSolved); //create variable for solved maze, sends maze allocation to method that solves the maze
        System.out.println();
        row = 0;
        col = 0;
        displayMaze(mazeArr, row, col); //displays traced + solved maze
    }

    public static void displayMaze(char[][] mazeArr, int row, int col) {
        if (row < mazeArr.length) { //iterate through all (11) rows
            if (col < mazeArr[row].length) { //iterate through all (11) columns
                System.out.print(mazeArr[row][col] + " "); //displays the current index in the array
                displayMaze(mazeArr, row, col+1); //repeats this method by iterating through the columns first
                return;
            }
            System.out.println(); //enters the line after each row for display purposes
            displayMaze(mazeArr, row+1, col=0); //repeats this method by iterating through the rows
        }
    }
    
    public static char[][] algorithm(char[][] mazeArr, int row, int col, boolean isSolved){
        boolean isPath = false; // assume there is no path

        if (mazeArr[row][col] == '$' && isSolved == true) { // IF MAZE IS COMPLETELY SOLVED
            return mazeArr;

        } else { // IF MAZE IS NOT COMPLETELY SOLVED
            
            // start searching thru the maze, assume there is no path
                // THERE IS NO DEAD END
                
                if (mazeArr[row - 1][col] == ' ') { // if north has a path
                    mazeArr[row - 1][col] = '@'; // block off path to not go back here again
                    isPath = true; // there is a path
                    isSolved = false; // assume maze is still not solved
                    
                    return algorithm(mazeArr, --row, col, isSolved); // repeat process going to next north spot
                }
                
                if (mazeArr[row][col + 1] == ' ') { // if east has a path
                    mazeArr[row][col + 1] = '@'; // block off path to not go back here again
                    isPath = true; // there is a path
                    isSolved = false; // assume maze is still not solved

                    return algorithm(mazeArr, row, ++col, isSolved); // repeat process going to next east spot
                }
                
                if (mazeArr[row + 1][col] == ' ') { // if south has a path
                    mazeArr[row + 1][col] = '@'; // block off path to not go back here again
                    isPath = true; // there is a path
                    isSolved = false; // assume maze is still not solved
                    
                    return algorithm(mazeArr, ++row, col, isSolved); // repeat process going to next south spot
                }
                
                if (mazeArr[row][col - 1] == ' ') { // if west has a path
                    mazeArr[row][col - 1] = '@'; // block off path to not go back here again
                    isPath = true; // there is a path
                    isSolved = false; // assume maze is still not solved
                    
                    return algorithm(mazeArr, row, --col, isSolved); // repeat process going to next west spot
                }
                
                if (mazeArr[row][col] == '$') { // if you have reached the end of the maze
                    isSolved = true; // maze has been solved
                    
                    
                    return algorithm(mazeArr, row, col, isSolved); // algorithm will recognize
                }

            // finds alternate path if there's a dead end
                if (mazeArr[row][col] != '#') {
                mazeArr[row][col] = '~'; //indicates that this index is a dead end
                }
                
                if (isPath == false) {
                    if (mazeArr[row - 1][col] == '@' && mazeArr[row - 1][col] != '#') {// if north was a path
                        isPath = true; 
                        isSolved = false; 
                        return algorithm(mazeArr, --row, col, isSolved);//returns to initial position before hitting dead end
                    }
                }
                
                if (isPath == false) {
                    if (mazeArr[row - 1][col] == '@' && mazeArr[row][col+1] != '#') {// if east was a path
                        isPath = true; 
                        isSolved = false; 
                        return algorithm(mazeArr, row, ++col, isSolved);//returns to initial position before hitting dead end
                    }
                }
                
                if (isPath == false) {
                    if (mazeArr[row + 1][col] == '@' && mazeArr[row - 1][col] != '#') {// if south was a path
                        isPath = true; 
                        isSolved = false; 
                        return algorithm(mazeArr, ++row, col, isSolved);//returns to initial position before hitting dead end
                    }
                }
                
                if (isPath == false) {
                    if (mazeArr[row][col-1] == '@' && mazeArr[row - 1][col] != '#') {// if west was a path
                        isPath = true; 
                        isSolved = false; 
                        return algorithm(mazeArr, row, --col, isSolved);//returns to initial position before hitting dead end
                    }
                }
                
                if (isPath == false) { // if there's no way out, that means there is no solution
                    System.out.println("No Solution");              
                    return mazeArr;
                }
                
            return mazeArr;
        }
    }
}

此版本的输出:

Presolved maze:
* * * * * * * * * * 
* # * * * * * * * * 
*   *           * * 
*   *       *   * * 
*       *   *   * * 
* * *       *   * * 
* *     *   *   * * 
* *     *   *     * 
* * * * * * *     * 
*               $ * 
* * * * * * * * * * 

Maze solution:
No Solution

* * * * * * * * * * 
* # * * * * * * * * 
* @ * @ @ @ @ @ * * 
* @ * @     * @ * * 
* @ @ @ *   * @ * * 
* * *       * @ * * 
* *     *   * @ * * 
* *     *   * @ @ * 
* * * * * * * @ @ * 
* ~ @ @ @ @ @ @ $ * 
* * * * * * * * * * 

以下是获取 StackOverflowError 的版本的代码:

在这个版本中，我删除了按位置回溯并递归调用的代码部分，只是表明该位置是死胡同，并递归调用算法来搜索下一个位置。

import java.util.*;

public class maze {
    public static void main(String[] args) {
        allocateMaze();
    }

    public static void allocateMaze() {
        char[][] mazeArr = { { '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' }, // 0
                { '*', '#', '*', '*', '*', '*', '*', '*', '*', '*' }, // 1
                { '*', ' ', '*', ' ', ' ', ' ', ' ', ' ', '*', '*' }, // 2
                { '*', ' ', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 3
                { '*', ' ', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 4
                { '*', '*', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 5
                { '*', '*', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 6
                { '*', '*', ' ', ' ', '*', ' ', '*', ' ', ' ', '*' }, // 7
                { '*', '*', '*', '*', '*', '*', '*', ' ', ' ', '*' }, // 8
                { '*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '$', '*' }, // 9
                { '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' } };// 10

        // setting row and col to 0 for display method
        int row = 0;
        int col = 0;
        System.out.println("Presolved maze:");
        displayMaze(mazeArr, row, col); // displays presolved maze
        row = 1;
        col = 1;
        boolean isSolved = false;
        System.out.println("\nMaze solution:");
        algorithm(mazeArr, row, col, isSolved); // create variable for solved maze, sends maze allocation to method that
                                                // solves the maze
        System.out.println();
        row = 0;
        col = 0;
        displayMaze(mazeArr, row, col); // displays traced + solved maze
    }

    public static void displayMaze(char[][] mazeArr, int row, int col) {
        if (row < mazeArr.length) { // iterate through all (11) rows
            if (col < mazeArr[row].length) { // iterate through all (11) columns
                System.out.print(mazeArr[row][col] + " "); // displays the current index in the array
                displayMaze(mazeArr, row, col + 1); // repeats this method by iterating through the columns first
                return;
            }
            System.out.println(); // enters the line after each row for display purposes
            displayMaze(mazeArr, row + 1, col = 0); // repeats this method by iterating through the rows
        }
    }

    public static char[][] algorithm(char[][] mazeArr, int row, int col, boolean isSolved) {
        boolean isPath = false; // assume there is no path

        if (mazeArr[row][col] == '$' && isSolved == true) { // IF MAZE IS COMPLETELY SOLVED
            return mazeArr;

        } else { // IF MAZE IS NOT COMPLETELY SOLVED

            // start searching thru the maze,
            // assume there is no path
            // THERE IS NO DEAD END

            if (mazeArr[row - 1][col] == ' ') { // if north has a path
                mazeArr[row - 1][col] = '@'; // block off path to not go back here again
                isPath = true; // there is a path
                isSolved = false; // assume maze is still not solved

                return algorithm(mazeArr, --row, col, isSolved); // repeat process going to next north spot
            }

            if (mazeArr[row][col + 1] == ' ') { // if east has a path
                mazeArr[row][col + 1] = '@'; // block off path to not go back here again
                isPath = true; // there is a path
                isSolved = false; // assume maze is still not solved

                return algorithm(mazeArr, row, ++col, isSolved); // repeat process going to next east spot
            }

            if (mazeArr[row + 1][col] == ' ') { // if south has a path
                mazeArr[row + 1][col] = '@'; // block off path to not go back here again
                isPath = true; // there is a path
                isSolved = false; // assume maze is still not solved

                return algorithm(mazeArr, ++row, col, isSolved); // repeat process going to next south spot
            }

            if (mazeArr[row][col - 1] == ' ') { // if west has a path
                mazeArr[row][col - 1] = '@'; // block off path to not go back here again
                isPath = true; // there is a path
                isSolved = false; // assume maze is still not solved

                return algorithm(mazeArr, row, --col, isSolved); // repeat process going to next west spot
            }

            if (mazeArr[row][col] == '$') { // if you have reached the end of the maze
                isSolved = true; // maze has been solved

                return algorithm(mazeArr, row, col, isSolved); // algorithm will recognize
            }

            //code from here and below is for the case of a dead end
            if (mazeArr[row][col] != '#' && isPath == false) {
                mazeArr[row][col] = '~'; // indicates that this index is a dead end
                isPath = true;
                isSolved = false;
                return algorithm(mazeArr, row, col, isSolved);
            }

            if (isPath == false) { // if there's no way out, that means there is no solution
                System.out.println("No Solution");
                return mazeArr;
            }

            return mazeArr;
        }
    }
}

任何帮助都会非常好!谢谢:)

编辑: 修改代码

public static void main(String[] args) {
        int row = 0, col = 0;
        char[][] mazeArr = { { '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' }, // 0
                { '*', '#', '*', '*', '*', '*', '*', '*', '*', '*' }, // 1
                { '*', ' ', '*', ' ', ' ', ' ', ' ', ' ', '*', '*' }, // 2
                { '*', ' ', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 3
                { '*', ' ', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 4
                { '*', '*', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 5
                { '*', '*', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 6
                { '*', '*', ' ', ' ', '*', ' ', '*', ' ', ' ', '*' }, // 7
                { '*', '*', '*', '*', '*', '*', '*', ' ', ' ', '*' }, // 8
                { '*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '$', '*' }, // 9
                { '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' } };// 10

        System.out.println("Input maze:");
        displayMaze(mazeArr, row, col);

        System.out.println("\nMaze solution:");
        boolean isSolved = algorithm(mazeArr);
        if (isSolved) {
            displayMaze(mazeArr, row, col);
        } else {
            System.out.println("No Solution");
        }
    }
    
    public static void displayMaze(char[][] mazeArr, int row, int col) {
        if (row < mazeArr.length) { //iterate through all (11) rows
            if (col < mazeArr[row].length) { //iterate through all (11) columns
                //displays maze without dead end indicators
                if(mazeArr[row][col] == '~') {
                    //mazeArr[row][col] = ' ';
                }
                System.out.print(mazeArr[row][col] + " "); //displays the current index in the array
                displayMaze(mazeArr, row, col+1); //repeats this method by iterating through the columns first
                return;
            }
            System.out.println(); //enters the line after each row for display purposes
            displayMaze(mazeArr, row+1, col=0); //repeats this method by iterating through the rows
        }
    }
    
    
    //indicates starting point for the maze to start solving and recursively calls algorithm method that is overloaded
    //pre: char 2D array mazeArr
    //post: returns a boolean value from the overloaded algorithm method 
    public static boolean algorithm(char[][] mazeArr) {
        int row = 1, col = 1; // where maze starts
            return algorithm(mazeArr, row, col);
    }
    
    //solves the maze looking for a solution (if there is one), modifies the 2D array accordingly 
    //to the algorithm to trace the solution
    //pre: char 2D array mazeArr, int row and col
    //post: returns boolean value depending on the algorithms solution
    public static boolean algorithm(char[][] mazeArr, int row, int col) {
        
        if (mazeArr[row][col] == '$') { // found the target/exit
            return true; //maze is completely solved 
        }
        
        if (mazeArr[row][col] == ' ') { // if there is a path
            mazeArr[row][col] = '@'; //mark as visited, block off path to not go back here again
        } 
        
        else if (mazeArr[row][col] != '#') { // not allowed
            return false;
        }
        // the core of the algorithm: try each direction until true is returned
        
        if (algorithm(mazeArr, row, col - 1) // west
                || algorithm(mazeArr, row - 1, col) // north
                || algorithm(mazeArr, row, col + 1) // east
                || algorithm(mazeArr, row + 1, col) // south
        ) {
            return true; // path found
        }
        
        if (mazeArr[row][col] == '@') { // mark backtracking
            mazeArr[row][col] = '~'; // indicates that this index is a dead end
        }
        
        return false;
        
    }

Answer 1

存在几个问题，包括:

• 死胡同不应触发新的递归调用。死端标记应该在从递归回溯时发生，并且应该向调用者表明没有成功。

• 每个检查特定方向(北、...等)的 if 语句都会在其 block 中执行 return，这意味着 if有这样一个方向，其他方向都不会尝试。

• 由于递归调用不会返回是否成功，调用者无法知道是否应该尝试另一个方向

不是问题，而是:

• 还有相当多的代码重复，您应该避免。
• 没有充分的理由让显示函数递归。只需使用两个 for 循环迭代单元格
• 在主程序中避免使用 row 和 col 变量:这些变量在那里没有任何意义。
• 当你改变迷宫时，应该没有必要返回那个迷宫。调用者可以在调用后以任何方式访问已填充的迷宫。
• 将起点 (#) 的搜索与算法的其余部分分开后，代码会更简单。

成功函数的关键之一是返回一个 boolean 值，指示是否找到路径。这样算法就可以决定是否应该在另一个方向上重试。

这是对代码的修改:

import java.util.*;

public class Main {
    public static void main(String[] args) {
        char[][] mazeArr = { 
                { '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' }, // 0
                { '*', '#', '*', '*', '*', '*', '*', '*', '*', '*' }, // 1
                { '*', ' ', '*', ' ', ' ', ' ', ' ', ' ', '*', '*' }, // 2
                { '*', ' ', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 3
                { '*', ' ', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 4
                { '*', '*', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 5
                { '*', '*', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 6
                { '*', '*', ' ', ' ', '*', ' ', '*', ' ', ' ', '*' }, // 7
                { '*', '*', '*', '*', '*', '*', '*', ' ', ' ', '*' }, // 8
                { '*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '$', '*' }, // 9
                { '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' } };// 10

        System.out.println("Input maze:");
        displayMaze(mazeArr);
        
        System.out.println("\nMaze solution:");
        boolean isSolved = algorithm(mazeArr);
        if (isSolved) {
            displayMaze(mazeArr);
        } else {
            System.out.println("No Solution");
        }
    }

    public static void displayMaze(char[][] mazeArr) {
        for (char[] row : mazeArr) {
            for (char cell : row) {
                System.out.print(cell + " ");
            }
            System.out.println();
        }
    }

    public static boolean algorithm(char[][] mazeArr) {
        // Look for starting point
        for (int row = 0; row < mazeArr.length; row++) {
            for (int col = 0; col < mazeArr[0].length; col++) {
                if (mazeArr[row][col] == '#') {
                    return algorithm(mazeArr, row, col);
                }
            }
        }
        return false; // No starting point found
    }

    public static boolean algorithm(char[][] mazeArr, int row, int col) {
        if (mazeArr[row][col] == '$') { // Found the target
            return true;
        }
        if (mazeArr[row][col] == ' ') {
            mazeArr[row][col] = '@'; // Mark as visited
        } else if (mazeArr[row][col] != '#') { // Not allowed
            return false;
        }
        // The core of the algorithm: try each direction until true is returned
        if (algorithm(mazeArr, row, col - 1) // west
                || algorithm(mazeArr, row - 1, col) // north
                || algorithm(mazeArr, row, col + 1) // east
                || algorithm(mazeArr, row + 1, col) // south
        ) {
            return true; // Path found
        }
        if (mazeArr[row][col] == '@') { // mark backtracking
            mazeArr[row][col] = '~';
        }
        return false;
    }
}

没有循环

从评论中我了解到您不想使用循环。在这种情况下，请使用递归在单独的递归函数中查找起始单元格，并将找到的位置作为单个整数返回 (row*width + col)。

下面是相应的代码:

public class Main {
    public static void main(String[] args) {
        char[][] mazeArr = { 
                { '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' }, // 0
                { '*', '#', '*', '*', '*', '*', '*', '*', '*', '*' }, // 1
                { '*', ' ', '*', ' ', ' ', ' ', ' ', ' ', '*', '*' }, // 2
                { '*', ' ', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 3
                { '*', ' ', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 4
                { '*', '*', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 5
                { '*', '*', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 6
                { '*', '*', ' ', ' ', '*', ' ', '*', ' ', ' ', '*' }, // 7
                { '*', '*', '*', '*', '*', '*', '*', ' ', ' ', '*' }, // 8
                { '*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '$', '*' }, // 9
                { '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' } };// 10

        System.out.println("Input maze:");
        displayMaze(mazeArr);
        
        System.out.println("\nMaze solution:");
        boolean isSolved = algorithm(mazeArr);
        if (isSolved) {
            displayMaze(mazeArr);
        } else {
            System.out.println("No Solution");
        }
    }

    public static void displayMaze(char[][] mazeArr) {
        displayMaze(mazeArr, 0, 0); // add the arguments
    }
    
    public static void displayMaze(char[][] mazeArr, int row, int col) {
        if (row >= mazeArr.length) {
            return; // all done
        }
        if (col >= mazeArr[0].length) {
            System.out.println();
            displayMaze(mazeArr, row + 1, 0);
        } else {
            System.out.print(mazeArr[row][col] + " ");
            displayMaze(mazeArr, row, col + 1);
        }
    }

    public static int findStart(char[][] mazeArr, int i) {
        // Look for starting point. i is combination of row/col
        int row = i / mazeArr.length;
        if (row >= mazeArr.length) {
            return -1; // all done, and not found
        }
        int col = i % mazeArr[0].length;
        if (mazeArr[row][col] == '#') {
            return i; // found it
        }
        return findStart(mazeArr, i + 1);
    }

    public static boolean algorithm(char[][] mazeArr) {
        int i = findStart(mazeArr, 0);
        if (i == -1) {
            return false; // No starting point found
        }
        int row = i / mazeArr.length;
        int col = i % mazeArr[0].length;
        return algorithm(mazeArr, row, col);
    }

    public static boolean algorithm(char[][] mazeArr, int row, int col) {
        if (mazeArr[row][col] == '$') { // Found the target
            return true;
        }
        if (mazeArr[row][col] == ' ') {
            mazeArr[row][col] = '@'; // Mark as visited
        } else if (mazeArr[row][col] != '#') { // Not allowed
            return false;
        }
        // The core of the algorithm: try each direction until true is returned
        if (algorithm(mazeArr, row, col - 1) // west
                || algorithm(mazeArr, row - 1, col) // north
                || algorithm(mazeArr, row, col + 1) // east
                || algorithm(mazeArr, row + 1, col) // south
        ) {
            return true; // Path found
        }
        if (mazeArr[row][col] == '@') { // mark backtracking
            mazeArr[row][col] = '~';
        }
        return false;
    }
}