3D Maze Solver
Project Overview
Multi-State Pathfinding System
This project implements a sophisticated state-space search system that solves color-coded maze puzzles where players must navigate through a grid while collecting color-coded buttons to open corresponding doors. The solver supports both breadth-first search (queue-based) and depth-first search (stack-based) exploration strategies, tracks discovered paths through multiple color states, and provides comprehensive visualization of the solution path across all color layers.
Technical Architecture
The system employs a multi-dimensional state representation where each position in the maze exists across multiple color planes (up to 26 colors plus a neutral state). A state is defined by its position (row, column), current active color, and cell type. The solver maintains a 3D backtrace structure indexed by [color][row][col] to track exploration history across all color states independently, allowing the same physical location to be visited multiple times under different color contexts. This enables elegant handling of scenarios where a player must revisit locations after acquiring new colors.
Core Algorithmic Components
State Space Exploration: Implements a unified search framework that switches between BFS (using deque as queue) and DFS (using deque as stack) based on command-line flags. Each state investigation first checks if the current cell is a button that can change the player's color, creating a new color-state transition without changing position. Then it explores all four cardinal directions (North, East, South, West), validating moves based on current color permissions—walls block all movement, open spaces allow all colors, doors only allow matching colors, and buttons can always be stepped on regardless of color.
Backtrace Reconstruction: Uses directional markers ('N', 'E', 'S', 'W') to record the inverse direction of movement, storing where the player came from rather than where they went. This simplifies path reconstruction by allowing the algorithm to follow the stored directions backward from target to start. Color transitions are recorded by storing the previous color character, enabling the system to reconstruct the exact sequence of button presses. The path is built in reverse from target to start, then reversed to produce the forward solution.
Dual Output Modes: Supports both list format (showing color-position pairs as a sequence of state transitions) and map format (rendering a separate visual map for each color layer with path markers). Map output uses special symbols: '@' marks color acquisition points, '%' marks color release points, '+' marks regular movement, and '?' marks the target. The visualization cleverly hides doors and buttons that match the current color layer by replacing them with dots, showing only obstacles and features relevant to that particular color state.
Performance & Design Considerations
The implementation validates input comprehensively, checking for proper color counts (max 26), non-zero dimensions, exactly one start ('@') and one target ('?'), and ensuring all referenced colors exist in the map. Error handling detects invalid characters, doors/buttons for non-existent colors, and structural inconsistencies. The backtrace array uses '!' as a sentinel value for unvisited states, enabling O(1) visited checks without requiring separate data structures. The deque container provides O(1) access at both ends, making it ideal for supporting both queue and stack semantics with a single underlying structure. Path reconstruction runs in O(path_length) time by following stored backpointers, and the discovered-map output for failed solutions reveals exactly which states were explored during the search process.