Maze generator in python

Question

I tried writing a perfect (only one solution) maze generator in Python using backtracking.

First of all, my maze is represented by an x*y grid

Where each line represents a wall. My program will start at the top left cell (labeled 1) and will check any possible moves (2 or 6) then it will randomly choose between these 2 and add the cell label to the stack, we repeat the same process until the stack is full (in this case, 25 items), when we reach a dead end, the program should be able to backtrack by popping items from the stack and to take another path.

For a better explanation, you can refer to this website

So, here is my code:

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)

When trying to create a 5x5 maze, I mainly get stuck at 23 cells, for example, my stack looks like this: 1, 2, 7, 6, 11, 12, 13, 8, 9, 4, 5, 10, 15, 14, 19, 20, 25, 24, 23, 22, 21, 16, 17

I know that the error is coming from the gen() function.

Answer 1

By popping visited while you backtrack, you destroy your path. You should use an index instead to keep track of your backtrack:

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)

With this change, a sample result of visited would be:

[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]