Recursive BacktrackingSolving a MazeThe Right-Hand RuleA Recursive View of MazesSlide 5The mazelib.h InterfaceEnumerated Types in C++Structure Types in C++Slide 9Slide 10Slide 11The SolveMaze FunctionTracing the SolveMaze FunctionRecursion and ConcurrencyThe P = NP QuestionRecursion and GamesGame TreesThe Essential Idea about Recursive GamesExercise: Generating SubsetsThe EndRecursive 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 to illustrate recursive backtracking is the problem of solving a maze, which has a long history in its own right.•The most famous maze in history is the labyrinth of Daedalus in Greek mythology where Theseus slays the Minotaur.•There are passing references to this story in Homer, but the best known account comes from Ovid in 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 strategy for solving a maze is called the right-hand rule, in which you put your right hand on the wall and keep it there until you find an exit.•If Theseus applies the right-hand rule in this maze, the solution path looks like this.•Unfortunately, the right-hand rule doesn’t work if there are loops in the maze that surround either the starting position or the goal.•In this maze, the right-hand rule sends Theseus into an infinite loop.A Recursive View of Mazes•It is also possible to solve a maze recursively. Before you can do so, however, you have to find the right recursive insight. •Consider the maze shown at the right. How can Theseus transform the problem into one of solving a simpler maze?•The insight you need is that a maze is solvable only if it is possible to solve one of the simpler mazes that results from shifting the starting location to an adjacent square and taking the current square out of the maze completely.A Recursive View of Mazes•Thus, the original maze is solvable only if one of the three mazes at the 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 /* * 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;};The mazelib.h InterfaceEnumerated Types in C++•It is often convenient to define new types in which the possible 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 type consisting of the four compass points, as follows:enum directionT { North, East, South, West};•You can then declare a variable of type directionT and use it along with the constants North, East, South, and West.Structure Types in C++•The other new type mechanism included in the mazelib.h interface is the creation of a structure type to hold the x and y components of a point within a maze. That definition isstruct pointT { int x, y;};•This definition creates a new type called pointT that has two fields: an int named x and another int named y.•You can declare variables of type pointT just as you would variables of any other type.•Once you have a variable of type pointT, you can refer to the individual components by using a dot to select the appropriate field. For example, if currentLocation is a pointT, you can select its x component by writing currentLocation.x./* * 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;};/* * 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 Interfaceskip codepage 2 of 4page 1 of 4/* * Function: ReadMazeMap * Usage: