Backtracking searches by following one sequence of decisions until it reaches a solution or dead end, then returning to the latest decision point and trying another alternative. It forms the core intuition of depth-first search and classical Sudoku solving. section 3.3.2 section 5.4
A backtracking search proceeds through a branching problem in a focused sequence:
- Select and expand a candidate decision or successor. section 3.3.2
- Continue down the current branch, often using a last-in, first-out stack or recursive calls. section 3.3.2
- When the branch reaches a dead end or violates a rule, return to the previous decision point. section 3.3.2 section 5.4
- Try the next available alternative and stop when a solution is found or alternatives are exhausted. section 3.3.2 section 5.4
Backtracking can use less space than breadth-first search because it concentrates on one deep branch, but it may spend more time exploring unproductive branches. A depth bound can restrict expansion, while rule checks can prune invalid branches earlier. section 3.3.2 section 5.4
Solving Sudoku
For a 9 × 9 Sudoku puzzle, assign a candidate number, test the row, column, and block constraints, and backtrack when the assignment makes the branch invalid. Backtracking is compared with simulated annealing and PuLP; dancing links applies the same recursive search idea through Algorithm X and exact cover. section 5.4
Algorithm 3.2 Depth-first search (DFS)
Inputs: Source node, Destination node Output: Route from source to destination Initialize Stack ← a LIFO initialized with sourcenode Initialize Explored ← empty Initialize Found ← False While stack is not empty and found is False do Set node ← stack.pop() Add node to explored For child in node.expand() do If child is not in explored and child is not in stack then If child is destination then Update route ← child.route() Update found ← True Add child to stack Return route
Follow the DFS pseudocode to see stack initialization, explored-node tracking, successor checks, route detection, and termination. section 3.3.2
