Backtracking is a way of searching through a space of possible solutions by extending a partial solution one decision at a time. Whenever a partial solution is found that cannot lead to any valid complete solution, the algorithm undoes its most recent decision and tries a different one. This pruning is what makes backtracking far faster than blindly listing every possibility, because whole branches of the search are discarded as soon as they are seen to be hopeless.
The technique is naturally recursive and is essentially a depth-first exploration of a tree of partial solutions: descend by making a choice, and on reaching a dead end, return to the previous level and choose again. Classic uses include placing N queens on a chessboard so none attack each other, filling in a Sudoku grid, solving constraint satisfaction problems, and parsing.
Donald Knuth’s paper “Dancing Links” examines exactly this style of computation. Its abstract describes “tricks to accelerate depth-first search algorithms” for combinatorial problems, and the paper uses examples such as the N-queens problem and tiling puzzles to show how a backtracking search can be made efficient by representing each tentative choice as a reversible operation on doubly linked lists.
The key idea Knuth highlights is that backtracking requires the program to undo its choices cleanly when it retreats. Dancing Links is a data-structure technique for removing and then restoring elements from a set during the search, so the cost of backing out of a decision is small and the algorithm can explore the next branch quickly.