Python: floodfill algorithm for minesweeper

Question

I'm writing a minesweeper game in python, and am currently trying to implement a floodfill algorithm. This is what I've written:

def floodfill(CURRENT_BOARD, row, col):
count = count_mines(row, col)
if count in POSSIBLE_MINE_NUMBERS:
    CURRENT_BOARD[row][col] = str(count) + ' '
else:
    if CURRENT_BOARD[row][col] == 'P  ':
        CURRENT_BOARD[row][col] = 'P  '
        if row > 0:
            floodfill(CURRENT_BOARD, row - 1, col)
        if row < len(BOARD[row]) - 1:
            floodfill(CURRENT_BOARD, row + 1, col)
        if col > 0:
            floodfill(CURRENT_BOARD, row, col - 1)
        if col < len(BOARD) - 1:
            floodfill(CURRENT_BOARD, row, col + 1)
    else:
        CURRENT_BOARD[row][col] = '  '
        if row > 0:
            floodfill(CURRENT_BOARD, row - 1, col)
        if row < len(BOARD[row]) - 1:
            floodfill(CURRENT_BOARD, row + 1, col)
        if col > 0:
            floodfill(CURRENT_BOARD, row, col - 1)
        if col < len(BOARD) - 1:
            floodfill(CURRENT_BOARD, row, col + 1)

things to note:

POSSIBLE_MINE_NUMBERS = [1,2,3,4,5,6,7,8]

count_mines is a function that counts the number of mines in the surrounding 8 squares of row, col.

the board (CURRENT_BOARD) is a list of lists.

'P ' represents a flag, the algorithm is supposed to skip over flags.

' ' represents an empty space in the board.

The problem is when it is called, I get heaps of errors before it overflows the call stack, and I'm wondering what I've done wrong.

How do you determine whether a tile has already been uncovered? The first thing that you should do in your function is to check whether the tile is still covered. Otherwise you try to uncover the same tiles all over again. — M Oehm, Nov 03 '14 at 09:30
@PythonNewb: No, it is not. Not in the code you show. You have to check for that while you are flood-filling your board, not separately. — M Oehm, Nov 03 '14 at 09:33
For fun, call `floodfill([[' ', ' '], [' ', ' ']], 0, 0)` on a board without mines and print out which tiles get visited before you blow the stack. Your second `else` needs a condition to only uncover covered tiles. Come to think of it (and heeding NPS's advice), you should probably revise your logic to keep everything except covered tiles untouched, then determine whether there are adjacent mines and recurse only if there aren't any. — M Oehm, Nov 03 '14 at 09:48
@M Oehm Adding this: elif CURRENT_BOARD[row][col] == ' ': return seems to have fixed the issue — JavascriptLoser, Nov 03 '14 at 09:49
Seems to have brought about more issues in my count_mines() function... looks like i need more work. — JavascriptLoser, Nov 03 '14 at 09:58

score 1 · Accepted Answer · answered Nov 03 '14 at 10:24

I think you should revise your recursion algorithm:

Operate only on covered tiles
Find number of adjacent mines
If there are any, reveal a numbered tile and stop recursion
If not, reveal a blank tile and recusre

You should probably also think about how you store your board. At the moment you use the representation of the board to store the data. It might be a good idea to create a tile class and have a function that prints the board accordingly.

As for the number of adjacent mines: The mines never change, so you don't have to determine the count for each tile over and over again with a function. It is enough to determine it once after placing the mines and store the information. (If you use a class for tiles, I'd store the information there.)

Anyway, below is an implementation that uses your identification by string plus a set of tuple positions to represent the mines:

Covered = '---'
Flagged = '-P-'

board = []
for x in range(12):
    board += [[Covered] * 12]

mines = set([
    (1, 12), (8, 2), (5, 5), (9, 4), (11, 11), (0, 9),
    (5, 5), (6, 7), (9, 9), (9, 10), (11, 5)
])

def count_mines(a, b):
    c = 0
    if (a - 1, b - 1) in mines: c += 1
    if (a + 0, b - 1) in mines: c += 1
    if (a + 1, b - 1) in mines: c += 1
    if (a - 1, b + 0) in mines: c += 1
    if (a + 1, b + 0) in mines: c += 1
    if (a - 1, b + 1) in mines: c += 1
    if (a + 0, b + 1) in mines: c += 1
    if (a + 1, b + 1) in mines: c += 1
    return c

def floodfill(board, row, col):

    if board[row][col] == Covered:
        count = count_mines(row, col)

        if count > 0:
            board[row][col] = ' ' + str(count) + ' '

        else:
            board[row][col] = '   '

            if row > 0:
                floodfill(board, row - 1, col)
            if row < len(board[row]) - 1:
                floodfill(board, row + 1, col)
            if col > 0:
                floodfill(board, row, col - 1)
            if col < len(board) - 1:
                floodfill(board, row, col + 1)

def show(board):    
    for b in board:
        print "".join(b)

floodfill(board, 0, 0)
show(board)

score 0 · Answer 2 · answered Nov 03 '14 at 09:30

0

The following jumps out at me:

if CURRENT_BOARD[row][col] == 'P  ':
    CURRENT_BOARD[row][col] = 'P  '
    ...

Here, you are recursing without modifying the board. This could well be the cause of the infinite recursion you're seeing.

answered Nov 03 '14 at 09:30

NPE

486,780
108
951
1,012

Python: floodfill algorithm for minesweeper

2 Answers2

Linked