Imagine that you are an intrepid adventurer that goes looking for hidden treasure in the far-off caves of lost civilization. As part of this quest, you become trapped in an underground maze. You are convinced that the treasure is somewhere in the maze, but you can see nothing but walls. You realize that you must have a strategy and a computer program to find the treasure. Unfortunately, no built-in Unix command would help you traverse a maze, so you must write a C program to do this.
In the example maze in the figure above, the red square is the exit of the maze (leading to the hidden treasure). The blue circle is the current location. The green circles mark the visited intersections. The yellow circles mark the visited locations.
Purpose
To exhaustively traverse a maze to find the exit and back tracking (algorithm) whenever reaching a dead end.
Sample Input and Output
You can download these sample inputs to test your program. Four examples are shown here. You are encouraged to post your answers to these test cases and compare your results with those of your classmates. The characters represent
'*': brick
' ': (space) corridor
'E': exit, i.e. the destination
's': your starting location
Please be aware that these test cases are not the cases to be used in grading. Passing all tests cases here does not guarantee a full score. You are responsible for creating test cases that meet the specification but are not included here.
If you need more mazes, please use some tools to generate one, like this Online Maze Generator. You may need to change the output a little to satisfy the assumptions. Here is a brief tutorial:
Change "Type of maze" to "Text"
Change "Width of each cell" and "Height of each cell" to 2
Click "Generate", then copy and paste the result into a text editor
Use "Find and Replace" to substitute '-'s and '+'s with 'B'
Enclose the maze and set starting and ending locations
As you are thinking about how to find the exit, you are thinking about the courses that have taught you problem-solving skills. You need to remember where you have been and to avoid visiting the same place twice. Every time you encounter an intersection, you have to remember the decision made at this intersection. You do not know the size of the maze so you have to store data of an unknown size. Fortunately, you have developed a survival strategy:
Go as far as possible until reaching the exit or a dead end.
Whenever you encounter an intersection, you rely on your compass (GPS doesn't work underground but fortunately your compass still does). You try different routes at an intersection in the following order:
East -> South -> West -> North
You should not take a direction that would lead you back to where you have been, unless you encounter a dead end.
After reaching a dead end, go back to the last intersection and take a different route, following the direction order listed above.
If all routes at an intersection reach to dead ends, go back to the previous intersection.
This strategy is called depth-first-search with backtracking because you go as far as possible and backtrack when a route turns out to be a dead end. If you follow this strategy, it is possible to show that you will eventually always find the exit (if there exists a path from the starting point to the exit in the first place, that is).
Requirements
The program takes one input argument as the maze file. If this input file name is not provided, the program prints an error message and terminates with return value -1. If the file cannot be opened, it also prints an error message and return -1.
Your program will read the maze file and keep track of all necessary information in memory.
Your algorithm must meet the strategy requirements in the [Strategy] section. It is very important that your solution follows the order: East -> South -> West -> North. If your program takes a different order, the output will be different and you will receive zero points on the assignment.
For each step, print out a string "Move to (row,col)\n" where (row,col) is the coordinate of the new location. The player can move only one step each time, i.e., from (row,col) you can only reach (row+/-1,col) or (row,col+/-1) as your next step. Here, row corresponds to the vertical (y) coordinate and col corresponds to the horizontal (x) coordinate.
The first step must be "Move to (row0,col0)\n" where (row0,col0) is the coordinate of the starting location 's', and the last step must be "Move to (row1,col1)\n" where (row1,col1) is the coordinate of the exit 'E'.
You must include a Makefile in your submission. Your program will be compiled and built using your Makefile. If there is no Makefile, your submission will not be graded. The name of the executable file must be 'ipa1' (case-sensitive, no extension, not ipa1.exe).
Your code needs to follow the coding standards specified here. We will manually check this and you can lose up to 1 point if standards are not followed.
Do not use a graphical user interface (GUI). Instead, print the location of every step to the console using standard C functions. Your program will be graded based on the textual output. You can print the maze and the current location for debugging. Please remember to remove all debugging information when you submit the program for grading.
If you want to learn GUI, you can try GTK or Qt. Both need some understanding about C++. You can take ECE 462 after 264.
Assumptions
The top-left block of the maze has coordinate (0,0). This is the convention in computers.
The maximum width (number of columns) of a maze does not exceed 80. A maze input file may contain many lines. Therefore, your program should allocate memory only after it knows the number of lines in the file.
The maze is always fully enclosed by bricks, i.e., it is impossible to escape from the maze other than through the exit. Be aware that a valid maze does not have to be rectangular.
The starting location may appear anywhere in the maze (e.g., at an intersection).
Each maze has only one starting location and only one exit.
All passages (corridors) in mazes are 1-character wide.
There is one and only one path between two points in the maze.
What to submit?
The source code (including all .c and .h needed to generate the final executable). You must use at least three files (one .h header file and two .c source files.) You will receive zero if everything is in a single file. Of course, you cannot submit three files and two of them are empty. You can have more files if necessary.
Upload the files as a zip package containing the necessary files (source files, header files and Makefile). You can name the source files, header files and the zip package arbitrarily, but make sure that the target executable of the Makefile is named "ipa1" (all lower-case). You will receive zero if there is no executable named "ipa1" after running "make".
Makefile to create the executable. Name the executable as ipa1 (not ipa1, not IPA1, not pa1, not ipa1.exe, or anything else). You will receive zero if your submission has no Makefile. The file name must be Makefile (this is a widely accepted convention); any other names will be rejected.
README to explain what you have done and how you do it. You need to explain how you store the locations. The file name must be README, not readme, not Readme, not README.txt, not README.pdf, nor README.doc.
Do not include object files, executable files, sample inputs, or outputs.
You should never have a space or symbol (other than .) in a file name. Some operating systems can accept file names with spaces or symbols but some operating systems cannot. To make sure your programs work, do not take a chance.
Part 1
This may be the most complex program you have ever written. To help you manage the assignment, this assignment is divided into two parts. In the first part, your program needs to read the maze file and print the following information:
The size of the maze: the width and the height.
The location of the exit.
The location of the starting point.
Please use the following code so that your output has the same format as expected by the grading program
printf("width=%4d, height=%4d\n", width, height);
printf("exit at (%4d, %4d)\n", exitX, exitY);
printf("start at (%4d, %4d)\n", startX, startY);
You can use different names for the variables: width, height, exitX, ...
Part 2
The second part requires that your program prints the location of every step from the starting point to the exit.
Performance
The score of your program is not determined by its performance. However, your program has to be "reasonably fast" so that it can be graded. If your program takes longer than 100 times of the sample solution, your program will fail certain tests.
Your program is graded by another program. Nobody will sit in front of a computer to enter anything from the keyboard. Do not use scanf or anything that requires inputs from keyboard. This will cause your program to hang up and eventually time out while your program is being graded and you will likely receive zero.
Grading
The full score of this assignment is 10 points, divided into two parts.
Part 1 (2 points)
0.5: return -1 if no file name is given
0.5: return -1 if the file cannot be open
0.5: print the size correctly
0.5: print the locations of the exit and the starting point
-1: Memory leak or unclosed files reported by valgrind. For self-checking: You must receive "no leaks are possible" at the end of valgrind's report to pass this test.
-0.2: each warning message reported by -Wall -Wshadow. Pay special attention to the variables that are defined but never used.
Part 2 (8 points)
Do not print the size of the maze, nor the locations of the exit and the starting point.
We will use 16 different mazes to test the outputf of your program. You will receive 0.5 point if your program produces correct results. For each failed test, you lose all 0.5 point.
Programming style:
You will lose 4 points if the program leaks memory. You will lose 0.5 point for each warning message.
The minimum score is zero. You will not receive a negative score.
Memory Management
Memory management (allocation and release) is an important part of ECE 264. You have to allocate enough memory to make your program work. You have to allocate and release memory as needed. You are not allowed to allocate a large piece of memory regardless of the input size. We will restrict stack size to prevent that. You will receve heavy penalty (50%) if your program does not release all memory (i.e. memory leak). We will use valgrind to check for memory leaks.
Submission Procedure
You must submit through this web site. This is the only way to submit your exercises and programming assignments.
You need to provide a user name and a password through Blackboard before submission. The user name and the password are different from your Purdue career account.
Congratulations!
You have found the priceless ancient treasure! After all, C programming isn't just about writing code. It saves your life. You are so happy that you study ECE 264 very hard and apply the knowledge in the future. You will lead an expedition team back to the maze and find the hidden treasure. You will also come back to tell future ECE 264 students that the course is very helpful.
Bonus Points
If you have done additional work and deserve bonus points, please contact the instructor before March 21, 2011. When you submit the assignment, turn off the bonus features because the grading programs do not handle bonus features.
Single Path
1 points: After finding the exit, print the path without the mistakes. Make the correct decision at every intersection.
2 points: For a w x h maze, what is the longest distance you may possibly need to go through before finding the exit? Write down your answer as a function of w and h.
Multiple Path
2 points: Handle multiple paths. The mazes used in this assignment have one common restriction: there is exactly one path between two points. We can easily create mazes in which there are multiple paths (by removing some bricks). How would your strategy be different?
1 points: Print the shortest path in a maze with mutliple path. Make the correct decision at every intersection.
