MAZE ALGORITHM: IS IT SOLVABLE?

Abstract

This article presents a solution to the classic maze traversal problem, where the objective is to determine whether a valid path exists from a designated starting point ('S') to an exit point ('E') in a grid-based maze. The maze is composed of open paths ('.'), walls ('#'), a start, and an exit, with movement restricted to horizontal and vertical directions. The solution implements the Depth-First Search (DFS) algorithm to explore the maze and identify whether a path from the start to the exit exists, while avoiding revisits and obstacles. Key operations include maze input handling, algorithm initialization, execution, and result output. The implementation employs essential data structures such as a 2D array for maze representation, a stack for DFS traversal, and a boolean array to track visited cells. The article discusses the design decisions behind these structures, outlines the algorithm's limitations, and explores potential future enhancements. This work highlights the importance of algorithmic problem-solving and data structure selection in pathfinding applications.