% cd your-pc2-directory
 % /homes/cs390cp/pc2/bin/pc2team &

Log in using your individually assigned “teamX” account and password. You can work in the current window/directory, creating a subdirectory for each problem.

• A: Prelude 1 to Backtracking -- Permutations
• B: Prelude 2 to Backtracking -- Subsets
• C: Prelude 3 to Backtracking -- Queens
• D: Little Bishops
• E: Queue
• F: Garden of Eden

Remember: If you've already solved one or more of these problems, try (1) solving again without referring to your old solution, and/or (2) using a different language (Java or C++). If you want to work on an additional problem from the book, let me know.

Hints:

• A: Here is an abstract class that defines the backtracking interface and solution from the textbook. Candidates are the numbers 1..N (or 0..N-1); but prune out the ones that have already appeared in a.
• B: The solution array is a vector of booleans: ai true means element i is in the subset; false means not in the subset. What are the candidate values? (Obviously, true and false.)
• C: The solution array values ai indicate the row in which the queen in column i appears. Choose candidates by pruning all the rows that conflict with (are “attacked by”) queens already placed in the previous columns.
• D: Like Queens, except more Bishops are possible. Solution vector contains n*n booleans indicating if a bishop is located in that space. Need functions that convert square number (0..n*n-1) to row and column values (integer division and mod are your friends). See Queens solution to determine if two bishops are in attack positions (the slope of the line between them is 45 degrees).
• E: Generate people placements from left to right. Need functions to compute number of people who can see left and number who can see right. Prune when impossible situations arise (e.g., tallest person is less than p locations of right).
• F: More exotic application of backtracking.