🏰
Click "Generate Maze" to create a random maze
About Maze
Two phases: ① Generate with Recursive Backtracking — DFS-like on grid, carves walls between cells to build the maze. ② Solve with BFS — finds the shortest path from Start to End.
🏗️
Generate
O(R×C)
🔍
Solve BFS
O(R×C)
Why this algorithm?
Recursive Backtracking generates perfect mazes — exactly one unique path exists between any two cells.
maze.py
# ① تولید: Recursive Backtracking
def carve(maze, r, c, visited):
visited[r][c] = True
for dr, dc in shuffle(DIRS):
nr, nc = r+dr, c+dc
if in_bounds(nr,nc) and not visited[nr][nc]:
remove_wall(maze, r,c, nr,nc) # کندن دیوار
carve(maze, nr, nc, visited) # بازگشتی
# ② حل: BFS
def solve(maze, start, end):
queue = deque([start])
prev = {start: None}
while queue:
cur = queue.popleft()
if cur == end:
return reconstruct(prev, end)
for nb in neighbors(maze, cur):
if nb not in prev:
prev[nb] = cur
queue.append(nb)