Dead Ends and Backtracking
Picture navigating a corn maze. You choose the left fork, walk confidently for two minutes, and hit a wall. The path simply ends. You have two options: stand there hoping the wall disappears, or turn around and go back to the place where you made the choice — and this time, take the right fork. That second option is backtracking. It is not defeat. It is intelligent problem-solving.
What Is a Dead End?
In planning, a dead end is a state where continuing along the current path cannot possibly reach the goal. The path is blocked — not temporarily delayed, but genuinely impassable from this point. A dead end can appear for many reasons: a required resource does not exist, a logical constraint makes a step impossible, every available action leads to states that make the goal unreachable. Dead ends are different from obstacles. An obstacle is a difficulty that can be overcome with more effort or a workaround. A dead end is a fundamental impasse: no amount of pushing harder will get through it. Recognizing this distinction is critical, because the right response to each is opposite — push through an obstacle, backtrack from a dead end.
A dead end is a point in a plan where no available action can lead to the goal. Unlike an obstacle (which can be overcome), a dead end requires returning to an earlier decision point and choosing differently.
Backtracking is the strategy of returning to a previous decision point — called a choice point — and selecting a different option than the one that led to the dead end. The key insight is that backtracking is not undoing all progress; it is undoing only the progress made after the last choice point. In a maze, if you chose left at the third junction and hit a dead end two turns later, you backtrack to the third junction — not to the entrance. You preserve all the progress you made reaching that junction and only reconsider the single decision that led you wrong. This same logic applies to AI planning. When a planning agent reaches a dead end, it rolls back its state to the most recent point where it made a choice, and explores the alternatives it had not yet tried from that point.
Backtracking is returning to the most recent choice point where an alternative option exists, and trying that alternative instead. It preserves progress up to the choice point while abandoning only the failed path beyond it.
Match each backtracking concept to its correct description.
Terms
Definitions
Drag terms onto their definitions, or click a term then click a definition to match.
Backtracking in AI Search and Planning
Backtracking is one of the oldest ideas in computer science. It underlies a class of algorithms called constraint satisfaction solvers, which are used to solve puzzles like Sudoku, schedule classes without room conflicts, and assign tasks to workers without overlaps. Here is how a Sudoku solver uses backtracking. It picks an empty cell, tries placing the digit 1. It checks all constraints — no 1 in this row, column, or box. If valid, it moves to the next empty cell. Eventually it might fill twenty cells and then find a cell where no digit from 1 to 9 is valid. That is a dead end. It backtracks to the most recent cell where it tried a digit and had alternatives, removes that digit, tries the next one, and continues. This systematic explore-and-backtrack process, called depth-first search with backtracking, can solve a 9x9 Sudoku in milliseconds — not by being clever, but by being systematic and willing to undo.
Students often feel that backtracking means they got something wrong. In planning and problem-solving, backtracking is a normal and expected part of finding the right path. Every dead end you find is information about the problem's structure. Good planners — and good agents — treat dead ends as data.
Modern AI planning agents extend this classical idea. When an agent trying to complete a multi-step task finds that a subgoal is now unreachable — perhaps an API it needed has become unavailable, or a piece of information it assumed existed does not — it does not simply halt. It identifies the most recent decision point where it could have chosen differently: perhaps it chose to use that particular API rather than another. It rolls back to that choice, selects the alternative, and continues the plan from there. This requires the agent to keep a record of its decision points and the choices it made at each one. Agents that cannot backtrack — that can only move forward — are fundamentally fragile: any dead end stops them permanently.
An AI agent is solving a scheduling problem and tries assigning Task A to Monday. After many more assignments, it finds that no valid schedule exists with Task A on Monday. What should it do?
What makes a dead end different from an obstacle in planning?
The Backtracking Maze
- Step 1: Draw a simple branching maze on paper — not a grid maze, but a decision tree. Start with one entry point. Branch into two paths. Each path branches again into two. Some paths end in a star (success) and some end in an X (dead end). Make sure there is at least one path to a star.
- Step 2: Starting from the entry, pick a path. Every time you choose a direction, write down the choice point and which option you picked.
- Step 3: If you hit an X, write: dead end at step [N]. Then backtrack to the most recent choice point and record: backtracking to step [N-1], trying alternative.
- Step 4: Continue until you find a star.
- Step 5: Count how many dead ends you hit. Write a paragraph describing what an AI agent would need to store (what information, in what format) to do exactly what you just did automatically.