MazeSolver

A solver for mazes

Build

CMAKE

To build, simply run:

mkdir build
mkdir lib
mkdir bin
cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build

The compiled program will be found in bin.

Solving a maze

The main purpose of this project is to solve mazes. However, it does have the ability to generate a maze for demonstration purposes.

Generate a maze and solve

Simply running MazeSolver will generate a 10x10 maze and display the solution.

Running MazeSolver <W> <H> will generate a maze of size WxH and display the solution.

Providing a maze to solve

To provide a maze to solve, use the -i flag like so MazeSolver -i <file>.

Solution example

Take the following maze:

#####################
#        X  # #   # #
### ##### # # # ### #
# # #     #       # #
# # ### # ### ##### #
# # # # # #     # # #
# ### # ##### # # # #
#     #   # # # #   #
# ### # # # # # # # #
# #   # # #   #   # #
# # # # # ######### #
# # #   #     #     #
# ##### ### ### #####
# # # # # # #       #
### # ### ### ### ###
#   #           # # #
# ######### # ### # #
#       # # # #     #
# ### # # ### ##### #
# #   #       #    S#
#####################

This is a solution generated by the solver:

#####################
#        x**#.#   #.#
### ##### #*#.# ###.#
# # #     #***    #.#
# # ### # ###*#####.#
# # # # # #  ***#.#.#
# ### # ##### #*#.#.#
#     #   # # #*#***#
# ### # # # # #*#*#*#
# #   # # #   #***#*#
# # # # # #########*#
# # #   #     #*****#
# ##### ### ###*#####
# # # # # # #  ***  #
### # ### ### ###*###
#   #           #*#.#
# ######### # ###*#.#
#       # # # #  ***#
# ### # # ### #####*#
# #   #       #    s#
#####################

Symbol Definition

The following symbols are defined for a maze:

• # - Wall
• space - Path (not visited or solution)
• . - Path (visited, but not solution)
• * - Path (solution)
• S - Starting location (not visited)
• s - Starting location (visited)
• X - Destination (not visited)
• x - Destination (visited)

Format

A valid maze must have:

1. A border of walls.
2. A start labeled S.
3. An end labeled X.

The maze consist of cells. Each cell is defined as a 9x9 grid of text.

This is an example of a cell:

###
# #
###

Only the 4 cardinal directions (up, down, left, right) are considered for walls. The corners are included mainly for alignment and ascetics.

This is an example of a cell with no walls:

# #
   
# #

Two neighboring cells will share the same wall.

This is an example of two neighboring cells (1 and 2):

#####
#1 2#
#####

This is an example of four cells in a 2x2 formation:

#####
#1 2#
### #
#3 4#
#####

Notice that for a maze of size MxN, it takes $(2M+1)\times(2N+1)$ characters to store the maze.

TODO

• Maze Solver
• Verbose Steps
• Write Help