Improve this page

Backtracking

Finding solutions by trying partial solutions and then abandoning them if they are not suitable.

• It is often implemented recursively.
• It is generally used when we the solution can be expressed as a set of tuples (or list of n elements)

Example:

• Producing all permutations of a set of values.
• Games: Suduko, word jumbles, etc
• Escaping from a maze.

A general pseudo-code algorithm for backtracking problems:

Explore(decisions):
  - if there are no more decisions to make: stop
  - else, let's handle one decision ourselves and rest by recursions
    for each available choice C for this decision.
      - choose C.
      - Explore the remaining decisions that could follow C.
      - Un-choose C.  # backtracking

Your code should have the above form. While writing the code there may be some little variations too.

NOTE: In case of backtracking usually the extra parameter that we add in the function is meant to remember things that we have chosen on previous calls.

The dice roll problem can also be solved using backtracking concept where we choose (add to the list), explore (handle one case and call the same function for rest cases), and un-choose (remove our choice). Below is the example code.

def dice_roll2(n, lis):
    if n == 0:
        print lis
    else:
        for i in xrange(1, 7):
            # choose
            lis.append(i)
            # explore
            dice_roll2(n-1, lis)
            # un-choose
            lis.pop()  # removing from last

The above code might make more sense as compared to the code written in the example 3 of exhaustive search tutorial because here I am un-choosing the last explored choice.

But, do you think popping out the last element is required? Actually, we have not used list lis after popping out the last element out of it. So, popping out is just another extra operation we are performing in above code. The updated value of lis list is going to persist in the recursion call stack, so it’s better to update only if we need to use.

For example, when I append the i in the lis then I know that it is going to be used in the same recursion call stack, but after popping out the element, the lis isn’t going to be used in that call stack as well as the subsequent call stacks.

I wouldn’t like to use backtracking approach to solve this problem because here I need to explore every possibility thus, its like an exhaustive-search problem.

Let’s look at a slightly modified problem statement.

Write a recursive function that accepts an integer (representing a number of 6-sided dice to roll) and a value (desired sum), and prints all the combinations that add up to exactly the desired sum.

To solve this problem one can just edit the above code and before printing the lis in the base case just check if the sum of elements in lis becomes equal to desired sum or not.

For example:

Input: n = 3, desired sum = 6

Output:

[1, 1, 4]
[1, 2, 3]
[1, 3, 2]
[1, 4, 1]
[2, 1, 3]
[2, 2, 2]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
[4, 1, 1]

Code:

def dice_sum_helper(n, desired_sum, lis):
    if n == 0:
        # checking if sum of elements in lis is equal to desired_sum
        if sum(lis) == desired_sum:
            print lis
    else:
        for i in xrange(1, 7):
            # choose
            lis.append(i)
            # explore
            dice_sum_helper(n-1, desired_sum, lis)
            # un-choose
            lis.pop()  # removing from last


def dice_sum(n, desired_sum):
    dice_sum_helper(n, desired_sum, [])


if __name__ == '__main__':
    dice_sum(3, 6)

The above code is a very bad and inefficient solution to the problem. Here we are exploring every possible branch. In backtracking problems we might need to explore a big tree of possiblities but it’s really important to limit the possible options (if possible) because if you don’t constraint yourself a little bit then the code will take long execution time.

If you make the decision tree or the recursion call stack tree, you will find many branches of the state space tree are not likely to lead to a successful outcome i.e. they are waste of memory and time.

We will not explore that branch where we see the sum of elements in lis list (which is recording the previous outcomes in recursion) becomes more than the desired_sum. Also, we need to ignore those branches where we know that the sum of elements in lis list can never be desired_sum.

Example:

Let’s say you are rolling 3 dices and you want a desired sum of 16. On the first roll you get 2, now we know that even if you get 6 on the other two throws of the dice still you won’t be able to acheive 16 as the desired sum. So there is no point in exploring the branch which has got 2 on its first dict throw.

We need to do two checks before exploring the branches in the recursions, which are:

1. sum_so_far + current_element + 1*(n - 1) <= desired_sum and
2. sum_so_far + i + 6*(n - 1) >= desired_sum

The first condition is checking if the sum_so_far is not too big and second condition is checking if the sum_so_far is not too small.

Example code:

# n is number of dice, lis is solution vector
def dice_sum_helper(n, lis, desired_sum, sum_so_far):
    if n == 0:
        print lis
    else:
        for i in xrange(1, 7):
            if sum_so_far + i + 1*(n - 1) <= desired_sum and\
                    sum_so_far + i + 6*(n - 1) >= desired_sum:
                # choose
                lis.append(i)
                dice_sum_helper(n-1, lis, desired_sum, sum_so_far + i)
                lis.pop()  # removing from last


def dice_sum(number_of_dice, required_sum):
    dice_sum_helper(number_of_dice, [], required_sum, 0)


if __name__ == '__main__':
    num = int(raw_input('Enter number of dices you wish to throw: '))
    desired_sum = int(raw_input('Enter the desired sum: '))
    dice_sum(num, desired_sum)

The asymptotic time complexity would still be O(6^n)

Example 1: Permutation of a string

Write a function that accepts a string as a parameter and outputs all possible rearrangements of the letter in that string.

To solve this problem you can make a decision tree and then simply code it. If you followed the previous posts I wrote then you should be able to code it up.

Example: Possible permutation of {A,B,C}

                      {A, B, C}
                  /	     |	      \
            {A|B,C}     {B|A,C}	  {C|A,B}
           /     \        |	  \       \    \
        {AB|C}  {AC|B}  {BA,C}  {BC,A}  {CA,B}  {CB,A}

Again, as with every recursion problem try to see how is this problem self-similar (optimal substructure) in nature?

You can first choose a letter and then leave the remaining choices of letters to be handled by the later calls of the function.

Base case: An empty string has no permutation, so base case would be when the string gets empty. Recursive case: Here we need to perform Choose, explore and un-choose. We need to form n branches where n is the length of the string. Each branch will start with one character present in the string.

Code 1:

def indent(n):
    for i in range(n):
        print '    ',


cnt = 0


def permute(arr, aux):
    global cnt
    indent(len(aux))
    print 'permute(', arr, ',', aux, ')'
    if len(arr) == 0:
        cnt += 1
        print aux
    else:
        for i in range(len(arr)):
            # choosing
            e = arr[i]
            aux.append(e)
            arr.remove(e)
            # exploring
            permute(arr, aux)
            # un-choose
            arr.insert(i, e)  # appending at index before i
            aux.pop()  # removing from the end


if __name__ == '__main__':
    arr = ['a', 'b', 'c', 'd']
    aux = []
    permute(arr, aux)
    print '\n', cnt

A better code example to achieve same task is:

def permute_helper(s, prefix):
    if len(s) == 0:
        print prefix
    else:
        for i in xrange(len(s)):
            permute_helper(s[:i]+s[i+1:], prefix+s[i])


def permute(s):
    print '\nPermutations are:'
    permute_helper(s, '')


if __name__ == '__main__':
    s = raw_input('enter string: \n')
    permute(s)

Example 1: Sublist

Write a function that finds every possible sub-list of a given list. A sub-list of a list L contains >= 0 of L’s element.

Example:

x = {x1, x2, x3, x4}

Output:

Back

Next