Python: floodfill algorithm for minesweeper

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.

Solution

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)