feat: add iterative version of recursive backtracking maze generator

new file mode 100644

@@ -0,0 +1,52 @@

#!/usr/bin/env python3

"""

Recursive Backtracking Maze Generator (Iterative Version)

An iterative implementation of the recursive backtracking algorithm to avoid stack limits.

"""

import random

import sys

def generate_maze_iterative(width: int = 21, height: int = 11) -> list[list[str]]:

    # Ensure odd dimensions

    width = width if width % 2 == 1 else width + 1

    height = height if height % 2 == 1 else height + 1

    maze = [['#' for _ in range(width)] for _ in range(height)]

    # Use stack for iterative backtracking

    stack = [(1, 1)]

    maze[1][1] = ' '

    while stack:

        x, y = stack[-1]

        directions = [(0, -2), (0, 2), (-2, 0), (2, 0)]

        random.shuffle(directions)

        found = False

        for dx, dy in directions:

            nx, ny = x + dx, y + dy

            if 0 < nx < width - 1 and 0 < ny < height - 1 and maze[ny][nx] == '#':

                maze[y + dy // 2][x + dx // 2] = ' '

                maze[ny][nx] = ' '

                stack.append((nx, ny))

                found = True

                break

        if not found:

            stack.pop()

    # Entrance and Exit

    maze[0][1] = ' '

    maze[height - 1][width - 2] = ' '

    return maze

def print_maze(maze: list[list[str]]) -> None:

    for row in maze:

        print(''.join(row))

if __name__ == '__main__':

    w = int(sys.argv[1]) if len(sys.argv) > 1 else 21

    h = int(sys.argv[2]) if len(sys.argv) > 2 else 11

    print_maze(generate_maze_iterative(w, h))