University of Toronto
CSC148S--Introduction to Computer Science, Spring 1996
Assignment 4: SEARCHING MAZES

Due:  Wednesday 20 March, 6:00 pm
This assignment is worth 10 marks towards your final grade.

Introduction

The purpose of this assignment is for you to get practice understanding, writing, and proving the correctness of recursive algorithms.

In this assignment, you will be writing programs that find paths from the entrance to the exits of well-formed rectangular mazes. You will also have the opportunity to reuse or adapt some of the code you (or we) wrote for assignment 2.

Definitions

Recall the definition of a well-formed rectangular maze from the solution to assignment 2: a two-dimensional array of black and white squares with the following properties:

1. The corners of the array are black.
2. There are no two adjacent white squares along any border of the array.
3. There is no block of white squares anywhere in the array.
4. There is exactly one white square on a border of the array that has an arrow pointing into it. (This is called the entrance of the maze.)

Any white square on the border of the array, other than the entrance, is called an exit of the maze.

Two squares in a well-formed rectangular maze are adjacent if they are successive squares in some row of the maze or they are successive squares in some column of the maze. Thus the square in row i and column j is adjacent to the square in row i+1 and column j and to the square in row i and column j+1, but not to the square in row i+1 and column j+1.

A path in a well-formed rectangular maze is any sequence of white squares such that every white square in the sequence, except the first, is adjacent to the square that precedes it in the sequence. A simple path is a path in which no square appears more than once. A solution to a well-formed rectangular maze is any path from the entrance to an exit. A simple solution is a solution which is a simple path.

The following well-formed rectangular maze has an infinite number of solutions, but only two that are simple.

1. Does a Solution Exist?

When searching for a solution to a well-formed rectangular maze, it is useful to mark the white squares that have been visited in order to avoid continually revisiting the same squares. A fresh path is a path in which all the squares are unmarked. Note that as the search for a solution proceeds, fresh paths will become unfresh, as squares in those paths are visited and marked.

Consider the following recursive algorithm, which, given a well-formed rectangular maze R and an unmarked white square v, determines whether there is a fresh path from v to an exit.

function SEARCHFROM(R: maze, v: square): boolean
     mark(v) 
     if v is an exit then
           result true
           end if
     while there is an unmarked white square w adjacent to v do
           if SEARCHFROM(R, w) then result true
           end if
     end while
     result false
     end SEARCHFROM

(a) Prove that for any call SEARCHFROM(R,v), where v is an unmarked white square, if the call returns true, then there is a fresh path from v to an exit when the call is made.

To do this, let S(n) denote the statement ``for any call SEARCHFROM(R,v), where R has n unmarked white squares and v is an unmarked white square, if the call returns true, then there is a fresh path from v to an exit when the call is made''. Prove S(n) is true for all positive integers n using strong induction.

(b) Prove that if v is an unmarked white square, then the call SEARCHFROM(R,v) eventually returns.

To do this, let T(n) denote the statement ``if R has n unmarked white squares and v is an unmarked white square, then the call SEARCHFROM(R,v) returns''. Prove T(n) is true for all positive integers n using strong induction.

(c) Do (a) and (b) constitute a proof of correctness of the function SEARCHFROM? Justify your answer.

(d) Prove that if all white squares are unmarked when SEARCHFROM(R,entrance(R)) is called and the call returns true, then R has a solution.

2. Find a Solution

Modify the algorithm in part 1 to produce an algorithm that, given a well-formed rectangular maze, returns a solution if one exists, rather than just returning true. More precisely, if the given well-formed rectangular maze R has a solution, then your algorithm should return a pointer to a linked list of white squares forming a simple solution and, if R has no solution, then your algorithm should return a nil pointer. Implement your algorithm and demonstrate that it works. As part of this, you must have some way of displaying solutions that your algorithm finds. Marks will be allocated for the quality of your user interface. You may reuse (or adapt) any of your code from assignment 2 (if it was correct) or use code from the solution posted in our course web page: http://www.cs.toronto.edu/ dianeh/148.html

3. Find All Simple Solutions

Write a program that uses recursion to perform backtracking (as described in section 9.6 of the Barnard, Holt, and Hume text) to find all simple solutions of a well-formed rectangular maze. Again, you must demonstrate that your program works.

What to Hand in

Written answers for parts 1(a), 1(b), 1(c), and 1(d)

For your program in part 2:

• printout of your code
• input and output for all your test cases
• an explanation of the testing you have performed

For your program in part 3:

• printout of your code
• input and output for all your test cases
• an explanation of the testing you have performed
• a description of your method (see page 11 of the course handbook)

Tentative Grading Scheme

Below is the tentative grading scheme. Although we reserve the right to change it somewhat, it should give you an idea of where to focus your efforts.

 
Proofs

		 part 1(a)   		 20


		 part 1(b)   		 10


		 part 1(c)   		 5


		 part 1(d)   		 5


		 Total for Proofs 		40

Program to find one solution 			10


Program to find all simple solutions     	20


User interface, including display of solutions  10

Coding style  		 		  	 5


Comments   		 		 	 5


Testing and explanation of testing 		10


Method for Part 3		 		 5

TOTAL                    		       105

University of Toronto
CSC148S--Introduction to Computer Science, Spring 1996
Cover sheet for Assignment 4

You may photocopy the cover page from a friend or from the handout in the Engineering library; or create a facsimile of it yourself.

Diane Horton
Wed Mar 6 14:44:14 EST 1996