Backtracking: Building Solutions One Step at a Time

Backtracking: Trying Every Path Until One Works

Imagine you are solving a maze. You walk down a path, and if you hit a dead end, you do not give up. You simply walk back to the last spot where you had a choice, pick a different turn, and keep going. You repeat this until you find the exit. This simple, patient idea is exactly what backtracking is.

What is backtracking?

Backtracking is a technique for solving problems by building the answer one piece at a time. After each piece you add, you check: "Does what I have so far still make sense?"

• If it does, you keep going and add the next piece.
• If it does not, you back up one step, undo your last choice, and try a different one.

It is a "brute-force" method, which just means it is willing to try all possible options until it finds the one that works. Because every step is "make a choice, then explore from there," backtracking leans very heavily on recursion (a function that calls itself to handle the next step).

There is one more important helper called a bounding function. This is just a check that looks at the partial answer you have built so far and asks, "Is this still allowed by the rules?" If yes, the search continues down that branch. If no, that whole branch is thrown away (we say it gets *pruned*), and we return to the previous level to try something else. Cutting off bad branches early saves a lot of wasted effort.

A real example: the forgotten phone password

Suppose you set a 4-digit password on your phone, took a nap, and woke up having forgotten it. To keep things simple, assume every digit can only be 0 or 1. How do you get back in?

Two facts make this a perfect backtracking problem:

1. There is only a finite number of possible passwords. Four digits, each either 0 or 1, gives a limited set of combinations to try.
2. You can check any guess. Type a number into the phone — if it unlocks, you were right; if not, it is some other number.

These two things — *a limited set of choices* and *a way to test each result* — are exactly the conditions backtracking needs.

How the search works, step by step

1. Make a choice. Start with an empty password ? ? ? ? and fill it in from the left. Pick the first digit (say 0), then the second, the third, and the fourth, until you have a full number like 0 0 0 0.

2. Check for validity. Enter 0 0 0 0 into the phone. If it unlocks, you are done. If not, this is not the password, so you must try something else.

3. Backtrack and try alternatives. Take one step back to the last digit and change your choice — for example, turn the final 0 into a 1 to get 0 0 0 1. Test that new result.

4. Repeat until solved. Keep going back one step and switching your choice to generate every 4-digit combination of 0s and 1s. Because the password is guaranteed to be one of them, you *will* eventually find it.

Watching it run

If you follow the process carefully, the search explores the numbers in this order:

0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111,
1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111

Notice the rhythm: the search dives all the way down to a full number, tests it, then climbs back up just far enough to flip the next available digit, and dives down again. The ? marks you see along the way are the spots not yet decided. This "dive deep, back up a little, try the other branch" motion is the heartbeat of every backtracking algorithm.

Why this matters

The phone password is a toy example, but the same shape appears in many famous problems: solving a Sudoku, placing queens on a chessboard so none attack each other, finding a path through a maze, or generating all permutations of a list. In every case the recipe is identical:

1. Build a partial solution by making a choice.
2. Check whether it still satisfies the rules.
3. If it fails, backtrack and try a different choice.
4. Repeat until you find a valid complete solution (or run out of options).

Master this one pattern, and a whole family of problems suddenly becomes approachable.