Towers of Hanoi
This program reads the representation of a maze from a text file, and finds a path through it.
Programming Issues
The first problem is to read in the maze itself. This is done in the following steps:
- Retrieve the name of the text file from the command line;
- Open the file;
- Skip through the file once to determine the number of lines;
- Dynamically allocate an array of pointer to pointer to char, with the same number of elements as the number of lines in the file;
- Skip through the file again, and allocate a char array for each line, and point one of our char ** pointers at it;
- As we go through, check that both an entrance and an exit are present, and store the location of the entrance;
We use a struct to store all the information about the maze.
The algorithm used to solve the maze is simple - stick to the left hand wall of the maze, and you will find the exit. Note this only works if both the entrance and the exit are on the outer wall of the maze (as would be usual). If the exit is in the centre, for instance, it might not be solved. We show an example of this type in our code.
A recursive function is used to solve the maze. The function knows the current position, and the current direction. From here, it tries turning 90 degrees left, going straight on, and turning 90 degree right. Having chosen the direction, it calls itself. The function terminates when it comes to a dead end, or it finds the exit, or it finds the entrance again.
Usage
Specify the name of the text file containing the maze on the command line.
For instance, if you have a file called "maze1.maz"
that looks like this:
XXXXXXXXXXXXXXXIXXX X X X XXXXXXXXXXXXXXXXX X X X X XXX XXXXX X X X X X X X X X X X X X X X XXX X X X X X X X X X X X X XXXXXXXXXXXOXXXXXXX
Call the program as follows:
./maze maze1.maz
and the program will produce the following output:
[paul@hermes maze]$ ./maze maze1.maz
Found exit!
XXXXXXXXXXXXXXXIXXX
X@@@@@@@@@@@@@@@ X
X@XXXXXXXXXXXXXXXXX
X@@@@@@@@@@@ X X
X XXX XXXXX@X X X X
X X X X@X X X X
X X X XXX X@X X X X
X X X X@X X X
XXXXXXXXXXXOXXXXXXX
[paul@hermes maze]$The format of the text file should be:
- Walls are denoted by a capital 'X';
- Paths through the maze are denoted by spaces;
- The entrance is denoted by a capital 'I'; and
- The exit is denoted by a capital 'O'
The program uses the '@' character to show the path through the maze.
Try testing the program out by designing your own mazes.