# Issue with implemented Minesweeper algorithm

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.rect = oldrect

• Could you show code for neighbor_mines and switch_state? – CiscoIPPhone Aug 12 '11 at 12:58
• sure, no problem – the_e Aug 12 '11 at 13:01
• It seems you want to create a flood fill ... without actually flooding the matrix (say, with "revealed" status instead of "hidden"). – Martin Sojka Aug 12 '11 at 14:00

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.

• ohhhhhhhhh crap...that makes a lot more sense now. thanks! – the_e Aug 12 '11 at 13:30
• As TokPhobia said, you should somehow save and get info about what cells are already processed. Another way to save this info is dictionary. Python has them. It would be of the same perfomance, as to have "another matrix". – Nakilon Aug 12 '11 at 15:38
• i just added a boolean flag to my Mine class...then reset that flag once all the recursive calls are complete – the_e Aug 12 '11 at 18:24
• @espais For something as light as minesweeper that will probably do the job just fine. – doppelgreener Aug 12 '11 at 23:58
• Or put all visited squares in a closed list and only call the function for squares which are not in the closed list. – Stephen Aug 13 '11 at 16:32