CODEWITHSUNDEEP
pythonrecursion
user3088454
user3088454

Reputation:

simplified minesweeper recursion in python: why is this code not succeeding?

I'm working on developing a minesweeper clone in python and am having trouble getting the reveal function to work. Currently, I get the following infinite error messages:

File "/Users/home/Desktop/minesweeper.py", line 79, in uncover_cells
uncover_cells(i - 1, j, board)

where uncover_cells is defined as follows (EDIT: added simpler example of problem at end of post):

def uncover_cells(i, j, board):

    length = len(board)
    width  = len(board[0])

    if i > -1 and j > -1 and i < length and j < width and not board[i][j].visited:

        board[i][j].visited = True

        # unproblematic code removed

        uncover_cells(i + 1, j, board)
        uncover_cells(i - 1, j, board)
        uncover_cells(i, j + 1, board)
        uncover_cells(i, j - 1, board)

        uncover_cells(i + 1, j + 1, board)
        uncover_cells(i + 1, j - 1, board)
        uncover_cells(i - 1, j + 1, board)
        uncover_cells(i - 1, j - 1, board)

    return

The original call is:

b, locs = setup_game(100, 100, 50)
uncover_cells(0, 0, b)

I don't think that the recursion limit has been reached and fear there might be a logic bug. Any input would be greatly appreciated.

Other code that might be important: each element of board is of type Cell:

class Cell:

    def __init__(self, isMine, loc, visited = False, flagged = False):
        self.visited = visited  # think of visited as 'uncovered'
        self.flagged = flagged
        self.isMine  = isMine
        self.x       = loc[0]
        self.y       = loc[1]

        self.label = 0

Here's how the board is setup:

def setup_game(length, width, n_mines):

    idx   = [(i, j)  for j in range(width)   for i in range(length)]
    board = [[None   for j in range(width)]  for i in range(length)]


    mine_locs = random.sample(idx, n_mines)

    for i, j in idx:

        if (i, j) in mine_locs:
            board[i][j] = Cell(isMine = True,  loc = (i, j))

        else:
            board[i][j] = Cell(isMine = False, loc = (i, j))

    return board, mine_locs

EDIT: here's the simplest instance of my problem:

def simple_fill(i, j, b):


    length = len(b)
    width  = len(b[0])

    if i > -1 and j > -1 and i < length and j < width and b[i][j] != 1:

        b[i][j] == 1

        simple_fill(i + 1, j, b)
        simple_fill(i - 1, j, b)
        simple_fill(i, j + 1, b)
        simple_fill(i, j - 1, b)

        simple_fill(i + 1, j + 1, b)
        simple_fill(i + 1, j - 1, b)
        simple_fill(i - 1, j + 1, b)
        simple_fill(i - 1, j - 1, b)

    return

original call:

b = [[0 for j in range(100)] for i in range(100)]
simple_fill(0, 0, b)

Upvotes: 1

Views: 1665

Answers (2)

user3088454
user3088454

Reputation:

I reimplemented simple_fill with a stack:

def simple_fill(x, y, b):

    length = len(b)
    width  = len(b[0])

    stack  = [(x,y)]

    while len(stack) > 0:

        i, j = stack.pop()

        if i > -1 and j > -1 and i < length and j < width :

            if b[i][j] != 1:
                b[i][j] = 1

                stack.append((i + 1, j))
                stack.append((i - 1, j)) 
                stack.append((i, j + 1))
                stack.append((i, j - 1))

                stack.append((i + 1, j + 1))
                stack.append((i + 1, j - 1))
                stack.append((i - 1, j + 1))
                stack.append((i - 1, j - 1))

Hopefully this is helpful for someone in the future (https://xkcd.com/979/)

Upvotes: 1

FMc
FMc

Reputation: 42411

In simple_fill():

b[i][j] == 1  # You have.
b[i][j] =  1  # Should be.

Using this code, your uncover_cells() works ... but only for small n. After that, we hit maximum recursion depth.

class Cell(object):
    def __init__(self, i, j):
        self.i = i
        self.j = j
        self.visited = False

def main():
    n = 30   # Works ... but not, for example, for 40.
    board = [[Cell(i,j) for j in range(n)] for i in range(n)]
    uncover_cells(0, 0, board)
    for row in board:
        for cell in row:
            assert cell.visited

main()

Upvotes: 1

Related Questions