Iterative Deepening DFS, in depth: depth-limited search with a cutoff signal, the b/(b-1) overhead measured, an 8-puzzle, and the transposition blow-up on graphs

Depth-limited search and the three outcomes

The building block is depth-limited search, DLS: a DFS that refuses to go deeper than a limit L. IDDFS calls DLS with L = 0, 1, 2 and so on. Because DLS with limit L explores every path of length at most L, the first limit at which it finds the goal is the depth of the shallowest goal, so the path returned has the fewest possible edges.

The one detail that implementations get wrong is the return value. DLS can end in three ways, and IDDFS must handle each differently. It finds a path. It finds nothing, but some branch was cut by the limit, so a deeper search might succeed: that is CUTOFF. Or it finds nothing and no branch was cut: the whole reachable space has been exhausted, the goal is unreachable, and deepening again would repeat the same search forever. An implementation that returns only a path or None cannot tell the last two apart, so on a finite graph with no goal it either loops until the limit counter overflows or stops at an arbitrary maximum depth and reports a wrong "not found".

A tested implementation

The implementation keeps the current path as a list for the answer and as a set for O(1) cycle checks. The on_path check is what lets DLS return None on a finite graph: without it, a walk around any cycle always reaches the limit, every iteration reports CUTOFF, and an unreachable goal is never declared unreachable.

CUTOFF = "cutoff"

def depth_limited(state, is_goal, neighbors, limit, path, on_path, stats):
    stats["expanded"] += 1
    if is_goal(state):
        return list(path)
    if limit == 0:
        return CUTOFF                       # there may be more below this node
    cut = False
    for nxt in neighbors(state):
        if nxt in on_path:                  # never walk around a cycle on this path
            continue
        path.append(nxt); on_path.add(nxt)
        r = depth_limited(nxt, is_goal, neighbors, limit - 1, path, on_path, stats)
        path.pop(); on_path.remove(nxt)
        if r == CUTOFF:
            cut = True
        elif r is not None:
            return r
    return CUTOFF if cut else None          # None: nothing below, at any depth

def iddfs(start, is_goal, neighbors, max_depth=10**6):
    stats = {"expanded": 0}
    for limit in range(max_depth + 1):
        r = depth_limited(start, is_goal, neighbors, limit, [start], {start}, stats)
        if r != CUTOFF:
            return r, limit, stats["expanded"]     # a path, or None = unreachable
    return CUTOFF, max_depth, stats["expanded"]    # gave up: answer unknown

Tested on 500 random directed graphs with 2 to 12 vertices against BFS: every depth matched, every unreachable goal returned None, and every returned path used real edges. On a four-vertex graph with a cycle and a separate, unreachable vertex, iddfs returned None at limit 4 after 23 expansions, instead of looping.

Why repeating the shallow levels is cheap

In a uniform tree with branching factor b and goal depth d, DLS with limit L visits 1 + b + ... + b^L nodes. Summed over L = 0 to d, a node at depth i is visited d + 1 - i times, so the total is the sum over i of (d + 1 - i) bⁱ. The deepest level dominates both BFS and IDDFS, and as d grows the ratio of IDDFS work to BFS work approaches b/(b - 1).

So IDDFS costs at most twice BFS on a binary tree, and about 11 percent more at branching factor 10, while memory drops from O(b^d) to O(d) for the path, or O(bd) if each frame keeps its list of remaining children. Time is O(b^d), the same order as BFS. The bigger the branching factor, the cheaper the repetition, which is why IDDFS suits puzzles and game trees.

Worked example: the 8-puzzle

The 8-puzzle has 181,440 reachable states, a branching factor between 2 and 4, and unit move costs. Scrambling the solved board with 40 random moves gave a start state whose shortest solution is 14 moves. BFS found the 14-move solution after discovering 4,873 states, all of which it holds in memory. IDDFS found a 14-move solution at limit 14 after 10,734 node expansions across 15 iterations, while holding one path of at most 15 states.

The ratio of about 2.2 is higher than the tree formula predicts because the 8-puzzle is a graph, not a tree: the path check stops a path from revisiting a state, but two different paths can still reach the same board. Here that overhead is modest; on grids it explodes.

Graphs and the transposition blow-up

On a k by k grid, searching from one corner to the opposite one, the number of simple paths of length at most 2(k - 1) grows exponentially in k while the number of cells grows only as k². Checking only the current path does not stop IDDFS from re-exploring a cell reached by a different route, which is called a transposition in game search.

The fix is a per-iteration table recording the largest remaining depth with which each state has been searched. If a state is reached again with no more remaining depth than before, nothing new can be found below it, so the search skips it. The table also stores whether that earlier search was cut, so the CUTOFF signal is not lost.

def depth_limited_memo(state, is_goal, neighbors, limit, budget, stats):
    """budget maps state -> (largest remaining depth seen this iteration, was it cut)."""
    stats["expanded"] += 1
    if is_goal(state):
        return [state]
    if limit == 0:
        budget[state] = (0, True)
        return CUTOFF
    budget[state] = (limit, False)          # in progress: a cycle back here is skipped
    cut = False
    for nxt in neighbors(state):
        seen = budget.get(nxt)
        if seen is not None and seen[0] >= limit - 1:
            cut = cut or seen[1]            # already searched at least this deep
            continue
        r = depth_limited_memo(nxt, is_goal, neighbors, limit - 1, budget, stats)
        if r == CUTOFF:
            cut = True
        elif r is not None:
            return [state] + r
    budget[state] = (limit, cut)
    return CUTOFF if cut else None

def iddfs_memo(start, is_goal, neighbors, max_depth=10**6):
    stats = {"expanded": 0}
    for limit in range(max_depth + 1):
        r = depth_limited_memo(start, is_goal, neighbors, limit, {}, stats)
        if r != CUTOFF:
            return r, limit, stats["expanded"]
    return CUTOFF, max_depth, stats["expanded"]

The memo version gave the same depths on the same 500 random graphs and cut the 8-puzzle to 8,650 expansions. The cost is memory: the table can hold every reachable state, which is what IDDFS was meant to avoid. Use it when transpositions dominate and the state count fits in memory; when it does not, plain BFS on the implicit graph with a compact visited set is often the better tool.

Descendants: IDA*, game engines and lengthening

IDDFS was analysed by Korf in 1985, who showed it is asymptotically optimal in time, space and solution length among brute-force tree searches. Three descendants matter in practice.

• IDA* deepens on f = g + h, the cost so far plus an admissible heuristic, instead of on depth. Each iteration raises the threshold to the smallest f that exceeded the last one. It solves 15-puzzle instances in memory proportional to the solution length; see A* variants.
• Game engines run alpha-beta to depth 1, 2, 3 and so on. They do it less for memory than for time control, since a result is always available when the clock runs out, and for move ordering, since the best move from depth L is searched first at depth L + 1. Game tree search measures the effect.
• Iterative lengthening extends the idea to weighted edges by deepening on path cost. With many distinct costs it can need one iteration per distinct value, so prefer Dijkstra or IDA* there.

Engineering a production search

Engineering notes for a production search, such as a configuration planner, a puzzle solver or an agent that explores tool-call sequences up to some depth:

• Recursion depth. Python's default recursion limit is 1,000 frames. For deep searches convert DLS to an explicit stack, as in iterative DFS, and keep a CUTOFF flag per frame.
• Anytime behaviour. Check a deadline between iterations and inside DLS. When time runs out, report the deepest completed limit, because that is a proof that no solution exists up to that depth.
• Neighbour order. Order changes which shortest path is returned, never its length. Put likely moves first and pass the previous iteration's path in to try first.
• Logging. Record expansions per iteration. The ratio between consecutive iterations estimates the effective branching factor, and a ratio that keeps growing means transpositions, so switch to the memo version.
• Goal test placement. Test the goal when a node is visited, as the code does, not when it is generated at the limit, or the depth reported is off by one.

Trade-offs

Bidirectional search, covered in meet in the middle, attacks the same exponential from the other side: two searches to depth d/2 instead of one to depth d.

Failure modes

• Two-valued DLS. Treating "cut off" and "exhausted" as the same None makes unreachable goals loop forever or stop with a wrong answer.
• No path check on graphs. Every cycle keeps CUTOFF alive and the search never terminates on an unreachable goal.
• Transposition blow-up. Grids, sliding puzzles and planners with commuting actions reach the same state by many routes; expansions grow exponentially while the state count stays small, as the table above shows.
• Assuming optimal costs. IDDFS minimises the number of edges. With weighted edges the path it returns can be far from cheapest.
• Global visited set. A single visited set shared across one iteration, without depths, can block the only shallow route to a state that was first reached by a deeper route, so the search misses the goal at the right limit or returns a longer path.
• Mutable state shared between frames. If neighbour generation mutates a shared board without undoing it, later siblings see corrupted state. Use immutable states or strict apply and undo pairs.

What to do next

1. Copy iddfs and test it against BFS on random graphs, including unreachable goals and directed edges.
2. Solve the 8-puzzle with it and log expansions per iteration to estimate the effective branching factor.
3. Run it on a 9 by 9 grid with and without the memo and confirm the blow-up.
4. Rewrite DLS with an explicit stack and a deadline, and return the deepest completed limit.
5. Move to IDA* with the Manhattan-distance heuristic and compare expansions on the same puzzles.