Backtracking

• a "brute force" algorithmic technique (tries all paths)
• often implemented recursively
• Could involve looking for one solution
  • If any of the paths finds a solution, a solution exists. If none find a solution, no solution exists.
• Could involve finding all solutions
• Idea: it's exhaustive search with conditions

Applications:

• Parsing languages
• Games: anagrams, crosswords, word jumbles, 8 queens, sudoku
• Combinatorics and logic programming. e.g., type inference
• Escaping from a maze

A general pseudo-code algorithm for backtracking problems searching for one solution:

Backtrack(decisions):
  -- if there are no more decisions to make:
     -- if our current solution is valid, return true
     -- else, return false
  -- else let's handle one decision ourselves, and the rest by recursion.
     For each available VALID choice C for this decision:
     -- Choose C by modifying parameters
     -- Explore the remaining decisions that could follow C. If any of them find a solution, return true
     -- Un-choose C by returning parameters to original state (if necessary)

  -- If no solutions were found, return false

A general pseudo-code algorithm for backtracking problems searching for all solution:

Backtrack(decisions):
  -- if there are no more decisions to make:
     -- if our current solution is valid, ADD IT TO OUR LIST OF FOUND SOLUTIONS
     -- else, DO NOTHING OR RETURN

  -- else let's handle one decision ourselves, and the rest by recursion.
     For each available VALID choice C for this decision:
     -- Choose C by modifying parameters
     -- Explore the remaining decisions that could follow C. KEEP TRACK OF WHICH SOLUTIONS THE RECURSIVE CALLS FIND.
     -- Un-choose C by returning parameters to original state (if necessary)

  -- RETURN THE LIST OF SOLUTIONS FOUND BY ALL THE HELPER RECURSIVE CALLS

Backtracking model

• Choosing
  1. We generally iterate over decisions. What are we iterating over here? What are the choices for each decision? Do we need a for loop?
• Exploring
  1. How can we represent that choice? Should we modify the parameters and store our previous choices? Do we need to use a helper due to extra parameters?
  2. How should we restrict our choices to be valid?
  3. How should we use the return value of the recursive calls? Are we looking for all solutions or just one?
• Un-Choosing
  1. How do we un-modify the parameters from the Exploring step? Do we need to un-modify, or are they copied? Are they un-modified at the same level as they were modified?
• Base Case
  1. What should we do in the base case when we are out of decisions (usually return true)?
  2. Is there a case for when there aren't any valid choices left or a "bad" state is reached (usually return false)?
  3. Are the base cases ordered properly? Are we avoiding arms-length recursion?

Dice roll sum

• Write a function diceSum that accepts two integer parameters: a number of dice to roll, and a desired sum of all dice values. Output all die values that add up exactly to that sum.

  diceSum(2, 7):
  {1, 6}
  {2, 5}
  {3, 4}
  {4, 3}
  {5, 2}
  {6, 1}
  
  diceSum(3, 7):
  {1, 1, 5}
  {1, 2, 4}
  {1, 3, 3}
  {1, 4, 2}
  {1, 5, 1}
  {2, 1, 4}
  {2, 2, 3}
  {2, 3, 2}
  {2, 4, 1}
  {3, 1, 3}
  {3, 2, 2}
  {3, 3, 1}
  {4, 1, 2}
  {4, 2, 1}
  {5, 1, 1}
  

Easier solution: First just output all possible combinations of values that could appear on the dice. This is just exhaustive search! In general, starting with exhaustive search and then adding conditions is not a bad idea.

diceSum(2, 7):  #36 possibilities
{1, 1}  {3, 1}  {5, 1}
{1, 2}  {3, 2}  {5, 2}
{1, 3}  {3, 3}  {5, 3}
{1, 4}  {3, 4}  {5, 4}
{1, 5}  {3, 5}  {5, 5}
{1, 6}  {3, 6}  {5, 6}
{2, 1}  {4, 1}  {6, 1}
{2, 2}  {4, 2}  {6, 2}
{2, 3}  {4, 3}  {6, 3}
{2, 4}  {4, 4}  {6, 4}
{2, 5}  {4, 5}  {6, 5}
{2, 6}  {4, 6}  {6, 6}

diceSum(3, 7):  #216 possibilities
{1, 1, 1}
{1, 1, 2}
...
{6, 6, 6}

Show the top part of the decision tree for diceSum(4,7), where we maintain the "chosen values in first few dice" and "number of remaining dice where a value has not yet been chosen". Initially, chosen= and available=4. At the next level, we have six children, with chosen={1}, available={3}, and so on.

Code for easier solution:

def diceSum(dice, desiredSum):
  chosen = []
  diceSumHelper(dice, desiredSum, chosen)

def diceSumHelper(dice, desiredSum, chosen):
  if dice == 0:
    if sumAll(chosen) == desiredSum:
      print(chosen)  #solution found, base case
  else:
    for i in range(1, 7):
      diceSumHelper(dice - 1, desiredSum, chosen + [i])

def sumAll(l):
  sum = 0
  for i in l:
    sum += i
  return sum

Wasteful decision tree. Show the decision tree and the chosen lists that are output.

Optimizations

• We need not visit every branch of the decision tree.
  • Some branches are clearly not going to lead to success.
  • We can preemptively stop, or prune, these branches.
• Inefficiencies in our dice sum algorithm:
  • Sometimes the current sum is already too high, i.e., even rolling 1 for all remaining dice would exceed the desired sum.
  • Sometimes the current sum is already too low, i.e., even rolling 6 for all remaining dice would be less than the desired sum.
  • The code must recompute the sum many times, e.g., 1+1+1, 1+1+2, 1+1+3, 1+1+4, and so on. Better if we remember that 1+1=2, to replace the computation with 2+1,2+2,2+3,...

Code for optimized solution:

def diceSum(dice, desiredSum):
  chosen = []
  diceSumHelper(dice, 0, desiredSum, chosen)

def diceSumHelper(dice, curSum, desiredSum, chosen):
  if dice == 0:
    if curSum == desiredSum:
      print(chosen)  #solution found, base case
  elif curSum + 1*dice > desiredSum or curSum + 6*dice < desiredSum:  # invalid state base case
    return
  else:
    for i in range(1, 7):
      diceSumHelper(dice - 1, curSum + i, desiredSum, chosen + [i])

Question (that I will not answer): How would you modify diceSum so that it prints only unique combinations of dice, ignoring order? e.g., do not print both {1,1,5} and {1,5,1}.

diceSum(2, 7):
  {1, 6}
  {2, 5}
  {3, 4}

erased:
  {4, 3}
  {5, 2}
  {6, 1}


diceSum(3, 7):
  {1, 1, 5}
  {1, 2, 4}
  {1, 3, 3}
erased:
  {1, 4, 2}
  {1, 5, 1}
  {2, 1, 4}
printed:
  {2, 2, 3}
erased:
  {2, 3, 2}
  {2, 4, 1}
  {3, 1, 3}
  {3, 2, 2}
  {3, 3, 1}
  {4, 1, 2}
  {4, 2, 1}
  {5, 1, 1}

Knapsack problem: Given N items where each item has some weight and profit associated with it and also given a bag with capacity W, [i.e., the bag can hold at most W weight in it]. The task is to put the items into the bag such that the sum of profits associated with them is the maximum possible.

A simple solution is to consider all subsets of items and calculate the total weight and profit of all subsets. Consider the only subsets whose total weight is smaller than W. From all such subsets, pick the subset with maximum profit.

To consider all subsets of items, there can be two cases for every item.

• Case 1: The item is included in the optimal subset.
• Case 2: The item is not included in the optimal set.

The maximum value obtained from ‘N’ items is the max of the following two values.

• Case 1 (include the Nth item): Value of the Nth item plus maximum value obtained by remaining N-1 items and remaining weight i.e. (W-weight of the Nth item).
• Case 2 (exclude the Nth item): Maximum value obtained by N-1 items and W weight.

Solution

def knapSack(W, wt, val, n): 
    # Base Case 
    if n == 0 or W == 0: 
        return 0
 
    # If weight of the nth item is 
    # more than Knapsack of capacity W, 
    # then this item cannot be included 
    # in the optimal solution 
    if (wt[n-1] > W): 
        return knapSack(W, wt, val, n-1) 
 
    # return the maximum of two cases: 
    # (1) nth item included 
    # (2) not included 
    else: 
        return max( 
            val[n-1] + knapSack( 
                W-wt[n-1], wt, val, n-1), 
            knapSack(W, wt, val, n-1)) 

profit = [60, 100, 120]
weight = [10, 20, 30]
W = 50
n = len(profit)
print knapSack(W, weight, profit, n)

Exercise: modify the program above to also print the weights and profits of all items that are included in the final solution