Recursive algorithm with Minesweeper not working as expected

Question

I am trying to understand recursion and so was trying to write a recursive function for the minesweeper game. My program has no game interface as it is just for the purpose of understanding.

Here is my understanding:

I have a grid of given size which will be filled with numbers. For simplicity I have assumed that the 0 will represent mine and an empty cell in grid will be represented by digit 9. Here is my grid:
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

Here is my recursive algorithm. I think I have put in the right boundary conditions but seems like the algorithm that goes into infinite recursion:

Base case:
IF the grid coordinates are less than 0 i.e x<0 OR y<0 OR x> grid.length-1 OR y > grid.length-1
return
ELSE
If the grid shows a number other than 0 or 9 , display the number i.e. grid[x][y]!=0 && grid[x][y]!=9
else If grid shows 0 that means it is a mine, display Game over
else
Recursive cases for all surrounding 8 cells as all surrounding cells are safe to open

Here is some code to show what I have listed in the algorithm:

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

            }
        }
    }

I passed the cell as 2,2 and it gives me java.lang.StackOverflowError. Can someone please guide me here. Is there a problem with my understanding on the algorithm or recursion or there is some bug that I have may have introduced. I am unable to spot the problem.

Answer 1

Thanks everyone for providing suggestions. After getting few suggestions it seems like the algorithms needs a single modification. We must ensure that we flag the empty cell once it is visited. This will prevent the algorithm to go into infinite recursion.
Here is the Updated Algorithm and the code, Please let me know if you think there can be any improvements:
Base case:
IF the grid coordinates are less than 0 i.e x<0 OR y<0 OR x> grid.length-1 OR y > grid.length-1
return
ELSE
If the grid shows a number other than 0 or 9 , display the number i.e. grid[x][y]!=0 && grid[x][y]!=9
else If grid shows 0 that means it is a mine, display Game over
else
Recursive cases for all surrounding 8 cells as all surrounding cells are safe to open. "At this point MAKE SURE EACH CELL IS MARKED VISITED"
Here is the updated code which works as expected.

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

            }
        }
    }

Answer 2

After the general advice, that it is always a good idea to step through code not working as expected in a debugger, on to the specific question given.

The problem with your implementation seems to be, that opening up empty fields, you don't keep track of fields already visited. Leading to the problem of running deeper and deeper in recursion oscillating between the same two fields.

Given the data from your example I marked the field actually visited with a cross x and the call stack on top to show you, what I am talking about.

Let's start with the cell 2, 2 as given in your emample:

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

code will end up calling 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

again we will reach 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

As this field is still empty we get another call to playGame(grid,x,y-1); //up

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

This time we will return and playGame(grid,x,y+1); //down will be called.

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

As this field is empty calling playGame(grid,x,y-1); //up will be the next step

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

From now on we will repeat the steps already observed until all stack space is used up:

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

grid.length returns the total number of elements in the array, not the length of one "side" of the array. For a 5x5 array, you are basically accepting any value of coordinates where both x and y are less than 25.

You also have no way to prevent a previously solved cell from getting readded to the stack -- you add all 8, regardless of whether they were previously solved at all. This continues until your stack exceeds available memory, and you get a stack overflow error.