# Depth-First Search with Backtracking

Exploring choices recursively and undoing them when a branch fails, the standard pattern for constraint problems and puzzles.

**Rests on:** Base Cases and Recurrence, Recursive Thinking, Stack Memory Behaviour

*Mathematical Foundations · Recursion*


## Why learn this

This technique lets you solve problems where you must make a sequence of choices, each narrowing the possibilities for the next. It is how you find a valid Sudoku solution by filling one cell at a time, or how a program finds a route through a network. You try one possibility, see if it leads to a result, and if it hits a dead end, you step back and try another. This matters because many real-world tasks — from scheduling meetings to planning travel — involve navigating a huge number of possibilities. Without this method, you would either have to check every single combination (which takes too long) or guess randomly. With it, you can systematically explore the 'tree' of options, ignoring branches that clearly won't work, and reliably find a valid path.


## The intuition

Imagine you are trying to solve a puzzle where you place items one by one into slots. For example, placing chess queens on an 8x8 board so that no two attack each other.

1. **Try**: You pick the first empty spot and place a queen there.
2. **Check**: You look at the current board. Is it still possible to solve the puzzle from here? Or have you already made two queens attack each other? If you haven't hit a contradiction, you move to the next slot and repeat. This is the 'deep' part of depth-first search: you commit to a choice and follow it as far as you can.
3. **Backtrack**: Suppose you place a queen in slot 5, and later you realize that no matter where you put the remaining queens, this board configuration is impossible. You have hit a dead end. The key step is to 'undo' your decision at slot 5. You remove the queen from slot 5. Now you are back at slot 4, where you originally chose where to put that queen. You move that queen to a different spot and try again.

You do not need to remember every dead end you ever hit. You only need to keep track of the current path. When you 'return' from a deeper level of your process (because that path failed), the computer automatically wipes away the temporary notes you made for that specific step, restoring the previous notes as if that step never happened. This automatic cleanup is why backtracking is easy: you don't have to manually delete old data; just returning from the current function call does it for you.

You also 'prune' (cut off) branches early. If placing a queen in slot 2 creates a conflict with slot 1, you don't need to even look at slots 3 through 8 for that specific branch. You stop exploring that path immediately because you know it will fail. This saves enormous amounts of work.


## An analogy

Think of finding your way through a vast underground cave system with no map. You have a backpack that holds a list of the tunnels you have currently entered.

You start at the entrance tunnel (Level 1). You enter Tunnel A (Level 2). Inside, you find two more tunnels: A1 and A2. You pick A1. Inside A1, there is only one dead end. You realize you are stuck. Instead of forgetting where you came from, you simply walk back out of A1 into Tunnel A. Your backpack now lists only 'Entrance -> A'. The fact that you were in A1 is gone from your memory because you left that level.

Now you are still in Tunnel A. You try the other option: A2. Inside A2, you find it leads to a large chamber (a solution). Success!

But suppose A2 also led to a dead end. You walk back out of A2. Your backpack again just says 'Entrance -> A'. Now all exits from A are tried. You walk back out of A to the Entrance. Your backpack is empty except for 'Entrance'. You now try Tunnel B.

This is depth-first search: you go as deep as possible down one branch, and when you hit a wall, you pop back up one level (forgetting the details of the lower level) to try the next option at that higher level. The 'stack' of tunnels you are currently in is managed by your physical position: you can only be in one tunnel at a time, and leaving it erases its presence from your immediate context.


## Definition

Depth-first search with backtracking is a problem-solving method that explores possible choices by going as deep as possible down one path, and if that path fails, stepping back to the previous choice point and trying the next available option, using the natural undoing of function returns to manage the state of progress.


## How it connects

This concept relies heavily on **recursion**, which is a technique where a function calls itself to solve smaller versions of the same problem; each call remembers where it left off when it returns. It also connects to **state management** in programming, which is how code tracks variables that change over time, ensuring that when you 'step back' in your logic, the variables revert to their earlier values automatically.


## The mathematics

This concept belongs to the branch of mathematics called discrete mathematics — the study of things that can be counted and combined in distinct steps, rather than continuous quantities like lengths or speeds. Discrete mathematics deals with sets, arrangements, and graphs — collections of points connected by lines. Depth-first search is a way of systematically walking through such a graph or a tree of possibilities.

Imagine you are exploring a maze. You always choose one path and go as far as you can before turning back. This is what "depth-first" means: you go deep into one branch of choices before looking at any other branches. The "backtracking" part is the act of returning to a previous point when you hit a dead end.

Let us look at how this works step by step using a simple rule-based example. Suppose we want to find all pairs of numbers (a, b) where both a and b are integers from 0 to 2, and they must satisfy the condition that a is less than b.

We build our answer one number at a time. We call the first number 'a' and the second number 'b'.

Step 1: Start with no numbers chosen. We call this state "empty".

Step 2: Choose a value for 'a'. We try the smallest available number, which is 0.
   - Current partial solution: [0]
   - Is this valid so far? Yes, because we have only one number, so no rules are broken yet.

Step 3: Now we need to choose 'b'. We must pick a number from the remaining options (1 and 2) that is larger than 'a' (which is 0).
   - Try b = 1. Is 1 > 0? Yes.
   - Current partial solution: [0, 1].
   - Have we chosen all numbers? Yes. We have a complete pair (0, 1). This is one valid solution. We record it.

Step 4: Can we find another 'b' for the same 'a'? The next available number is 2.
   - Try b = 2. Is 2 > 0? Yes.
   - Current partial solution: [0, 2].
   - Have we chosen all numbers? Yes. We have a complete pair (0, 2). This is another valid solution. We record it.

Step 5: Are there more 'b' values for a = 0? No, we have tried 1 and 2. We are done with a = 0.

Step 6: Backtrack. We go back to the choice of 'a'. We try the next available number for 'a', which is 1.
   - Current partial solution: [1]
   - Is this valid so far? Yes.

Step 7: Now choose 'b' again, looking for numbers larger than 1.
   - Try b = 2. Is 2 > 1? Yes.
   - Current partial solution: [1, 2].
   - Have we chosen all numbers? Yes. We have a complete pair (1, 2). This is another valid solution. We record it.

Step 8: Are there more 'b' values for a = 1? No, we have tried 2. We are done with a = 1.

Step 9: Backtrack. We go back to the choice of 'a'. We try the next available number for 'a', which is 2.
   - Current partial solution: [2]
   - Is this valid so far? Yes.

Step 10: Now choose 'b' again, looking for numbers larger than 2.
   - The only remaining number is... none. There are no integers greater than 2 in our set {0, 1, 2} that we haven't used or that satisfy the condition.
   - We cannot place a 'b'. This path leads to a dead end.

Step 11: Backtrack again. Go back to the start. There are no more choices for 'a'. The search is complete.

The valid solutions found were (0, 1), (0, 2), and (1, 2).

This process illustrates the core logic:
1. Extend the current partial solution by adding one new element.
2. Check if the new element breaks any rules immediately. If it does, stop this branch (prune) and do not go deeper.
3. If it is valid, check if the solution is complete. If yes, record it. If no, repeat step 1 with the next possible element.
4. If all possibilities for the current position have been tried without success, remove the last element added (backtrack) and try a different option at the previous level.

In computer science terms, this is often written as a recursive function. A function takes the current partial list of choices. It loops through every possible next choice. For each choice, it checks if the choice is allowed. If allowed, it calls itself with the new, longer list. If the recursive call finds a solution, it returns that success. If the loop finishes without finding any valid path, the function returns failure, which triggers the backtracking in the previous level.


## A worked example

Consider a simple puzzle: place two queens on a 2-by-2 chessboard so that no two queens attack each other (in chess, a queen attacks any piece in the same row, column, or diagonal). We will search depth-first, trying to place a queen in column 1, then column 2. We represent a partial solution as a list of column positions for each row, e.g., [] for empty, [0] for a queen in row 0, column 0, and so on.

Step 1: Start at root: partial = []   # No queens placed yet.

Step 2: Try placing the first queen. We iterate through possible rows for the first queen (row 0).
   - Place queen at row 0, column 0.
   - Current partial solution: [0]   # This means Queen 1 is at (row 0, col 0).
   - Check conflicts: None yet, as there is only one queen.

Step 3: Now place the second queen. We iterate through possible rows for the second queen (row 1).
   - Try placing Queen 2 at row 1, column 0.
   - Current partial solution: [0, 0]   # Queen 1 at (0,0), Queen 2 at (1,0).
   - Check conflicts:
     - Same column? Yes. Both are in column 0.
     - Result: Conflict detected. This placement is invalid.

Step 4: Backtrack. We remove the last placement (Queen 2). The partial solution returns to [0].

Step 5: Try the next option for Queen 2. But wait, on a 2x2 board, if Queen 1 is at column 0, Queen 2 must be in column 1? No, we are iterating through *rows* for a fixed column structure in this specific example description, but typically N-Queens iterates rows and picks columns. Let us stick to the provided example's logic: "place a queen in column 1, then column 2". This implies we fix the column index and vary the row.

   - Let's restart the example with clearer variable names to match the standard N-Queens problem where we place one queen per column.
   - We have 2 columns: Column 0 and Column 1.
   - We need to choose a row for each column.

   **Attempt 1:**
   Step 1: Start with empty list [].
   
   Step 2: Choose a row for Column 0. Try row 0.
   - Partial solution: [0] (Queen at row 0, col 0).
   - Valid so far? Yes.
   
   Step 3: Choose a row for Column 1. Try row 0.
   - Partial solution: [0, 0].
   - Check conflicts with previous queens:
     - Compare Queen at (row 0, col 1) with Queen at (row 0, col 0).
     - Same column? No (col 1 vs col 0).
     - Same row? Yes (both row 0). Queens attack horizontally.
     - Result: Invalid.
   
   Step 4: Backtrack. Remove the choice for Column 1. Partial solution is [0].
   
   Step 5: Try next row for Column 1. Try row 1.
   - Partial solution: [0, 1].
   - Check conflicts with previous queens:
     - Compare Queen at (row 1, col 1) with Queen at (row 0, col 0).
     - Same column? No.
     - Same row? No.
     - Same diagonal? Calculate the difference in rows and columns.
       - Row difference: |1 - 0| = 1.
       - Column difference: |1 - 0| = 1.
       - Since the differences are equal, they are on the same diagonal. Queens attack diagonally.
     - Result: Invalid.
   
   Step 6: Backtrack. Remove the choice for Column 1. Partial solution is [0].
   
   Step 7: Are there more rows for Column 1? No, we tried 0 and 1. We are done with Column 1 for this branch.
   
   Step 8: Backtrack to Column 0. Remove the choice for Column 0. Partial solution is [].
   
   **Attempt 2:**
   Step 9: Try next row for Column 0. Try row 1.
   - Partial solution: [1] (Queen at row 1, col 0).
   - Valid so far? Yes.
   
   Step 10: Choose a row for Column 1. Try row 0.
   - Partial solution: [1, 0].
   - Check conflicts:
     - Compare Queen at (row 0, col 1) with Queen at (row 1, col 0).
     - Same column? No.
     - Same row? No.
     - Same diagonal?
       - Row difference: |0 - 1| = 1.
       - Column difference: |1 - 0| = 1.
       - Equal differences mean they are on the same diagonal.
     - Result: Invalid.
   
   Step 11: Backtrack. Remove choice for Column 1. Partial solution is [1].
   
   Step 12: Try next row for Column 1. Try row 1.
   - Partial solution: [1, 1].
   - Check conflicts:
     - Compare Queen at (row 1, col 1) with Queen at (row 1, col 0).
     - Same row? Yes (both row 1).
     - Result: Invalid.
   
   Step 13: Backtrack. Remove choice for Column 1. Partial solution is [1].
   
   Step 14: Are there more rows for Column 1? No.
   
   Step 15: Backtrack to Column 0. Remove choice for Column 0. Partial solution is [].
   
   Step 16: Are there more rows for Column 0? No, we tried 0 and 1.

Result: No solution exists for 2 queens on a 2x2 board. The search visited all possibilities and backtracked wherever a conflict was detected. This demonstrates the systematic exploration and undoing.


## From scratch, in Python

```python
def is_safe(board, row, col, n):
    # Check the same column in previous rows
    for r in range(row):
        if board[r] == col:
            return False
    # Check upper-left diagonal
    r, c = row - 1, col - 1
    while r >= 0 and c >= 0:
        if board[r] == c:
            return False
        r -= 1
        c -= 1
    # Check upper-right diagonal
    r, c = row - 1, col + 1
    while r >= 0 and c < n:
        if board[r] == c:
            return False
        r -= 1
        c += 1
    return True

def solve_n_queens(n):
    board = [-1] * n  # board[r] = column of queen in row r, -1 means not placed
    solutions = []
    
    def backtrack(row):
        if row == n:
            # All rows filled: a solution
            solutions.append(board[:])  # copy the board
            return
        for col in range(n):
            if is_safe(board, row, col, n):
                board[row] = col
                backtrack(row + 1)
                board[row] = -1  # undo: this is the backtracking step
    
    backtrack(0)
    return solutions

# Example: solve 4-queens
sol = solve_n_queens(4)
for s in sol:
    print(s)
```


## What the code does

First, define is_safe: it checks whether placing a queen in (row, col) conflicts with any previously placed queen (which are all in rows 0 to row-1). It checks: same column? Then any previous queen in that column would attack. Upper-left diagonal: a previous queen at (r, c) attacks if the row difference equals the column difference. Upper-right diagonal: same but with increasing column. The function returns True if no conflicts.

Next, solve_n_queens sets up a board: a list of length n, where board[r] holds the column index of the queen in row r, or -1 if not yet placed. solutions is an empty list to collect all valid placements.

Then define an inner function backtrack(row). Parameter row tells us which row we are trying to fill next. If row == n, we have placed queens in all rows — that is a valid solution, so we append a copy of the board (board[:] makes a copy, so later changes do not modify the saved solution). Otherwise, for each column from 0 to n-1: if is_safe allows the placement, we set board[row] = col, then call backtrack(row + 1) to recursively fill the next row. After that recursive call returns (whether it found solutions or not), we set board[row] = -1 — this undoes the placement, which is the backtracking step. This ensures that when the for loop tries the next column, the board is exactly as it was before we tried the current column. The recursion naturally implements depth-first exploration: it goes as deep as possible (row by row) before trying alternative columns.

The call backtrack(0) starts the search. When it finishes, solutions contains all valid boards. In the example for n=4, it prints the two classical solutions: [1, 3, 0, 2] and [2, 0, 3, 1], where each list gives the column of the queen in each row.


## Common misconceptions

**Backtracking means trying all possibilities blindly** — Backtracking is just brute force, so it is always exponential and useless.

Backtracking is systematic but prunes branches as soon as a partial solution is invalid. In the n-queens problem, for example, you do not explore all n^n placements; you stop as soon as a conflict is found. This pruning is what makes it efficient for many real puzzles. In fact: Backtracking is a depth-first search with early pruning: it abandons a branch the moment it cannot lead to a solution, which is why it is far faster than brute force in practice.

**Undoing state is optional** — If I just try a choice and then move on, it will work.

If you do not undo the change (like setting board[row] = -1), the next attempt will see the stale state and produce incorrect results. The recursion depends on each branch starting from the state as it was before the last choice. In fact: Every failed attempt must be undone — you must restore the state to what it was before you made that choice, so the next option sees a clean slate.

**Depth-first means solving one path to completion** — You only go down one path and if it fails you give up.

Depth-first does go down one path, but if it fails, you do not give up — you backtrack to the last branch and try the next alternative. You continue until you find a solution or exhaust all possibilities. In fact: Depth-first search goes deep first, but backtracks to try other branches whenever the current one fails. It explores the entire search space unless pruning avoids it.

**Backtracking only works for puzzles** — This is only for Sudoku and chess puzzles; it has no use in real software.

Backtracking is used in compiler parsers (recursive descent), regex matching (backtracking engines), and in planning algorithms for robots and agents. It is a general search strategy for any tree of choices. In fact: Backtracking is a general technique for searching a space of possibilities, just with pruning. It underlies many algorithms that need to try alternative paths, from parsing to tool selection in agentic AI.


## In short

Depth-first search with backtracking is the systematic exploration of a tree of choices: commit to one branch, go as deep as possible, and when a branch fails, undo the last choice and try the next. The key to making it work is to undo state properly and to prune branches as early as possible. This pattern is fundamental to recursion and appears across AI — from solving puzzles to planning in agentic systems.


## Where this is used

Depth-first search with backtracking is used explicitly in constraint solving (Sudoku solvers, n-queens, cryptography puzzles) and implicitly in many AI systems. In large language models (LLMs), beam search — a variant of depth-first search — is used during text generation, where the model explores multiple possible next tokens and selects the one with highest probability. More directly, the back-and-forth of trying a sequence of tokens and evaluating the resulting likelihood is a form of tree search, though breadth-first. In agentic systems that plan and call tools, backtracking is the core of a planning loop: an agent tries a tool call, checks if the result satisfies its goal, and if not, it 'undoes' that step (mentally or by reverting the state) and tries another tool. This is what OpenAI's function calling does when it searches for a sequence of API calls to achieve a user request. In retrieval-augmented generation (RAG), the retrieval step often uses approximate nearest neighbour search, which is based on navigating a tree of vectors (like HNSW), and the search algorithm there is depth-first with backtracking when it explores branches and backtracks when it finds a better candidate. In small models running on devices, backjumping is used in on-device grammar-based decoding, where the model tries to generate text that conforms to a grammar and backtracks if the output violates the rules. In everyday applied machine learning, backtracking appears in hyperparameter tuning with tree-structured search (like TPE), where the algorithm explores a tree of hyperparameter combinations and backtracks when a branch performs poorly. For a developer, implementing a Sudoku solver with backtracking is a classic exercise, but in production you would use a library like python-constraint or OR-Tools, which internally use depth-first search with pruning. What breaks when done badly: if you do not undo state correctly, you get incorrect solutions or an explosion of states; if you do not prune, the search space may be exponentially too large. The exact reason n-queens is tractable is that the backtracking prunes many branches early, reducing the search from n^n to far fewer states.


---

Read this on the web: https://basavapurushottam.com/learn-ai/depth-first-search-with-backtracking
