DFS 迷宫求解器 returns 正确时为 false

Question

我目前正在研究一个小迷宫求解器项目，以更好地掌握深度优先搜索等算法。它的工作原理是将当前位置变为 2，然后检查其中一个位置（上、下、左或右）是否为 0（路径），并且它将向前移动，直到它被 1s（墙）的单元格包围，然后它是一个死胡同，它回溯。

然而，我的迷宫解算器奇怪地保持 returning 错误，即使它已经找到了数字 3（结束）。所以我有两个问题，是什么导致它 return false 以及可以在求解器中更改什么以便只有最短路径的数字为 2（即当它回溯时它会将死胡同路径变成其他）？

提前致谢！

迷宫求解器

public class DFS {
    
    private int[][] maze;
    
    public DFS(int[][] maze) {
        
        this.maze = maze;
    }
    
    // Solves given maze recursively, input starting position in maze.
    public boolean solve(int x, int y) {
        
        maze[x][y] = 2;
        
        // 3 is the cell the algorithm is supposed to find.
        if (maze[x][y] == 3) {
            return true;
        }
        
        // Looks up.
        if (x > 0 && maze[x-1][y] == 0  && solve (x-1, y) ) {
            maze[x][y] = 2;
            return true;
        }
        // Looks down
        if (x < maze.length && maze[x+1][y] == 0  && solve (x+1, y) ) {
            maze[x][y] = 2;
            return true;
        }
        // Looks right.
        if (y < maze.length && maze[x][y+1] == 0  && solve (x, y+1) ) {
            maze[x][y] = 2;
            return true;
        }
        // Looks left.
        if (y > 0 && maze[x][y-1] == 0  && solve (x, y-1) ) {
            maze[x][y] = 2;
            return true;
        }
        
        return false;
    }
    
}

硬编码迷宫

import java.util.ArrayList;

public class TestMazeDFS {
    private static int[][] maze = {
            {1, 1, 1, 1, 1, 1, 1, 1, 1},        
            {1, 0, 0, 0, 0, 0, 0, 0, 1},
            {1, 0, 1, 0, 1, 1, 1, 1, 1},
            {1, 0, 1, 0, 0, 0, 0, 0, 1},
            {1, 1, 1, 1, 1, 0, 1, 0, 1},
            {1, 0, 0, 0, 1, 0, 1, 0, 1},
            {1, 0, 1, 1, 1, 1, 1, 0, 1},
            {1, 0, 0, 0, 0, 0, 0 ,0, 1},
            {1, 1, 1, 1, 1, 1, 1, 3, 1},
        };
    
    public int[][] getMaze(){
        
        return this.maze;
    }
    
    public static void main(String[] args) {
        
        DFS dfs = new DFS(maze);
        boolean test = dfs.solve(1, 1);
        System.out.println(test);
        
    }
}

打印时的解决方案图像。 https://imgur.com/a/UqHP81o

Answer 1

快速浏览一下就知道你做错了：

        maze[x][y] = 2;
        
        // 3 is the cell the algorithm is supposed to find.
        if (maze[x][y] == 3) { // <-- It will never be 3
            return true;
        }

同样在每个 if-check 中：if (x > 0 && maze[x-1][y] == 0 && solve (x-1, y) ) {，您只访问值为 0 的邻居。因此，出于显而易见的原因，您永远不会访问值为 3 的单元格。 if-check 应该是这样的：if (x > 0 && (maze[x-1][y] == 0 || maze[x-1][y] == 3) && solve (x-1, y) ) {

并且注意回溯的时候，需要将状态恢复到原来的状态。也就是说，当您返回 false 时，maze[x][y] 应该具有原始值。

也许试试这个？

    public boolean solve(int x, int y) {
        // 3 is the cell the algorithm is supposed to find.
        if (maze[x][y] == 3) {
            maze[x][y] = 2;
            return true;
        }

        int orig = maze[x][y];
        maze[x][y] = 2;
        
        // Looks up.
        if (x > 0 && (maze[x-1][y] == 0 || maze[x-1][y] == 3)  && solve (x-1, y) ) {
            //maze[x][y] = 2;
            return true;
        }
        // Looks down
        if (x < maze.length && (maze[x+1][y] == 0 || maze[x+1][y] == 3)  && solve (x+1, y) ) {
            //maze[x][y] = 2;
            return true;
        }
        // Looks right.
        if (y < maze.length && (maze[x][y+1] == 0 || maze[x][y+1] == 3)  && solve (x, y+1) ) {
            //maze[x][y] = 2;
            return true;
        }
        // Looks left.
        if (y > 0 && (maze[x][y-1] == 0 || maze[x][y-1] == 3)  && solve (x, y-1) ) {
            //maze[x][y] = 2;
            return true;
        }

        maze[x][y] = orig;
        return false;
    }

工作解决方案：https://onlinegdb.com/ryxoPKgCaw

DFS 迷宫求解器 returns 正确时为 false

DFS Maze Solver returns false when correct

java

algorithm

maze

depth-first-search

recursive-backtracking