DOC PREVIEW
Stanford CS 106B - Recursive Backtracking

This preview shows page 1 out of 4 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Eric Roberts Handout #19CS 106B April 17, 2009Recursive BacktrackingRecursive BacktrackingEric RobertsCS 106BApril 17, 2009Solving a MazeA journey of a thousand miles begins with a single step.—Confucius, 5th century B.C.E.• The example most often used toillustrate recursive backtrackingis the problem of solving a maze,which has a long history in itsown right.• The most famous maze in historyis the labyrinth of Daedalus inGreek mythology where Theseusslays the Minotaur.• There are passing references tothis story in Homer, but the bestknown account comes from Ovidin Metamorphoses.. . . When Minos, willing to conceal the shameThat sprung from the reports of tatling Fame,Resolves a dark inclosure to provide,And, far from sight, the two-form’d creature hide.Great Daedalus of Athens was the manThat made the draught, and form’d the wondrous plan;Where rooms within themselves encircled lye,With various windings, to deceive the eye. . . .Such was the work, so intricate the place,That scarce the workman all its turns cou’d trace;And Daedalus was puzzled how to findThe secret ways of what himself design’d.These private walls the Minotaur include,Who twice was glutted with Athenian blood:But the third tribute more successful prov’d,Slew the foul monster, and the plague remov’d.When Theseus, aided by the virgin’s art,Had trac’d the guiding thread thro’ ev’ry part,He took the gentle maid, that set him free,And, bound for Dias, cut the briny sea.There, quickly cloy’d, ungrateful, and unkind,Left his fair consort in the isle behind . . .Metamorphoses—Ovid, 1 A.C.E.The Right-Hand Rule• The most widely known strategyfor solving a maze is called theright-hand rule, in which you putyour right hand on the wall andkeep it there until you find an exit.• If Theseus applies the right-handrule in this maze, the solution pathlooks like this.The Right-Hand Rule• The most widely known strategyfor solving a maze is called theright-hand rule, in which you putyour right hand on the wall andkeep it there until you find an exit.• If Theseus applies the right-handrule in this maze, the solution pathlooks like this.• Unfortunately, the right-hand ruledoesn’t work if there are loops inthe maze that surround either thestarting position or the goal.• In this maze, the right-hand rulesends Theseus into an infinite loop.A Recursive View of Mazes• It is also possible to solve a mazerecursively. Before you can do so,however, you have to find the rightrecursive insight.• Consider the maze shown at theright. How can Theseus transformthe problem into one of solving asimpler maze?• The insight you need is that a mazeis solvable only if it is possible tosolve one of the simpler mazes thatresults from shifting the startinglocation to an adjacent square andtaking the current square out of themaze completely.A Recursive View of Mazes• Thus, the original maze is solvableonly if one of the three mazes atthe bottom of this slide is solvable.• Each of these mazes is “simpler”because it contains fewer squares.• The simple cases are:– Theseus is outside the maze– There are no directions left to try– 2 –The mazelib.h Interface/* * File: mazelib.h * --------------- * This interface provides a library of primitive operations * to simplify the solution to the maze problem. */#ifndef _mazelib_h#define _mazelib_h#include "genlib.h"/* * This type is used to represent the four compass directions. */enum directionT { North, East, South, West };/* * The type pointT is used to encapsulate a pair of integer * coordinates into a single value with x and y components. */struct pointT { int x, y;};Enumerated Types in C++• It is often convenient to define new types in which thepossible values are chosen from a small set of possibilities.Such types are called enumerated types.enum name { list of element names };• In C++, you define an enumerated type like this:•The mazelib.h interfaces uses enum to define a new typeconsisting of the four compass points, as follows:enum directionT { North, East, South, West};• You can then declare a variable of type directionT and useit along with the constants North, East, South, and West.Structure Types in C++• The other new type mechanism included in the mazelib.hinterface is the creation of a structure type to hold the x and ycomponents of a point within a maze. That definition isstruct pointT { int x, y;};• This definition creates a new type called pointT that has twofields: an int named x and another int named y.• You can declare variables of type pointT just as you wouldvariables of any other type.• Once you have a variable of type pointT, you can refer to theindividual components by using a dot to select the appropriatefield. For example, if currentLocation is a pointT, youcan select its x component by writing currentLocation.x./* * Function: ReadMazeMap * Usage: ReadMazeMap(filename); * ----------------------------- * This function reads in a map of the maze from the specified * file and stores it in private data structures maintained by * this module. In the data file, the characters '+', '-', and * '|' represent corners, horizontal walls, and vertical walls, * respectively; spaces represent open passageway squares. The * starting position is indicated by the character 'S'. For * example, the following data file defines a simple maze: * * +-+-+-+-+-+ * | | * + +-+ + +-+ * |S | | * +-+-+-+-+-+ * * Coordinates in the maze are numbered starting at (0,0) in * the lower left corner. The goal is to find a path from * the (0,0) square to the exit east of the (4,1) square. */void ReadMazeMap(string filename);The mazelib.h Interface/* * Function: GetStartPosition * Usage: pt = GetStartPosition(); * ------------------------------- * This function returns a pointT indicating the coordinates of * the start square. */pointT GetStartPosition();/* * Function: OutsideMaze * Usage: if (OutsideMaze(pt)) . . . * --------------------------------- * This function returns true if the specified point is outside * the boundary of the maze. */bool OutsideMaze(pointT pt);The mazelib.h Interface/* * Function: WallExists * Usage: if (WallExists(pt, dir)) . . . * ------------------------------------- * This function returns true if there is a wall in the indicated * direction from the square at position pt. */bool WallExists(pointT pt, directionT dir);/* * Functions:


View Full Document

Stanford CS 106B - Recursive Backtracking

Download Recursive Backtracking
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Recursive Backtracking and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Recursive Backtracking 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?