Алгоритм рекурсии Python Minesweeper Превышение предела рекурсии - PullRequest
Новая
       42

Алгоритм рекурсии Python Minesweeper Превышение предела рекурсии

0 голосов
/ 08 октября 2018

Я пытаюсь создать Сапер с массивами Python и успешно сгенерировал доску и бомбы.Однако у меня возникли трудности с "нулевой рекурсией" тральщика.Если вы выберете 0 в Minesweeper, он покажет все соседние плитки, а если любой из соседних плиток будет 0, он покажет все смежные плитки с этим 0 и так далее.В конечном счете, по краям раскрытых тайлов не может быть нулей, так как будут показаны все смежные тайлы с выявленными нулями.Мой алгоритм рекурсии превышает максимальную глубину рекурсии Python.Вот код: 

def zero():

    for y in range(height):

        for x in range(width-1):

            if hidden[y][x] == 0 and (hidden[y+1][x] == '?' or hidden[y-1][x] == '?' or hidden[y+1][x+1] == '?' or hidden[y-1][x-1] == '?' or hidden[y+1][x-1] == '?' or hidden[y-1][x+1] == '?' or hidden[y][x+1] == '?' or hidden[y][x-1] == '?'):

                if y+1 < height:

                    hidden[y+1][x] = board[y+1][x]

                if y-1 >= 0:

                    hidden[y-1][x] = board[y-1][x]

                if y+1 < height and x+1 < width:

                    hidden[y+1][x+1] = board[y+1][x+1]

                if y-1 >= 0 and x+1 < width:

                    hidden[y-1][x+1] = board[y-1][x+1]

                if y-1 >= 0 and x-1 >= 0:

                    hidden[y-1][x-1] = board[y-1][x-1]

                if x+1 < width:

                    hidden[y][x+1] = board[y][x+1]

                if x-1 >= 0:

                    hidden[y][x-1] = board[y][x-1]

                if y+1 < height and x-1 >= 0:

                    hidden[y+1][x-1] = board[y+1][x-1]


                zero()

Код проверяет, есть ли обнаруженные нули с какими-либо скрытыми соседними плитками в массиве.(Скрытые плитки обозначены символом «?»).Если есть какие-либо нули, которые соответствуют этим параметрам, будут показаны все соседние плитки к нулю.Затем он перезапускает функцию.Если во всем массиве нет нулей, соответствующих параметрам, цикл функции будет прерван, и код продолжит выполнение.Это превышает предел рекурсии.Какие-либо предложения?

1 Ответ

0 голосов
/ 08 октября 2018

Ваш тест для '?' не защищен от индексации за пределами платы.На краях с низким индексом это приводит к отрицательным индексам, которые окружают.Тем не менее, код, который очищает '?' s, проверяет его индексы, так что любой перекрестный край 0-?пара сохраняется и результаты бесконечной рекурсии.

На краях доски с высоким индексом чтение завершится неудачей с IndexError (при условии, что заполнение не будет с «призрачными ячейками»), но, конечно, алгоритм смещенего порядок поиска в сторону меньших индексов, поэтому обычно он никогда не заходит так далеко.

...