2008 October 7 / jjddaavviiss@@ccaarrlleettoonn..eedduu

Solving Mazes

Carleton College CS 201, Prof. Joshua R. Davis

In many computer games the player can opt to play against the computer itself. Such a game must be programmed with a sense of strategy; it must exhibit some degree of complex, high-level "thinking", which computer scientists call artificial intelligence (AI). In fact, AI is not just for computer games; AI techniques are used in a wide variety of applications, from web search to robotics to electronic surveillance.

One of the fundamental AI problems is path-finding: Given a "space" of some sort (a grid of squares or hexagons, a network of roads, etc.) and two spots in that space, can you find a path through the space from one spot to the other? This problem is crucial in many games; it's also encountered in shipping/logistics software, web-crawling programs, and other applications.

In this assignment you'll write a recursive solution to the problem of finding a path through a maze. Although this may seem to be a rather special kind of path-finding problem, its methods of solution are typical of path-finding algorithms in general.

0. Obtain Files

Download the following files to a single folder on your computer. You don't need all of the maze files, but do get several of them, including some ones with higher numbers, which tend to be more complicated. These files have been written by students like you in previous terms.

• maze.py is the maze-solving program that you'll be editing.
• graphics.py is our usual graphics library.
• maze01.txt, maze02.txt, maze03.txt, maze04.txt, maze05.txt, maze09.txt, maze10.txt, maze12.txt, maze15.txt, maze16.txt, maze17.txt, maze18.txt, maze19.txt are text files that describe mazes.

1. Acquaint Yourself With The Maze File Format

A maze file is a plain text file containing a lot of numbers in a specific format. Here's what the numbers mean, starting from the first line.

• The first line contains the number of rows and the number of columns.
• For each row, there is a sequence of 0s and 1s specifying the existence of interior vertical walls (0 = no wall, 1 = wall).
• For each column, there is a sequence of 0s and 1s specifying the existence of interior horizontal walls.

3 7
1 1 0 0 0 0
1 0 0 1 0 1
0 0 0 1 0 0
0 0
0 1
1 0
0 1
1 0
0 1
0 1

Here is that maze after it's been solved:

Because they are plain text, the maze files are easy to edit (for example, in Smultron), so you can design your own mazes — and you are encouraged to do so! Just e-mail them to Josh and he will disperse them among the townspeople.

2. Write Code To Initialize The Maze

In the Maze class, the __init__() method has two places marked with "!!" where you need to fill in code to set up the maze squares with the correct wall values. Write this code and test your program to make sure it can display an unsolved maze correctly.

3. Write Code To Solve the Maze

In the Maze class there is a slot marked "!!" where you can implement a recursive maze-solving method. This is the main work of this assignment. In main() there is a slot marked "!!" where you can call your maze-solver. Edit these to solve the maze recursively. Your recursive maze solver should be extensively commented, so that your method for solution is clear. You might even want to write a paragraph describing your method.

4. Submit Your Work Electronically

By Monday at 11:59 PM, submit your maze.py file electronically (either using hsp or by putting it on COURSES manually).

Your work will be graded based on these criteria:

• Your maze-initializing code works correctly. (3 points)
• Your recursive maze-solving code works correctly. (3 points)
• Your code is clear and appropriately commented — including a thorough explanation of how your maze-solving code works. (3 points)