Understanding the backtracking search pattern

Backtracking is the ultimate brute-force search technique for exploring the entire problem space and finding solution states. In some cases, there may be many solution states, but we only need to find one. We start from an initial problem state and, at each step, choose from a set of available choices to move to another state, eventually exploring the entire problem space. Every time we move to a new state, we determine its validity and if it is a solution state by validating it against some constraints. As soon as we reach a solution state, we halt further exploration and return it as the solution to the problem.

It is essential to note that any choice we make at a step may be either independent or dependent on the choices we made earlier.

The search pattern is the classification of problems that can be solved using backtracking to search for solution states in a problem space.

The state-space tree for the backtracking search problem.

In this course, we will learn more about the backtracking search technique and how to identify a problem as a backtracking search pattern problem.

Searching using backtracking

Consider the state space tree below, where we have an initial problem state and k dependent choices that we can make at each step. The depth of the problem space is denoted by n, which is the maximum number of choices we must make to reach a solution state.

At every step, making a different choice may lead to completely different solution states in the end. We recursively make a series of choices until we reach a solution state. Once we reach a solution state, we terminate the search and return it as the solution, and so, we don't need to explore the entire problem space.