What is Backtracking ?

Backtracking is an improvement of the brute force approach. It systematically searches for a solution to a problem among all available options. In backtracking, we start with one possible option out of many available options and try to solve the problem if we are able to solve the problem with the selected move then we will print the solution else we will backtrack and select some other option and try to solve it. If none of the options work out, we will claim that there is no solution for the problem.

Backtracking is a form of recursion.The usual scenario is that you are faced with a number of options, and you must choose one of these. After you make your choice you will get a new set of options, Just what set of options you get depends on what choice you made. This procedure is repeated over and over until you reach a final state. if you made a good sequence of choices, your final state is a goal state, if you didn’t it isn’t. Backtracking can be thought of as a selective tree/graph traversal method. The tree is a way of representing some initial starting position (the root node) and a final goal state (one of the leaves). Backtracking allows us to deal with situations in which a raw brute-force approach would explode into an impossible number of options to consider. Backtracking is a sort of refined brute force. At each node, we eliminate choices that are obviously not possible and proceed to recursively check only those that have potential.

What’s interesting about backtracking is that we back up only as far as needed to reach a previous decision point with an as-yet-unexplored alternative. In general, that will be at the most recent decision point. Eventually, more and more of these decision points will have been fully explored and we will have to backtrack further and further. If we backtrack all the way to our initial state and have explored all alternatives from there, we can conclude the problem is unsolvable. In such case we will have done all the work of the exhaustive recursion and known that there is no viable solution possible.

Example Algorithms of Backtracking –

• Binary Strings – generating all binary strings
• Generating k-ary strings
• N-Queens Problem
• The Knapsack Problem
• Generalized Strings
• Hamiltonian Cycles
• Graph Coloring Problem

Backtracking Problems & Solutions –

Problem 1 – Generate all the binary strings with n bits. Assume A [0….n-1] is an array of size n.

Solution –

def appendAtFront(x, L):
    return [x + element for element in L]

def bitStrings(n):
    if n == 0:
        return []
    if n == 1:
        return ["0","1"]
    else:
        return (appendAtFront("0", bitStrings(n-1)) + appendAtFront("1", bitStrings(n-1)))
    
print(bitStrings(4))

Problem 2 – Path Finding Problem

Given an n X n matrix of blocks with a source upper left block, we want to find a path from the source to the destination (the lower right block). We can only move downwards and to the left. Also a path is given by 1 and a wall is given by 0. The following is an example of a maze (the grey cells are inaccessible).

We can now outline a backtracking algorithm that returns an array containing the path in a coordinate form. For example, for the example above the solution is

\left( 0,0 \right) \to \left( 0,1 \right)\to \left( 1,1 \right) \to \left( 1,2 \right) \to \left( 1,2 \right) \to \left( 3,2 \right) \to \left( 3,3 \right)

Solution –

Algorithm –

If we have reached the destination point

return an array containing only the position of the destination

else

• Move in the forward direction and check if this leads to a solution
• if option a does not work, then move down
• if either work, and the current position to the solution obtained at either 1 or 2

def pathFinder(Matrix, position, N):
    # return a list of the path taken
    if position == (N-1, N-1):
        return [(N-1,  N-1)]
    x, y  = position
    if x + 1 < N and Matrix[x + 1][y] == 1:
        a = pathFinder(Matrix, (x + 1, y), N)
        if a != None:
            return [(x, y)] + a 
    if y + 1 < N and Matrix[x][y + 1] == 1:
        b = pathFinder(Matrix, (x, y + 1), N)
        if b != None:
            return [(x, y)] + b 

Matrix = [[1,1,1,1,0], [0,1,0,1,0],[0,1,0,1,0],[0,1,0,0,0],[1,1,1,1,1]]
print(pathFinder(Matrix, (0, 0), 5))