Maze Solver

A comprehensive maze-solving application that implements three different pathfinding algorithms (BFS, DFS, and A*) with both command-line and web-based interfaces.

📁 Project Structure

Maze-Solver/
├── app.py              # Streamlit web application
├── main.py             # Command-line interface application
├── bfs.py              # Breadth-First Search implementation
├── dfs.py              # Depth-First Search implementation
├── astar.py            # A* Search algorithm implementation
├── visualize.py        # Matplotlib visualization functions
├── utils.py            # Utility helper functions
├── maze.py             # Maze input handling functions
├── requirements.txt    # Project dependencies
└── README.md           # Project documentation

🚀 Algorithms Implemented

File	Algorithm	Description
bfs.py	Breadth-First Search (BFS)	Guarantees shortest path using queue-based exploration
dfs.py	Depth-First Search (DFS)	Stack-based exploration, may not find shortest path
astar.py	A* Search	Informed search using Manhattan distance heuristic

🖥️ Applications

1. Streamlit Web App (app.py)

Interactive web application with visual maze solving capabilities.

Features:

• Dynamic maze size selection (rows/columns)
• Interactive maze input grid
• Algorithm selection dropdown
• Real-time visualization using matplotlib
• Error handling for invalid inputs

Run with:

streamlit run app.py

2. Command-Line Interface (main.py)

Terminal-based maze solver with text output.

Features:

• Step-by-step maze input
• Algorithm selection menu
• Text-based path output
• Console visualization

Run with:

python main.py

🔧 Algorithm Details

BFS (bfs.py)

• Uses collections.deque for queue operations
• Guarantees shortest path in unweighted grids
• Returns path as list of coordinates or None if no path exists

DFS (dfs.py)

• Uses stack (LIFO) for traversal
• May find longer paths but uses less memory
• Order-dependent path results

A* (astar.py)

• Uses heapq for priority queue
• Manhattan distance heuristic
• Combines actual cost (g) + heuristic (h) for optimal pathfinding

📦 Dependencies

All dependencies are listed in requirements.txt:

streamlit==1.46.0    # Web interface
matplotlib==3.10.3   # Visualization
numpy==2.2.6         # Array operations

Install with:

pip install -r requirements.txt

🧩 Module Documentation

Core Algorithm Modules

Module	Function	Parameters	Returns
bfs.py	bfs(maze, start, end)	2D list, tuple, tuple	List or None
dfs.py	dfs(maze, start, end)	2D list, tuple, tuple	List or None
astar.py	astar(maze, start, end)	2D list, tuple, tuple	List or None

Visualization Module (visualize.py)

visualize_maze(maze, path, start, end)

• Creates matplotlib figure with color-coded maze
• Colors: White (path), Black (wall), Blue (solution), Green (start), Red (end)
• Compatible with Streamlit's st.pyplot()

Utility Module (utils.py)

Function	Purpose
is_valid_position(maze, position)	Validates cell accessibility
print_maze(maze)	Prints maze to console
is_within_bounds(maze, position)	Checks grid boundaries
reconstruct_path(parent, start, end)	Builds path from parent pointers
manhattan_distance(a, b)	Calculates heuristic for A*

Maze Input Module (maze.py)

Function	Description
input_maze()	Interactive maze grid input
input_coordinates(prompt, max_row, max_col)	Validated coordinate input
get_maze_from_user()	Complete maze and coordinate collection

🎮 Usage Examples

Maze Format

• 0 = Open path (walkable)
• 1 = Wall (blocked)

Sample 5x5 Maze

0 0 0 1 0
1 0 1 0 0
0 0 0 0 1
0 1 1 0 0
0 0 0 0 0

Input Format

• Start coordinates: 0 0 (row column)
• End coordinates: 4 4 (row column)

🎨 Visualization Output

The visualize_maze() function generates a color-coded grid:

• 🟩 Green - Start position
• 🟥 Red - End position
• 🔵 Blue - Solution path
• ⬜ White - Walkable cells
• ⬛ Black - Walls

⚠️ Error Handling

All modules include validation for:

• Invalid maze dimensions
• Out-of-bounds coordinates
• Start/end points on walls
• Invalid cell values (non-0/1)
• Missing or invalid user input

🔄 Workflow

1. Input Phase (maze.py): Collect maze dimensions and grid
2. Algorithm Selection (main.py or app.py): Choose BFS/DFS/A*
3. Pathfinding (algorithm module): Execute search algorithm
4. Visualization (visualize.py): Display solved maze
5. Output: Path coordinates and visual representation

📝 Notes

• BFS is recommended for shortest path discovery
• A* is most efficient for larger mazes with heuristic guidance
• DFS uses less memory but may produce longer paths
• All algorithms use 4-directional movement (up, down, left, right)

🤝 Contributing

Feel free to extend the project with:

• Additional heuristics for A*
• Diagonal movement support
• Animated path visualization
• Maze generation algorithms
• Performance benchmarking tools