Assignment #2 – Recursion and Backtracking

Due June 19, 2008

(You must submit electronically, as well as hand in a printed copy.)

Introduction to Backtracking

In general, a recursive function or method is one that makes a call to itself. In class, the recursive algorithms that we saw were generally structured as follows:

Check if the subproblem being solved for is small enough to solve directly (i.e., is it a 'base case'). If it is, return the solution to the subproblem.
Otherwise recursively call the algorithm on a smaller version of the problem, and then use the solution to the smaller problem to determine the solution to the original problem.

This approach works well for problems whose solutions can be expressed in terms of solutions to smaller subproblems. For example, a recursive algorithm for calculating n! (n factorial) easily follows from the fact that n! = n*(n-1)! when n>0 and n! = 1 when n=0.

Recursion is also typically used by algorithms that employ backtracking. We introduce the idea of backtracking by way of an example.

Consider the following problem. You are at the entrance to a large maze that you need to find your way through. Initially, there's two directions you can travel in the maze: either left or right. If you choose to go right, then the subproblem you have to solve is how to find your way out of the maze having gone right in the initial step; if you choose to go left, then the subproblem you have to solve is how to find your way out of the maze having gone left in the initial step. At each junction in the maze you have to choose some direction to go. After making a choice at each junction, you have a smaller subproblem to solve: how to get out of the maze having made the choices you've made thus far. But there's a catch. What if you made a choice that leads you to a dead end? That is, you may end up trying to solve a "subproblem" that has no solution. If you're lucky, this won't happen and each choice you make will get you closer to the maze's exit. If you're unlucky, then you'll have to return to a junction point that you previously visited and make a different choice for which direction to go. In other words, you will have to backtrack.

Suppose we want to write a Python function to help us find a path through the maze. How can we use recursion in our function to do the backtracking described above? Lets call our function mazeSolve(path). This function returns True if there exists a way out of the maze using the sequence of choices that's been made thus far (stored in path), or False otherwise. A very high-level implementation of the mazeSolve function is as follows.

def mazeSolve(path):

if the current sequence of choices in path leads to a dead end: return False
if the current sequence of choices leads to the maze exit (without any more junctions): return True
# (if we reached this point, it means we have to make a choice of direction at another junction)
for each choice of direction at the current junction:

add the choice to path
invoke mazeSolve recursively, with the updated path variable (that is, call mazeSolve(path) )
if the return value is True, then a path out of the maze has been found and we immediately return True to the caller
if the return value is False, then the choice we just made resulted in a dead end and we have to try the other choices

if every possible choice of direction at the current junction leads to a dead end, we have to backtrack to the previous junction and make a different choice there. This is simply done by returning False.

There are a lot of details omitted from the above description, but it should give you an idea of how recursion can be used to do backtracking. In particular, each recursive call to mazeSolve advances to the next junction in the maze, and whenever a call to mazeSolve returns, it backtracks to an earlier position in the maze.

In the context of the maze problem and the description we gave above, the term 'backtracking' has a taken on a very specific meaning: you are physically backtracking to a previous position in the maze because a choice you made led you to a dead end. More generally, backtracking is a technique for systematically exploring the set of all possible solutions to a problem. In the maze problem, for example, the set of all possible solutions is the set of all sequences of choices that can be made at junctions. mazeSolve explores this set systematically until it hits upon a correct solution.

Although mazeSolve stops after finding one correct solution, there may be other ways through the maze. One can modify the technique given above to find all possible ways through the maze. Think about how you might do this and what changes you would need to make. You will need to do something similar in the problem explained below.

The Problem – Escaping an n-Dimensional Universe

The problem that you need to solve in this assignment shares some similarities with finding a path through a maze, but it is ultimately more complex. You are trapped in an n-dimensional universe, where n is a positive integer, and you have to find your way out. The universe is divided into a grid of k₁ x k₂ x ... x k_n cells, and each cell's position in the universe can be described by an n-element tuple containing only non-negative integers. The origin of the universe is at (0,0,...,0) (a tuple containing n 0's). In general, a cell located at position (i₁,i₂,...,i_n) is i₁ cells from the origin along the first dimension, i₂ cells from the origin along the second dimension, and so forth.

Two cells (i₁,i₂,...,i_n) and (i'₁,i'₂,...,i'_n) in the universe are orthogonally adjacent if there exists some j such that either i_j = i'_j + 1 or i_j = i'_j - 1, and all other coordinates are equal. For example, in a two dimensional universe, two cells are orthogonally adjacent if one cell is left, right, above, or below the other cell. Cells that are touching but on a "diagonal" from each other are not orthogonally adjacent. (See the examples section below.)

Your movement in the universe is constrained by the following rules:

You can only move one cell at a time, and you can only move to cells that are orthogonally adjacent to your current position. For example, in a two dimensional universe this means that you can only move up, down, left, or right. In a three dimensional universe, this means you can only move up, down, left, right, forward or back.
You can visit any given cell at most once.
Once you reach a cell that allows you to escape the universe, you must escape. That is, after reaching an escape cell, you cannot keep making moves in hopes of finding another escape cell if you don't like the particular one on which you landed.
You cannot move off the "edge" of the universe, and the universe does not "wrap around". (This rule is clarified in the examples below.)

The universe contains obstacles that you must handle. In particular, a cell possibly contains one of the following:

Bomb. If you move to a cell with a bomb, it will kill you, and you will have failed to escape the universe.
Gold Troll. If you move to a cell containing a gold troll, then you must pay the troll at least one gold bar. If you don't pay the troll, he will kill you. If you pay the troll one gold bar, then the troll will let you live, and if you pay the troll two gold bars, then he will let you live, and he will also give you one silver bar.
Silver Troll. If you move to a cell containing a silver troll, then you must pay the troll at least one silver bar. If you don't pay the troll, he will kill you. If you pay the troll one silver bar, then the troll will let you live, and if you pay the troll two silver bars, then he will let you live, and he will also give you one gold bar.

You cannot pay a gold troll with silver bars, or a silver troll with gold bars. Also, trying to give a troll more than two bars does not mean he will give you extra bars of the other type in return. You pay either one bar to live, or two bars to live and get one bar of the other type in return.

It probably does not make sense to you that a silver troll will give you a gold bar in exchange for an extra silver bar, since gold is traditionally more valuable than silver. However, nothing in this universe makes sense, which is the reason you want to escape it.

You start at some cell in the universe with some number of gold and silver bars in your possesion. The start cell does not contain any obstacles (i.e., it is empty). To escape the universe you must reach an "escape" cell. Such a cell may or may not exist in the universe, and even if it does exist, it may not be reachable.

There are a number of interesting questions that we can ask:

Does there exist a path from the starting cell that allows you to escape the universe without being killed?
What is a path (if any) that allows you to escape?
What is the maximum number of gold bars that you can possibly have when you escape?
What is the minimum total number of bars (silver + gold) with which you need to start so that you can escape the universe?

There are other similar questions that we can ask, but we will limit ourselves to the ones above.

Examples

The following is an example of a two dimensional universe that's divided into a 3 x 3 grid of cells.

You start at cell (1,1). Since you are restricted to only moving to orthogonally adjacent cells, you can only move up, down, left, and right. Hence, from cell (1,1) you can only move to (1,0), (1,2), (2,1), or (0,1). Even though cell (0,0) and (2,2) are touching (1,1), you cannot move directly to these cells from (1,1) since they are not orthogonally adjacent to (1,1). Cells (1,0) and (0,1) contain bombs, so you don't want to move to either of these. This means that the escape cell at (0,0) is not reachable.

Lets try answering each of the questions asked at the end of the previous section:

Does there exist a path from the starting cell that allows you to escape the universe without being killed? and What is a path (if any) that allows you to escape? Whether a path of escape exists depends on the number of gold and silver bars you start with. If you start with at least one gold bar, then you can move to (1,2), pay the troll, and then move to (2,2) to escape. If you start with at least one silver bar, then you can move to (2,1), pay the troll, and then move to (2,2) to escape. If you start with no silver or gold bars, then it's not possible to escape.
What is the maximum number of gold bars that you can possibly have when you escape? This depends on the number of gold and silver bars you start with. If you start with no silver bars and at least one gold bar, then the maximum number of gold bars with which you can escape is one fewer than the number with which you start. If you start with one silver bar, then the maximum number of gold bars with which you can escape is the same as the number with which you start. This is done by following the path that visits the silver troll. If you start with at least two silver bars, then maximum number of gold bars with which you can escape is the number with which you start plus one. This is done by following the path that visits the silver troll and giving him two bars.
What is the minimum total number of bars (silver + gold) with which you need to start so that you can escape the universe? The minimum total number of bars with which you need to start so that you can escape is one.

Here's another example of a two dimensional universe:

Observe that cells can be empty. Because of the rule that says you cannot move off the edge of the universe and that the universe does not "wrap around", you cannot move directly from (0,0) to (0,2) by moving "down". Moving up to (0,1) is not an option since there is a bomb there.

Does there exist a path from the starting cell that allows you to escape the universe without being killed? and What is a path (if any) that allows you to escape? There is a path of escape as long as you have at least one gold bar. You first move to (1,0), where you must pay a gold bar to the troll. From (1,0) you can move to (1,1), then (1,2), and finally (0,2).
What is the maximum number of gold bars that you can possibly have when you escape? This depends on the number of gold and silver bars you start with. If you start with at least one gold bar and one or less silver bars, then the maximum number of gold bars with which you can escape is one fewer than the number with which you start. If you start with at least one gold bar and at least two silver bars, then the maximum number of gold bars with which you can escape is the same as the number with which you start. This is done by following a path that visits the silver troll and giving him two bars.
What is the minimum total number of bars (silver + gold) with which you need to start so that you can escape the universe? The minimum total number of bars that you need to spend in order to escape is one.

Details

You are going to write a class called Universe and implement four methods, each of which answers one the questions posed above.

The class is already defined for you in the starter code in universe.py. Download this module and inspect the class definition. Notice that an instance of Universe has three attributes: n, dimensions, universe. These attributes are intialized when an instance is created. The meaning of these attributes is as follows:

n This is a positive integer representing the number of dimensions in the universe.
dimensions This is an n-element tuple specifying how the universe is divided into a grid of cells. Each element of the tuple is a positive integer. If the tuple is (k₁, k₂,...,k_n), then the universe is divided into a grid of k₁ x k₂ x ... x k_n cells. There are k₁ cells along the first dimension, k₂ cells along the second dimension, and so forth.
universe This argument is an "n-dimensional list" and defines the contents of each cell in the universe. By "n-dimensional list" we mean a list that has been nested multiple times, where the number of "nestings" depends on n, the number of dimensions in the universe. In a one dimensional universe, this argument is just a simple list. In a two dimensional universe, this argument is a list of lists. In a 3 dimensional universe, this argument is a list of list of lists, and so forth. You can determine the contents of any cell by addressing elements in universe with the coordinates of the cell's position. For example, in a three dimensional universe, the contents of the cell at (0,3,5) is universe[0][3][5]. The contents of a given cell will be one of the following predefined constants:
- EMPTY The cell is an empty cell.
- ESCAPE The cell is an escape cell.
- GOLD The cell contains a gold troll.
- SILVER The cell contains a silver troll.
- BOMB The cell contains a bomb.
(These constants are defined as integer values in the starter code.)

The class defines four methods, which you have to implement. They are as follows:

def does_escape_exist(self, start, gold, silver)
def find_escape_path(self, start, gold, silver)
def max_gold_obtainable(self, start, gold, silver)
def min_bars_required(self, start)

In all of the above methods, the start argument is an n-element tuple, and the gold and silver arguments are non-negative integers.

The method does_escape_exist(self, start, gold, silver) returns boolean True if you can escape the universe starting from the start cell, having gold gold bars and silver silver bars in your possession initially. The method returns False otherwise.

The method find_escape_path(self, start, gold, silver) returns a path of escape in the universe, assuming that you start from the start cell, and have gold gold bars and silver silver bars in your possession initially. The path returned by this method is represented by a list, and each element in the list is an n-tuple representing a cell position. The order of elements in the list corresponds to the order in which you visit cells as you move through the universe. The first element in the list should be the position of the start cell, and the last element should be the position of an escape cell. If no path of escape exists, this method returns None.

The method max_gold_obtainable(self, start, gold, silver) returns an integer representing the maximum number of gold bars with which you can escape starting from the start cell, having gold gold bars and silver silver bars in your possession initially. If it is not possible to escape, then return -1.

The method min_bars_required(self, start) returns an integer representing the minimum total number of bars (silver + gold) that you need to have initially so that you can escape the universe starting from the start cell. If it is not possible to escape no matter how many bars you start with, then this method returns -1.

Testing

To get you started with testing, and to provide you some examples of how we expect the methods to work, we're providing you with testuniverse.py.

We recognize that writing a set of test cases, complete with docstrings, can be very time consuming. As such, we're only asking that you submit test cases for the does_escape_exist method. The set of tests that you write should be sufficient to convince yourself (and us) that your code is correct.

Note: even though you don't have to submit your tests for the other methods, you should still test them!

Marks Breakdown

Marking will be done according to the "Assignment Expectations" laid out on the course website. Solutions for does_escape_exist and find_escape_path will be worth roughly 50% of your grade, a solution for max_gold_obtainable will be worth roughly 30%, and a solution for min_bars_required will be worth roughly 20%.

Hints and Comments

DON'T PANIC! Although the problem looks very complicated, there is a very elegant and general solution. Read the problem over several times and wrap your head around what you're being asked to do.
Use backtracking and recursion in your solution.
Don't go overboard testing your code for universes in higher dimensions. Testing for up to n=3 is sufficient. We will only run your code in universes in which n < 5.
If your solution involves special casing the various configurations of gold trolls, silver trolls, and bombs that may appear in the universe, then you are probably on the wrong track. For example, don't try reasoning about obscure cases like what to do if a gold troll is surrounded by silver trolls. Try to approach the problem more generally.
Start by thinking about how to implement does_escape_exist and find_escape_path without worrying about the other two methods. If you can implement a solution for these two methods, then a solution for max_gold_obtainable and min_bars_required should only involve a moderate amount of additional work.
Be careful not to duplicate code. Although there are four separate methods that you are implementing, you should try to design your solution in such a way that allows you to share as much code as possible between these four methods.
As always, ask questions on the discussion board if something isn't clear, or visit the instructor in office hours, or visit the Help Centre.

What To Submit

Submit the following.

universe.py Implement the four methods described earlier. Make sure you add docstrings to these methods, as they are not provided in the starter code.
testuniverse.py This should include your test cases for the does_path_exist method. You don't have to submit your tests for the other methods, but still be sure to test them!

You need to submit electronically, and also submit a printed copy of your code. Be sure that you include your cdf id and student number in the hard copy that you hand in.