import random
import time
def generate_maze(width, height):
"""Generate a random maze using depth-first search"""
maze = [[1 for _ in range(width)] for _ in range(height)]
def carve(x, y):
maze[y][x] = 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
random.shuffle(directions)
for dx, dy in directions:
nx, ny = x + dx*2, y + dy*2
if 0 <= nx < width and 0 <= ny < height and maze[ny][nx] == 1:
maze[y + dy][x + dx] = 0
carve(nx, ny)
carve(1, 1)
maze[0][1] = 0
maze[height-1][width-2] = 0
return maze
def print_maze(maze, path=None):
"""Print the maze with ASCII characters"""
if path is None:
path = []
for y in range(len(maze)):
for x in range(len(maze[0])):
if (x, y) in path:
print('◍', end=' ')
elif maze[y][x] == 0:
print(' ', end=' ')
else:
print('▓', end=' ')
print()
def solve_maze(maze, start, end):
"""Solve the maze using recursive backtracking"""
visited = set()
path = []
def dfs(x, y):
if (x, y) == end:
path.append((x, y))
return True
if (x, y) in visited or maze[y][x] == 1:
return False
visited.add((x, y))
path.append((x, y))
for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
if dfs(x + dx, y + dy):
return True
path.pop()
return False
dfs(*start)
return path
width, height = 21, 11
maze = generate_maze(width, height)
start = (1, 0)
end = (width-2, height-1)
print("Generated Maze:")
print_maze(maze)
print("\nSolving Maze...")
time.sleep(2)
path = solve_maze(maze, start, end)
print("\nSolved Maze:")
print_maze(maze, path)