Генератор лабиринта в питоне

Question

Я попытался написать идеальный (только одно решение) генератор лабиринта в Python с использованием обратного отслеживания.

Прежде всего, мой лабиринт представлен сеткой x*y

https://upload.wikimedia.org/wikipedia/commons/thumb/e/e1/Ising_model_5x5_0.svg/2000px-Ising_model_5x5_0.svg.png

Где каждая строка представляет стену. Моя программа запустится в верхней левой ячейке (с меткой 1) и проверит любые возможные ходы (2 или 6), затем случайным образом выберет эти 2 и добавит метку ячейки в стек, мы повторяем один и тот же процесс, пока стек не будет полный (в данном случае 25 элементов), когда мы заходим в тупик, программа должна иметь возможность вернуться назад, вытолкнув элементы из стека и выбрав другой путь.

Для лучшего объяснения, вы можете обратиться к этому сайту

Итак, вот мой код:

import random

dim_x = 5
dim_y = 5

grid = [[0 for i in range(dim_x)] for j in range(dim_y)]
visited = [1]

def valid(nb):
    if nb >= 1 and nb <= dim_x * dim_y:
        return True
    return False

def list_moves(nb):
    moves = []
    nb = int(nb)
    if valid(nb + dim_y) and visited.count(nb + dim_y) < 1:
        moves.append(nb + dim_y)
    if valid(nb - dim_y) and visited.count(nb - dim_y) < 1:
        moves.append(nb - dim_y)
    if valid(nb + 1) and visited.count(nb + 1) < 1 and nb % dim_x != 0:
        moves.append(nb + 1)
    if valid(nb - 1) and visited.count(nb - 1) < 1 and nb % dim_x != 1:
        moves.append(nb - 1)
    return moves

def gen():
    while len(list_moves(visited[len(visited) - 1])) < 1:
        visited.pop()
    next_visit = random.choice(list_moves(visited[len(visited) - 1]))
    visited.append(next_visit)

while len(visited) != dim_x * dim_y:
    gen()
    print(visited)

При попытке создать лабиринт 5х5 я в основном застреваю в 23 ячейках, например, мой стек выглядит так: 1, 2, 7, 6, 11, 12, 13, 8, 9, 4, 5, 10, 15, 14, 19, 20, 25, 24, 23, 22, 21, 16, 17

Я знаю, что ошибка исходит от функции gen().

Answer 1

Хлопая visited пока ты возвращаешься назад, ты уничтожаешь свой путь. Вместо этого вы должны использовать индекс для отслеживания вашего возврата:

def gen():
    pos = len(visited) - 1
    while len(list_moves(visited[pos])) < 1:
        pos -= 1
    next_visit = random.choice(list_moves(visited[pos]))
    visited.append(next_visit)

С этим изменением пример результата visited было бы:

[1, 2, 7, 12, 11, 16, 17, 18, 23, 24, 25, 20, 19, 14, 15, 10, 5, 4, 9, 8, 13, 3, 22, 21, 6]

Answer 2

Сохранение двух переменных, одна для обхода пути, а другая для посещенных узлов, решит проблему. Кроме того, ничто не должно выталкиваться из пройденного пути, так как обход должен быть результатом этой программы.

def gen():
    pathLen = len(path)
    nextNode = path[pathLen - 1]
    while len(list_moves(nextNode)) < 1:
        pathLen -= 1
        nextNode = path[pathLen-1]
        path.append(nextNode)

    next_visit = random.choice(list_moves(path[len(path) - 1]))
    visited.append(next_visit)
    path.append(next_visit)