Maze Solver

Project Description

This project is a simple command-line maze solver written in Python. It reads an ASCII maze from a text file, finds a path from a designated start cell to a goal cell using a search algorithm, prints the maze and the solution path in the terminal, and generates a visual representation of the maze and solution as an image file.

The project appears to be based on / inspired by an exercise from Harvard's CS50 AI course.

Purpose and Main Features

Purpose

• Demonstrate basic search algorithms (depth-first search) on a grid-based maze.
• Provide a minimal, self-contained example of representing and solving pathfinding problems.
• Visualize the search result as an image for easier inspection.

Main Features

• Load a maze from a plain-text file.
• Validate that the maze contains exactly one start (A) and one goal (B).
• Model the maze as a grid with walls, free cells, start, and goal.
• Use a stack-based frontier (depth-first search) to find a path from start to goal.
• Track and report the number of explored states.
• Print the maze and the solution path to the console.
• Generate a PNG image of the maze, optionally highlighting the solution path and explored cells, using Pillow.

Installation

Requirements

• Python 3.7+ (any modern Python 3 should work)
• pip (Python package installer)
• The Pillow library for image generation

Install Dependencies

From the project root, install the required dependency using requirements.txt:

pip install -r requirements.txt

This will install:

• pillow – used to create the PNG visualization of the maze and the solution path.

Usage

From the project root directory, run the maze solver by providing a maze text file as a command-line argument:

python maze.py maze1.txt

You can replace maze1.txt with any maze file that follows the expected format (for example, maze2.txt or maze3.txt).

Command-Line Interface

python maze.py <maze_file>

If the program is not invoked with exactly one argument, it will exit with a usage message:

Usage: python maze.py maze.txt

Example

python maze.py maze2.txt

Typical output:

• Prints the maze layout to the terminal.
• Prints Solving....
• After solving, prints the number of explored states, e.g. States Explored: 123.
• Prints the maze again with a * marking the solution path.
• Writes an image file maze.png to the current directory showing the maze, the solution path, and (optionally) explored cells.

Maze File Format

Maze files are plain-text files describing a grid. Each character corresponds to a single cell in the maze.

Special characters:

• # – wall (blocked cell)
• space ( ) – empty, traversable cell
• A – start position (exactly one required)
• B – goal position (exactly one required)

Example (maze1.txt):

#####B#
##### #
####  #
#### ##
     ##
A######

Constraints and behavior:

• The file must contain exactly one A and exactly one B, otherwise an exception is raised.
• Lines may have different lengths; the code internally pads shorter lines with empty space.
• Any character other than A, B, and space is treated as a wall.

File Structure Overview

.
├── maze.py        # Main program: maze representation, search, CLI entry point
├── maze1.txt      # Example maze input file
├── maze2.txt      # Example maze input file
├── maze3.txt      # Example maze input file
├── requirements.txt  # Python dependency list (Pillow)
└── lecture.pdf    # Related lecture notes/slides (not used by the script)

Technical Details

Core Classes

• Node

  • Represents a state in the search tree.
  • Attributes: state (row, col), parent (previous Node), action ("up", "down", "left", "right").

• StackFrontier

  • Stores nodes to be explored (LIFO / stack behavior).
  • Methods:
    • add(node) – push a node onto the frontier.
    • contains_state(state) – check if a state is already in the frontier.
    • empty() – whether the frontier is empty.
    • remove() – pop the last-added node; raises an exception if empty.

• QueueFrontier(StackFrontier)

  • Inherits from StackFrontier but overrides remove() to behave as a queue (FIFO).
  • Not used in the main script by default, but can be used to implement breadth-first search.

• Maze

  • Responsible for reading, representing, solving, and visualizing the maze.
  • Key attributes:
    • height, width – dimensions of the maze grid.
    • walls – 2D list of booleans indicating walls vs free cells.
    • start, goal – coordinates of the start and goal cells.
    • solution – tuple (actions, cells) after solving.
    • explored – set of visited states during search.
  • Key methods:
    • __init__(filename) – parses the maze file, validates A and B, builds the grid.
    • print() – prints the maze, optionally overlaying the solution path.
    • neighbors(state) – returns available moves from a given state.
    • solve() – performs depth-first search using StackFrontier to find a path.
    • output_image(filename, show_solution=True, show_explored=False) – generates a PNG image using Pillow.

Search Algorithm

• The solve() method performs depth-first search (DFS) using StackFrontier:
  • Initialize the frontier with a single Node at the start state.
  • Maintain a set of explored states to avoid revisiting.
  • Repeatedly remove a node from the frontier.
    • If its state is the goal, reconstruct the path by following parent pointers back to the start.
    • Otherwise, mark the node as explored and add all valid neighbors (not in frontier or explored) to the frontier.
  • If the frontier becomes empty before reaching the goal, raise an exception indicating no solution.

Image Output

• The output_image method uses Pillow (PIL.Image, PIL.ImageDraw) to render the maze as a PNG:
  • Each maze cell is drawn as a colored rectangle.
  • Colors (by default):
    • Walls: dark gray
    • Start: red
    • Goal: green
    • Solution path: light yellow
    • Explored cells (when show_explored=True): reddish
    • Empty cells: light background
  • The default output file in maze.py is maze.png in the current directory.

Extending the Project

Here are a few ideas if you want to build on this project:

• Switch from depth-first search to breadth-first search (using QueueFrontier) or other search strategies (A*, greedy best-first, etc.).
• Add support for different maze input formats.
• Add command-line options (e.g., to configure algorithm, output image name, or whether to show explored cells).
• Build a simple GUI around the solver.