扫雷器的递归算法未按预期工作

Question

我试图理解递归，因此试图为扫雷游戏编写递归函数。我的程序没有游戏界面，只是为了理解。

这是我的理解：

我有一个给定大小的网格，其中将填充数字。为简单起见，我假设 0 代表我的，网格中的空单元格将由数字 9 表示。这是我的网格：
0 1 9 9 9
1 1 9 9 9
9 9 9 9 9
9 9 9 1 1
9 9 9 1 0

这是我的递归算法。我想我已经设置了正确的边界条件，但看起来像进入无限递归的算法：

基本案例：
如果网格坐标小于 0 即 x<0 或 y<0 或 x> grid.length-1 或 y > grid.length-1
return
其他
如果网格显示的数字不是 0 或 9 ，则显示数字即 grid[x][y]!=0 && grid[x][y]!=9
else 如果grid显示0表示是地雷，则显示Game over
否则
所有周围 8 个单元格的递归情况，因为所有周围单元格都可以安全打开

下面是一些代码来显示我在算法中列出的内容：

public static void playGame(int[][]grid, int x, int y){
        if(x > grid.length-1 || x <0 || y > grid.length-1 || y<0){
            return;
        }else{
            if(grid[x][y] !=0 && grid[x][y]!=9){
                //means this is a valid number to display to user
                System.out.println("opening cell:"+x+","+y+" "+grid[x][y]);
            }else if(grid[x][y] == 0){
                System.out.println("Game over!");
                //might want to show all mine locations
            }else{
                //all 8 cells are safe to open 
                playGame(grid,x-1,y-1); //left
                playGame(grid,x,y-1); //up
                playGame(grid,x,y+1);//down
                playGame(grid,x+1,y);//diagonal
                playGame(grid,x-1,y); //diagonal
                playGame(grid,x+1,y-1);//diagonal
                playGame(grid,x+1,y+1);//right
                playGame(grid,x-1,y+1);//diagonal

            }
        }
    }

我将单元格作为 2,2 传递给了我 java.lang.WhosebugError。有人可以在这里指导我吗？我对算法或递归的理解是否有问题，或者我可能引入了一些错误。我无法发现问题。

Answer 1

grid.lengthreturns数组中元素的总数，不是数组的一个"side"的长度。对于 5x5 数组，您基本上接受 x 和 y 均小于 25 的任何坐标值。

您也无法阻止之前已解决的单元格重新添加到堆栈中——您将所有 8 个单元格都添加进去，而不管它们之前是否已解决。这一直持续到您的堆栈超过可用内存，并且您收到堆栈溢出错误。

Answer 2

根据一般建议，逐句检查在调试器中未按预期工作的代码，然后再解决给定的具体问题始终是个好主意。

您的实施问题似乎是，打开空白字段，您没有跟踪已经访问过的字段。导致问题运行越来越深的递归在相同的两个字段之间振荡。

根据您的示例中的数据，我用十字标记实际访问的字段 x 并在顶部标记调用堆栈以向您展示我在说什么。

让我们从您的示例中给出的单元格 2、2 开始：

playGame(grid, 2, 2)
0 1 9 9 9
1 1 9 9 9
9 9 x 9 9
9 9 9 1 1
9 9 9 1 0

代码将最终调用 playGame(grid,x,y-1); //up

playGame(grid, 2, 2)
  playGame(grid, 2, 1)
0 1 9 9 9
1 1 x 9 9
9 9 9 9 9
9 9 9 1 1
9 9 9 1 0

我们将再次到达 playGame(grid,x,y-1); //up

playGame(grid, 2, 2)
  playGame(grid, 2, 1)
    playGame(grid, 2, 0)
0 1 x 9 9
1 1 9 9 9
9 9 9 9 9
9 9 9 1 1
9 9 9 1 0

由于此字段仍为空，我们再次调用 playGame(grid,x,y-1); //up

playGame(grid, 2, 2)
  playGame(grid, 2, 1)
    playGame(grid, 2, 0)
      playGame(grid, 2, -1)

这次我们将return和playGame(grid,x,y+1); //down调用。

playGame(grid, 2, 2)
  playGame(grid, 2, 1)
    playGame(grid, 2, 0)
     playGame(grid, 2, 1)
0 1 9 9 9
1 1 x 9 9
9 9 9 9 9
9 9 9 1 1
9 9 9 1 0

由于此字段为空调用 playGame(grid,x,y-1); //up 将是下一步

playGame(grid, 2, 2)
  playGame(grid, 2, 1)
    playGame(grid, 2, 0)
      playGame(grid, 2, 1)
        playGame(grid, 2, 0)
0 1 x 9 9
1 1 9 9 9
9 9 9 9 9
9 9 9 1 1
9 9 9 1 0

从现在开始，我们将重复已经观察到的步骤，直到所有堆栈 space 用完：

playGame(grid, 2, 2)
  playGame(grid, 2, 1)
    playGame(grid, 2, 0)
      playGame(grid, 2, 1)
        playGame(grid, 2, 0)
          playGame(grid, 2, 1)
            playGame(grid, 2, 0)
               ...

Answer 3

感谢大家提出建议。在获得一些建议后，算法似乎需要进行一次修改。我们必须确保在访问空单元格后对其进行标记。这将防止算法进入无限递归。
这是更新后的算法和代码，如果您认为有任何改进，请告诉我：
基本情况：
如果网格坐标小于 0 即 x<0 或 y<0 或 x> grid.length-1 或 y > grid.length-1
return
其他
如果网格显示的数字不是 0 或 9 ，则显示数字即 grid[x][y]!=0 && grid[x][y]!=9
else 如果grid显示0表示是地雷，则显示Game over
其他
所有周围 8 个单元的递归案例，因为所有周围的单元都可以安全打开。 "At this point MAKE SURE EACH CELL IS MARKED VISITED"
这是按预期工作的更新代码。

public static void playGame(int[][]grid, int x, int y){
        System.out.println("Currently working with cell :x: "+x +" and y :"+y);
        if(x > grid.length-1 || x <0 || y > grid.length-1 || y<0 ){
            return;
        }
        else{
            if(grid[x][y] !=0 && grid[x][y]!=9) {
                //means this is a valid number to display to user
                System.out.println("opening cell:"+x+","+y+" "+grid[x][y]);
            }else if(grid[x][y] == 0){
                System.out.println("Game over!");
                //might want to show all mine locations
            }else if(grid[x][y] == 9){
                //mark this cell visited.
                grid[x][y] = -1;
                //all 8 cells are safe to open 
                playGame(grid,x-1,y-1); //left
                playGame(grid,x,y-1); //diagonal left
                playGame(grid,x,y+1);
                playGame(grid,x+1,y);
                playGame(grid,x-1,y);
                playGame(grid,x+1,y-1);
                playGame(grid,x+1,y+1);
                playGame(grid,x-1,y+1);

            }
        }
    }

扫雷器的递归算法未按预期工作

Recursive algorithm with Minesweeper not working as expected

algorithm

recursion

minesweeper