Larger Example: Solving Mazes

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#..##
##########

Modeling the problem domain

A good first step in writing functional programs is to start with defining types that express the problem domain. In this case, we are dealing with a 2D grid of fields that can be either walls, free spaces, or the start and exit of the maze.

The grid

Let’s start by defining a data type for fields.

data Field = Start | Free | Wall | Exit deriving (Eq, Show)

We derive Eq and Show so we can easily compare and print the fields. Since the input to our program will be in text form, ...