difficulty: under graduate
Here’s a sample program in Python that generates random mazes with varying difficulties using the depth-first search (DFS) algorithm:
import random
def generate_maze(rows, cols, difficulty):
"""
Generate a random maze using depth-first search (DFS) algorithm.
:param rows: number of rows in the maze
:param cols: number of columns in the maze
:param difficulty: difficulty level of the maze, either "easy", "medium", or "hard"
:return: 2D list representing the maze
"""
maze = [[1 for _ in range(cols)] for _ in range(rows)]
stack = [(0, 0)]
while stack:
curr = stack.pop()
x, y = curr
maze[x][y] = 0
neighbors = []
for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
x_, y_ = x + dx, y + dy
if 0 <= x_ < rows and 0 <= y_ < cols and maze[x_][y_] == 1:
neighbors.append((x_, y_))
random.shuffle(neighbors)
if difficulty == "easy":
if len(neighbors) > 1:
stack.append(neighbors[0])
elif difficulty == "medium":
if len(neighbors) > 1:
stack.extend(neighbors[:2])
elif difficulty == "hard":
stack.extend(neighbors)
return maze
# Example usage
rows, cols = 10, 10
difficulty = "medium"
maze = generate_maze(rows, cols, difficulty)
for row in maze:
print(row)
In this program, we define a generate_maze function that takes three arguments: the number of rows rows, the number of columns cols, and the difficulty level difficulty of the maze. The function generates a maze using the DFS algorithm, where it starts from the top-left position (0, 0) and explores all possible neighbors. The maze 2D list stores the state of each cell, where 1 represents a wall and 0 represents a free space. The stack list stores the current position and the neighbors that need to be explored.
The difficulty level determines the number of neighbors that are explored in each iteration. For an “easy” difficulty, only one neighbor is explored. For a “medium” difficulty, two neighbors are explored. For a “hard” difficulty, all neighbors are explored. The neighbors are shuffled randomly to generate a random maze.
The example usage generates a 10×10 maze with a “medium” difficulty, and prints the maze as the output.
Here’s a sample program in Python that solves a maze using the depth-first search (DFS) algorithm:
def solve_maze(maze, start, end):
"""
Solve the maze using depth-first search (DFS) algorithm.
:param maze: 2D list representing the maze
:param start: tuple (x, y) representing the starting position
:param end: tuple (x, y) representing the ending position
:return: list of tuples representing the path from start to end, if found; otherwise None
"""
rows, cols = len(maze), len(maze[0])
stack = [start]
parent = {start: None}
while stack:
curr = stack.pop()
if curr == end:
path = []
while curr:
path.append(curr)
curr = parent[curr]
return path[::-1]
for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
x, y = curr[0] + dx, curr[1] + dy
if 0 <= x < rows and 0 <= y < cols and maze[x][y] == 0 and (x, y) not in parent:
parent[(x, y)] = curr
stack.append((x, y))
return None
# Example maze
maze = [
[1, 1, 1, 1, 1],
[1, 0, 0, 0, 1],
[1, 0, 1, 0, 1],
[1, 0, 0, 0, 1],
[1, 1, 1, 1, 1]
]
start = (1, 1)
end = (3, 3)
path = solve_maze(maze, start, end)
print(path)
In this program, we define a solve_maze function that takes a 2D list maze, representing the maze, and two tuples start and end, representing the starting and ending positions in the maze. The function uses a stack to keep track of the current position and uses the DFS algorithm to explore all possible paths from the start to the end. The parent dictionary stores the parent of each position in the path. When the end position is found, the path is reconstructed by tracing back from the end position to the start position using the parent dictionary.
The example maze is a 5×5 matrix where 1 represents a wall and 0 represents a free space. The start and end positions are defined as (1, 1) and (3, 3), respectively. The solve_maze function is called to find the path from the start to the end, which is printed as the output.