In previous courses you have seen the basic idea of recursion to solve mathematical problems such as the factorial function or Fibonacci numbers. In this lab, you will solve recursive problems using more advanced approaches known as backtracking and memoization.
This lab was originally developed by Dr. Michael Kirkpatrick.
Both backtracking and memoization are general strategies that are used for a wide variety of problems, but are particularly useful in constraint satisfaction problems. As an example, consider a program that solves Sudoku or crossword puzzles. The rules of the puzzle (such as only one letter or number per box) are constraints that have to be satisfied by a valid solution. Along the way, the algorithm (or human) that is solving the puzzle creates partial solutions that satisfy the constraints, repeatedly considering the next step to take.
In a backtracking strategy, the algorithm recursively adds a new value to partial solution. If all the constraints are still valid, then the algorithm would add another value. This process repeats until either the problem is solved or one of the constraints would be violated. When that happens, the algorithm throws away the most recently added value (backtracking to a previous valid partial solution) and tries again with a different value. If no other values can be used to replace this value (for instance, they've all been tried already), the algorithm backtracks again and again until it reaches a valid partial solution.
Memoization provides a different approach that is very powerful for
recursive problems that have an overlapping structure in which
sub-problems are repeatedly solved. As an example, consider the fifth
Fibonacci numbers: Fib(5) = Fib(4) + Fib(3). We have to compute both
Fib(3) and Fib(4). But note that computing Fib(4) also
requires solving Fib(3)! That is, the work to solve Fib(5)
overlaps with the work to solve Fib(4). Instead of solving Fib(3)
twice, the memoization approach involves solving it once and storing
the solution in a table that can be consulted later.
Note that memoization is closely related to Dynamic Programming. Dynamic Programming describes a category of algorithms that constructs a solution to a complete problem by building up from solutions to overlapping instances of smaller sub-problems.
Each of these files contain comments about how to implement the algorithm. Note that you should not be writing much code for this lab, as they can be solved quite neatly with recursion. Some of this code can be quite tricky, though, so you are strongly encouraged to work out some examples of how the recursion works on paper first.
The 8 Queens Problem is based on the game of chess. Queens in chess can move any number of spaces in a single direction (including diagonals) to capture another piece. The goal of the problem is to place 8 queens on an 8x8 chess board so that none of them can attack any of the others. We have generalized this problem to require placing N queens on an NxN board.
The Fibonacci numbers are often implemented with a very basic recursive routine:
public int fib(int n) {
if (n <= 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return fib(n - 1) + fib(n - 2);
}
}This approach is fine for small values of n, but does very poorly as
n increases. (Try running this with n set to 40 or 50 and see for
yourself!) Memoization, however, provides a very efficient
solution. The general approach for the recursion can be described in
pseudo-code as follows:
if (base case)
return correct value
else
if fib(n) has not been memoized
memoize fib(n) by recursively calculating fib(n-1) and fib(n-2)
return memoizedTable[n]The last problem to solve in this lab is the Subset Sum Problem. As an example, consider the set of numbers { 2, 5, 10, 13 }. Does there exist a subset that adds up to the sum 7? (Yes: 2 + 5 = 7) Does there exist a subset that adds up to 9? (No: We would need a second copy of 2.) Note that it doesn't matter whether or not the subset is unique. If we asked if there was a subset that adds up to 15, there are two (2 + 13 and 5 + 10). All that matters is that there is at least one such subset.
In the backtracking approach, we try two recursive calls each time:
with and without a value removed from the set. For instance, assume we
are looking for the sum 17 (called as subsetSum(set, 17)). If there is a subset that
includes 2, then subsetSum(set \ { 2 }, 15)
would return true. (Recall that \(S \setminus R\) denotes set subtraction; the
result is all of the elements of \(S\) after all of the elements of \(R\)
have been removed.) On the other hand, if there is no subset with 2
included, then we can backtrack and try again by calling subsetSum(set \ { 2 }, 17).
In the dynamic programming approach, we keep a table that keeps track of all possible subset sums. Starting with the empty subset, the only possible sum is 0. Then, if we consider 2, we have possible sums 0 and 2. Next, we consider 5, which creates possible sums 0, 2, 5, and 7. And so on. To implement this memoization table, we create a 2-dimensional array that is size (N+1) x (SUM+1), where N is the size of the set. If we were to compute this table for the set above and for the sum 12, the final values would look like this:
0 1 2 3 4 5 6 7 8 9 10 11 12
+---+---+---+---+---+---+---+---+---+---+---+---+---+
Row 0: | T | F | F | F | F | F | F | F | F | F | F | F | F | [Start with empty set]
+---+---+---+---+---+---+---+---+---+---+---+---+---+
Row 1: | T | F | T | F | F | F | F | F | F | F | F | F | F | [Add 2 to the previous subset sum]
+---+---+---+---+---+---+---+---+---+---+---+---+---+
Row 2: | T | F | T | F | F | T | F | T | F | F | F | F | F | [Add 5 to each of the previous subset sums]
+---+---+---+---+---+---+---+---+---+---+---+---+---+
Row 3: | T | F | T | F | F | T | F | T | F | F | T | F | T | [Add 10 to each of the previous subset sums]
+---+---+---+---+---+---+---+---+---+---+---+---+---+
Row 4: | T | F | T | F | F | T | F | T | F | F | T | F | T | [Add 13 to each of the previous subset sums]
+---+---+---+---+---+---+---+---+---+---+---+---+---+
The answer to the question is found in the last entry of the Nth row. Note that this was set to true when 10 was added (a subset of 2 + 10 = 12).
Submit your completed BacktrackingQueens, DynamicFibonaci,
BacktrackingSubsetSum, and DynamicSubsetSum code as a src.zip
through Autolab.