Backtracking

Some tasks cannot be solved in one go. You have to guess, keep building, and only later realize that it doesn’t work out. Backtracking is the strategy of going back at exactly that moment. You undo the last decision and try the next alternative. A Sudoku is solved this way: enter a digit, keep calculating, and if there’s a contradiction, erase the digit again and try the next one. The name says it literally, since “to backtrack” means to retrace one’s steps.

Why brute-force trial and error isn’t enough

For many tasks, the number of possibilities is absurdly large. A classic example is the eight queens puzzle: eight chess queens are to be placed on a board so that none threatens another. Anyone who writes out every single arrangement ends up with billions of cases. A computer would take a long time to work through that, even though the solution is actually simple.

Backtracking therefore saves work by aborting early. If two queens are already in the same row, any further addition is pointless. The algorithm turns back immediately, thereby ignoring millions of arrangements in one stroke. Experts call this “pruning” — cutting off, as with a tree from which entire branches are removed.

So the trick isn’t speed, but avoiding unnecessary work. Nevertheless, backtracking remains slow in the worst case. If no intermediate step can be recognized as wrong ahead of time, everything ends up being tried anyway. That’s why the quality of a backtracking program depends on how well it detects wrong paths early.

Guessing forward, correcting backward

A backtracking method works in steps. It makes a partial decision, checks whether it’s still consistent with the rules, and then goes deeper. If everything is valid and the task is completely solved, you’re done. If, on the other hand, the partial decision turns out to be untenable, it is undone.

You can picture this as a maze. At every fork you choose a passage and remember which passages you haven’t yet tried there. If the path ends at a wall, you walk back to the last fork. This way you search through the entire maze without walking any path twice. Programmers usually implement this with recursion, that is, with a function that calls itself for the next step.

It’s important to distinguish this from a related approach. In backtracking, there are fixed rules that either permit or forbid a partial solution. Optimization methods, by contrast, are about improving a solution only gradually. A common misconception is also to regard backtracking as a mere stopgap. For tasks with hard constraints, it’s often the best known method.

From Sudoku apps to AI models

In everyday life, backtracking is found in puzzle apps, in timetable software, and in programs for shift schedules. The pattern search function in a text editor also uses it. If a pattern allows for several interpretations, the software tries one of them and, upon failure, goes back. This is exactly what makes such searches, in rare cases, very slow.

In AI news, the word now also appears in a second context. Language models, i.e. programs like ChatGPT that generate text word by word, can get stuck while solving a task. Newer systems are trained to discard a line of reasoning they’ve started and try a different approach. Companies like to describe this behavior as backtracking in the thinking process.

The comparison, however, is only partially correct. A classic algorithm discards a branch because a rule is clearly violated. A language model merely estimates that a different path is probably a better fit. For readers of tech news, it’s therefore worth keeping the two meanings apart.