Issue with implemented Minesweeper algorithm

Question

So I'm attempting to learn Python by way of Minesweeper. I've got experience with SDL, so I figured playing around with PyGame sounded like a fun way to learn the syntax of the language.

Anywho, I'm having an issue in uncovering adjacent open squares as you would in a normal game of Minesweeper. I click on a cell with 0 neighboring mines, and attempt to scan the top, left, right, and bottom to see if those also have 0 neighboring mines, and I do this recursively.

Here is the error that I receive:

RuntimeError: maximum recursion depth exceeded in cmp

And here is my algorithm:

#open up blank mines
def open_blank_cells(mines, cr, cc):
  #top
  if (cr > 0):
    t_mine = mines[cr-1][cc]
    t_mine.switch_state(3)
    if (t_mine.neighbor_mines == 0):
      open_blank_cells(mines, cr-1, cc)

  #right
  if (cc < 9):
    r_mine = mines[cr][cc+1]
    r_mine.switch_state(3)
    if (r_mine.neighbor_mines == 0):
      open_blank_cells(mines, cr, cc+1)

  #bottom
  if (cr < 9):
    r_mine = mines[cr+1][cc]
    r_mine.switch_state(3)
    if (r_mine.neighbor_mines == 0):
      open_blank_cells(mines, cr+1, cc)

  #left
  if (cc > 0):
    l_mine = mines[cr][cc-1]
    l_mine.switch_state(3)
    if (l_mine.neighbor_mines == 0):
      open_blank_cells(mines, cr, cc-1)

  return

where mines is my 2D array of cells, cr is the index of the current row (first array index), and cc is the index of the current column (second array index).

I thought that my algorithm was decently solid (but please tell me if I'm wrong there!!!), so I turned to the Internet and found that the default Python recursion limit of 1000 could be to blame. However, when I bump it higher with the call to sys.setrecursionlimit the game either exhibits the same behavior, or simply crashes as the system kills it.

When I comment out 2 of the 4 recursive checks in the function, it will open up blank cells without any problem. 3 or more however breaks the algorithm.

---

Edit

As requested....

Calculation of neighbor_mines

# if not a mine, figure out how many surround it
  for i in xrange(10):
    for j in xrange(10):
      if (mines[i][j].is_mine == False):
        #check top 3
        if (i > 0):
          if (j > 0):
            if (mines[i-1][j-1].is_mine == True):
              mines[i][j].neighbor_mines += 1


          if (mines[i-1][j].is_mine == True):
            mines[i][j].neighbor_mines += 1

          if (j < 9):
            if (mines[i-1][j+1].is_mine == True):
              mines[i][j].neighbor_mines += 1

        #check left and right
        if (j > 0):
          if (mines[i][j-1].is_mine == True):
            mines[i][j].neighbor_mines += 1

        if (j < 9):
          if (mines[i][j+1].is_mine == True):
            mines[i][j].neighbor_mines += 1

        #check bottom 3
        if (i < 9):
          if (j > 0):
            if (mines[i+1][j-1].is_mine == True):
              mines[i][j].neighbor_mines += 1

          if (mines[i+1][j].is_mine == True):
            mines[i][j].neighbor_mines += 1

          if (j < 9):
            if (mines[i+1][j+1].is_mine == True):
              mines[i][j].neighbor_mines += 1

Switch_state

 def switch_state(self, newstate):
    self.state = newstate

    #marked as mine
    if (newstate == 1):
      nf = "sq_mine_marked.png"
    elif (newstate == 2):
      nf = "sq_mine_question.png"
    elif (newstate == 3):
      nf = "sq_mine_open.png"
    elif (newstate == 4):
      nf = "sq_mine_mine.png"
    else:
      nf = "sq_mine.png"

    oldrect = self.rect #save old rect as load_image overwrites it
    self.image, self.rect = load_image(nf, (255,0,255))
    self.rect = oldrect

Answer 1

Imagine the following setup:

1 1 1 1 1 1 
1 0 0 0 0 1
1 0 0 0 0 1
1 0 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

As a side note, I refer to squares in the matrix like this: (row, column). I've represented mines with "1" and empty spaces with "0". Assume the user clicks on the empty space at (2, 2) (the corner at the top-left is (0, 0)).

This is what would happen:

• the square at (2, 3) is empty and has no adjacent mines. Let's call our function for those coordinates
• in the new function call we notice that (3, 3) is empty and has no adjacent mines, let's call the function for that space as well
• (3, 2) is a valid place too, let's call again
• in the fourth call we'll notice that (2, 2) is empty and has no nearby mines, so we're back at square one, thus creating an endless loop

Any adjacent squares that each do not have adjacent mines will create an endless loop once your recursive function is called for either of them. Simply putting in a condition to not call the function again for the square you just came from wouldn't have been enough, as can be seen in the example above.

One solution is to create another matrix that can show what squares have already been visited. If the current square has already been visited, return from the function immediately. Otherwise, mark is as a visited square and carry on with your usual code.