maze-solver

Abstract

• This project is a simple maze solver based on Breadth-First Search (BFS).
• It reads a maze from a text file, finds the shortest path from S (Start) to G (Goal), and outputs the result to a new file.
• Walls are represented by #, open paths by ., start by S, and goal by G.
• The solved path is visualized using directional arrows:
  • ^ : move up
  • > : move right
  • v : move down
  • < : move left

Input Format

The maze is provided as a plain text file (in.txt) with the following rules:

• # : wall
• . : free cell
• S : start position (must be unique)
• G : goal position (must be unique)
• All rows must have the same length.

Example Input

########################################
#S#.......#.......#.........#..........#
#.#.#####.#.#####.#.#######.#.########.#
#...#...#...#...#...#.....#...#........#
#####.#.#######.#.###.###.#####.######.#
#.....#.........#.....#.#.......#......#
#.#####.#######.#######.#.#######.####.#
#.#.....#.......#.......#.#.......#....#
#.#.#####.#######.#######.#.#######.####
#.#.#...#.#.......#.....#.#.#.....#....#
#.#.#.#.#.#.#######.###.#.#.#.###.####.#
#.#.#.#.#.#.#.......#...#.#.#.#.#......#
#.###.#.#.#.#.#######.###.#.#.#.########
#.....#.#.#.#.......#.#...#.#.#........#
#######.#.#.#######.#.#.###.#.########.#
#.......#.#.......#.#.#.#...#.#........#
#.#######.#######.#.#.#.#.###.#.########
#.#.......#.......#.#.#.#.#...#.#......#
#.#.#######.#######.#.#.#.#.###.#.####.#
#.#.#.......#.......#.#.#.#.#...#.#....#
#.#.#.#######.#######.#.###.#.###.#.####
#.#.#.#.......#.......#.#...#.#...#....#
#.#.#.#.#######.#######.#.###.#.#######.
#.#.#.#.#.......#.......#.#...#........#
#.#.###.#.#######.#######.#.##########.#
#.#.....#.#.......#.......#.#..........#
#.#######.#.#######.#######.#.##########
#.........#.........#.......#..........#
###########.#########.#######.########.#
#...........#.........#.......#........#
#.###########.#######.#.#######.######.#
#.#...........#.......#.#.......#......#
#.#.###########.#######.#.#######.####.#
#.#.#...........#.......#.#.......#....#
#.#.#.###########.#######.#.#######.####
#.#.#.#...........#.......#.#.......#..#
#.#.#.#.###########.#######.#.#######..#
#...#...#...........#.......#.........G#
########################################

Output Format

• The result is written to out.txt.
• The shortest path from S to G is marked using directional arrows.
• S and G remain unchanged in the output.

Example Output

########################################
#S#>>>>>>v#>>>>>>v#.........#..........#
#v#^#####v#^#####v#.#######.#.########.#
#>>^#...#>>^#...#v..#>>>>v#...#........#
#####.#.#######.#v###^###v#####.######.#
#.....#.........#>>>>^#.#v......#......#
#.#####.#######.#######.#v#######.####.#
#.#.....#.......#.......#v#.......#....#
#.#.#####.#######.#######v#.#######.####
#.#.#...#.#.......#.....#v#.#.....#....#
#.#.#.#.#.#.#######.###.#v#.#.###.####.#
#.#.#.#.#.#.#.......#...#v#.#.#.#......#
#.###.#.#.#.#.#######.###v#.#.#.########
#.....#.#.#.#.......#.#v<<#.#.#........#
#######.#.#.#######.#.#v###.#.########.#
#.......#.#.......#.#.#v#...#.#........#
#.#######.#######.#.#.#v#.###.#.########
#.#.......#.......#.#.#v#.#...#.#......#
#.#.#######.#######.#.#v#.#.###.#.####.#
#.#.#.......#.......#.#v#.#.#...#.#....#
#.#.#.#######.#######.#v###.#.###.#.####
#.#.#.#.......#.......#v#...#.#...#....#
#.#.#.#.#######.#######v#.###.#.#######.
#.#.#.#.#.......#v<<<<<<#.#...#........#
#.#.###.#.#######v#######.#.##########.#
#.#.....#.#v<<<<<<#.......#.#..........#
#.#######.#v#######.#######.#.##########
#.........#v........#.......#>>>>>>>>>v#
###########v#########.#######^########v#
#v<<<<<<<<<<#>>>>>>>>v#>>>>>>^#.......v#
#v###########^#######v#^#######.######v#
#v#>>>>>>>>>>^#v<<<<<<#^#.......#.....v#
#v#^###########v#######^#.#######.####v#
#v#^#v<<<<<<<<<<#>>>>>>^#.#.......#v<<<#
#v#^#v###########^#######.#.#######v####
#v#^#v#>>>>>>>>>>^#.......#.#v<<<<<<#..#
#v#^#v#^###########.#######.#v#######..#
#>>^#>>^#...........#.......#>>>>>>>>>G#
########################################

Algorithm

• Uses Breadth-First Search (BFS) to compute the shortest distance from S to every reachable cell.
• Once G is reached, the algorithm reconstructs the path by moving backward along decreasing distance values.
• Each step is replaced with an arrow indicating the direction of movement toward G.

Installation

Require Python 3.

Clone this repository:

git clone https://github.com/pantsman-jp/maze-solver

Usage

1. Prepare an input file named in.txt in the project directory.
2. Run the solver:

python main.py

3. The solved maze will be written to out.txt.

---

Copyright © 2026 pantsman