Backtracking: Introduction

About the pattern

Imagine we’re planning an exciting road trip through a city, aiming to visit all the places we want to see while covering the shortest distance possible. However, there are some conditions we must follow: we can’t revisit the same place more than once, and we must end up back where we started. This problem, known as the city road trip problem, requires finding the optimal route that satisfies these conditions. It’s a classic example where the concept of backtracking comes into play, allowing us to explore different paths until we find the shortest one that fulfills all the conditions.

Let’s first see how this problem can be solved using a brute-force approach. We can do this by exploring routes in every single way we can visit the places. We have to write down every possible route, check how long each one is, and then pick the shortest one. But as our list of places grows, it makes this approach computationally impractical for a large number of routes.

Now, let’s look at a backtracking approach to solve the same problem. With backtracking, we can start by picking a place and choose the next place to visit that’s close and follows our conditions. We move back (backtrack) to the previous place if the current place has been visited before or if we cannot move forward to any place from here. We check these conditions on each of our choices because we do not want to break any of our road trip rules. We keep doing this, choosing, checking conditions, and backtracking until we’ve visited all the places according to the requirements. At every step, we choose the closest place, ensuring we have chosen the shortest path to visit all the places we want to see.

Backtracking is an algorithmic technique for solving problems by incrementally constructing choices to the solutions. We abandon choices as soon as it is determined that the choice cannot lead to a feasible solution. On the other side, brute-force approaches attempt to evaluate all possible solutions to select the required one. Backtracking avoids the computational cost of generating and testing all possible solutions. This makes backtracking a more efficient approach. Backtracking also offers efficiency improvements over brute-force methods by applying constraints at each step to prune non-viable paths.

As seen in the above example, backtracking works by exploring all potential routes toward a solution step-by-step. It can be visualized as traversing a state space treeA tree that shows all the possible states of the problem, from an initial state to the ending state., where each node represents a partial solution. Starting from the root (an empty solution), backtracking moves deeper into the tree, exploring branches (choices) until it finds a feasible solution or reaches a leaf node that cannot be extended into a complete solution. Upon reaching a dead end, the algorithm backtracks to the previous state and explores a different branch. This process is repeated, with constraints applied at each step to avoid exploring paths that cannot lead to a successful, feasible solution.

Let’s look at the visualization of the space state tree below to better understand the working: