Larger Example: Solving Mazes

Let's apply everything that we have learned in the course to write a maze solver in Haskell.

In this lesson, we will combine all that we have learned in the course to write a larger Haskell program. Our goal is to write a program that solves mazes. To do so, we will first read the maze from an input file, compute the solution, and finally print it to the console.

Problem definition

The program that we will write will solve mazes of this format:

##########
#........#
#.###.##.#
#.#S.....#
#.###.##.#
#.#...##.#
#..##...##
##.####.##
#...E#..##
##########

In such a grid based maze

  • the hash # denotes a wall
  • the dot . denotes a free space
  • the character S denotes the starting position
  • the character E denotes the exit

The task is to find a sequence of moves through the grid that leads from the start to the exit. Only movement along the four cardinal directions is allowed.

For the example maze above, one possible solution is to take

  1. Two steps east
  2. Two steps north
  3. Four steps west
  4. Five steps south
  5. One step east
  6. Two steps south
  7. Two steps east

This is a visualization of the taken path:

##########
#v<<<<...#
#v###^##.#
#v#S>^...#
#v###.##.#
#v#...##.#
#>v##...##
##v####.##
#.>>E#..##
##########

Get hands-on with 1200+ tech skills courses.