Generic Iterative Deepening on Search Trees

Why Generic Iterative Deepening on Search Trees Matters

Suppose a puzzle solver can generate legal moves cheaply, but you do not know whether the nearest solution takes three moves or thirty. Breadth-first search stores a growing frontier; ordinary depth-first search may follow a long branch before trying a one-move answer. Iterative deepening depth-first search (IDDFS) runs depth-limited DFS repeatedly with limits $0,1,2,\ldots$, trading repeated work near the root for a small active search path.

The result is a path to a goal with the fewest edges, provided the state model is complete, branching is finite, and the search reaches the necessary limit without exhausting its resources. For equal-cost moves this also minimizes cost. With unequal move costs, the shallowest path can be expensive; depth alone does not optimize weight.

The recursion and choose/recurse/undo pattern from the prerequisites stays intact. The new ideas are a remaining-depth argument, a distinction between an exhausted branch and a cutoff branch, and an outer loop that starts each pass from a clean root. This lesson makes those decisions observable through paths, return states, and counters. The main benefit arises in large implicit search trees, where successors are generated on demand; a small explicit graph is used here so every step is reproducible.

Core Concepts and Terminology

A state describes everything that determines legal successors and whether the goal holds. A search-tree node is a particular path to a state: different paths may end at the same state. IDDFS revisits those occurrences intentionally. The root has depth $0$; a path containing $k+1$ states has depth $k$.

For a pass with limit $L$, a call at depth $k$ receives remaining depth $r=L-k$. A child is admitted only if $r\gt0$ and it is not already on the current path. In an actual tree, cycle checks are unnecessary. Our graph adapter adds current-path cycle pruning so finite cyclic graphs also terminate once all useful simple paths are exhausted. This is a legality prune; the depth boundary is a temporary resource prune.

The inputs are a start state, a deterministic ordered successor function, a goal predicate, a maximum depth, and a total node-admission budget. The output reports a found path, proven exhaustion, or an inconclusive resource limit. The diagram uses the worked tree with goal $7$ and limit $2$: a leaf at the boundary is different from a node whose child was excluded by the boundary.

How Generic Iterative Deepening on Search Trees Works, Step by Step

1. Validate the graph and search limits. Clear the previous answer, path, marks, counters, and pass history. The budget counts all passes together.
2. For $L=0,1,\ldots,D$, push and mark the root, then call the depth-limited search with $r=L$.
3. On entry, check the global node budget. If admission is refused, return ABORT without counting a node. Otherwise increment nodes, update peak, and test the goal before testing the depth boundary. This finds both a root goal and a goal exactly at the limit.
4. If the current non-goal has $r=0$, inspect successors only until finding one not already on the active path. Such a successor proves CUTOFF; do not enter it. If every successor is absent or cycle-blocked, return FAILURE. Each tested adjacency increases edges, and each blocked one increases cycles.
5. With $r\gt0$, inspect children in their stored order. For each allowed child, append and mark it, recurse with $r-1$, then unmark and pop it before handling the returned code. Copy the witness inside the goal call so undo cannot erase it.
6. Propagate FOUND or ABORT immediately after undo. Otherwise remember whether any child returned CUTOFF; return CUTOFF if so, or FAILURE when all children failed. A single exhausted child does not establish exhaustion of its siblings.
7. The driver removes the root, verifies complete restoration, and records this pass's counter deltas. FOUND becomes a successful result; root FAILURE becomes NO_SOLUTION; ABORT becomes NODE_LIMIT. Only root CUTOFF starts another pass, unless the depth cap has been reached, in which case report DEPTH_LIMIT.

This lesson uses an exact cutoff probe at the boundary. A simpler version may conservatively return cutoff for every non-goal boundary node and need an extra pass to establish exhaustion. Both conventions can find shallowest goals, but their cutoff counts and stopping passes differ. Use one convention consistently.

flowchart TD
    A["Driver: initialize limit to zero"] --> B["Push root and call DLS"]
    B --> C["Undo root and record pass"]
    C --> D{"Root outcome?"}
    D -->|FOUND| E["Return copied goal path"]
    D -->|FAILURE| F["Return NO_SOLUTION"]
    D -->|ABORT| G["Return NODE_LIMIT"]
    D -->|CUTOFF| H{"Depth cap reached?"}
    H -->|Yes| I["Return DEPTH_LIMIT"]
    H -->|No| J["Increase limit by one"]
    J --> B
    subgraph SEARCH["DLS: one recursive call"]
        K{"Node budget available?"} -->|No| Q["Return ABORT"]
        K -->|Yes| M["Count node and update peak"]
        M --> N{"Goal?"}
        N -->|Yes| O["Copy path; return FOUND"]
        N -->|No| P{"Remaining depth zero?"}
        P -->|Yes| R{"Any child outside active path?"}
        R -->|Yes| S["Return CUTOFF"]
        R -->|No| T["Return FAILURE"]
        P -->|No| U["Scan next child; skip cycle edges"]
        U --> V{"Allowed child left?"}
        V -->|Yes| W["Push and mark child; recurse"]
        W --> X["Unmark and pop child"]
        X --> Y{"Child outcome?"}
        Y -->|FOUND or ABORT| Z["Propagate outcome"]
        Y -->|CUTOFF| AA["Remember cutoff"]
        AA --> U
        Y -->|FAILURE| U
        V -->|No| AB{"Any child cutoff?"}
        AB -->|Yes| S
        AB -->|No| T
    end
    B -. "DLS entry" .-> K

Worked Example with a Full Trace

Use the ordered adjacency lists $0:[1,2]$, $1:[3,4]$, $2:[5]$, $3:[6]$, $4:[]$, $5:[7]$, $6:[]$, $7:[]$. Start at $0$, seek goal $7$, allow maximum depth $5$, and use a node budget of $1{,}000{,}000$. There are no cycle edges. Child order is significant: the left subtree is exhausted before the right subtree is tried.

The complete admission trace follows. Each row records the active path on entry, its remaining depth, and the code that this call eventually returns. A parent's result appears on its entry row even though it is determined after the listed descendants return; DFS returns in the corresponding reverse nesting order. Undo removes each child immediately after its return. The root is also removed between passes.

At a boundary cutoff only the first admissible edge is probed. Thus limit $0$ tests $0\to1$ but does not test $0\to2$. At limit $1$ the tested edges, in order, are $0\to1$, $1\to3$, $0\to2$, $2\to5$. At limit $2$ they are $0\to1$, $1\to3$, $3\to6$, $1\to4$, $0\to2$, $2\to5$, $5\to7$. At limit $3$ those same seven edges are tested, but their children are now admitted. This accounts for every edge-counter increment.

The saved witness is $[0,2,5,7]$ with $3$ edges. The active path is empty after return, every mark is false, and the total node counter is $18$, even though the graph has only $8$ distinct states. No goal exists at a smaller depth, as demonstrated by the three completed earlier passes.

Implementation in Python, C++, and Java

The three programs implement the same driver and DLS logic. is_goal and successors isolate the search from the problem representation; here their adapter is an ordered adjacency list with dense integer state IDs. To search an implicit puzzle tree, replace this adapter with a complete state representation and a lazy successor generator, and adapt the current-path membership structure. If legal moves or goals depend on history, that history must be part of the state.

Input contract. Supply a finite adjacency list with $1\le V\le128$ vertices and at most $4096$ total adjacency entries; every successor and start/goal ID must be an integer in $[0,V-1]$. Rows and the goal collection must be non-null collections of integer IDs. Self-loops, duplicate edges, and duplicate goal IDs are allowed; goal collections have at most $128$ entries. Adjacency order is preserved and copied, and callers' inputs are not modified. The maximum depth satisfies $0\le D\le64$; the global budget satisfies $1\le B\le10{,}000{,}000$. These are demonstration safeguards, not mathematical restrictions of IDDFS. Invalid numeric sizes, ranges, and IDs in this contract are rejected with an exception.

run returns status, last attempted depth limit, a copied answer, statistics in the order [nodes,edges,cutoffs,cycles,peak], and per-pass histories. A history entry contains the limit, the internal DLS code, and four counter deltas. cutoffs counts boundary calls that discover an admissible child, not each propagation of the code. peak is the greatest admitted edge-depth. edges also includes a tested edge whose child admission is refused. restored=YES is printed only after the driver's restoration assertion has passed.

NO_SOLUTION means root FAILURE, including an empty goal set once the reachable search is exhausted. DEPTH_LIMIT and NODE_LIMIT are inconclusive and have empty answers. A budget is checked on the next attempted admission: exactly consuming it does not erase a goal or failure already established. Each call to run resets its own search state, so the same solver can be reused.

Run with Python 3, compile C++14 or newer, and save Java as Main.java for Java 17 or newer. The complete programs include the worked tree, boundary and root goals, a dead leaf, a cycle, a transposition, and both resource limits.

class IterativeDeepening:
    def __init__(self, graph):
        if not 1 <= len(graph) <= 128 or sum(map(len, graph)) > 4096:
            raise ValueError("invalid graph size")
        n = len(graph)
        if any(type(v) is not int or not 0 <= v < n for row in graph for v in row):
            raise ValueError("invalid successor")
        self.graph = [list(row) for row in graph]

    def is_goal(self, state):
        return self.goals[state]

    def successors(self, state):
        return self.graph[state]

    def visit(self, state, remaining):
        if self.nodes >= self.budget:
            return "ABORT"
        self.nodes += 1
        self.peak = max(self.peak, len(self.path) - 1)
        if self.is_goal(state):
            self.answer = self.path.copy()
            return "FOUND"
        if remaining == 0:
            for child in self.successors(state):
                self.edges += 1
                if self.on_path[child]:
                    self.cycles += 1
                    continue
                self.cutoffs += 1
                return "CUTOFF"
            return "FAILURE"
        saw_cutoff = False
        for child in self.successors(state):
            self.edges += 1
            if self.on_path[child]:
                self.cycles += 1
                continue
            self.path.append(child)
            self.on_path[child] = True
            result = self.visit(child, remaining - 1)
            self.on_path[child] = False
            self.path.pop()
            if result in ("FOUND", "ABORT"):
                return result
            saw_cutoff |= result == "CUTOFF"
        return "CUTOFF" if saw_cutoff else "FAILURE"

    def run(self, start, goal_states, max_depth, node_budget=1_000_000):
        n = len(self.graph)
        if (type(start) is not int or not 0 <= start < n or len(goal_states) > 128 or
                any(type(g) is not int or not 0 <= g < n for g in goal_states) or
                type(max_depth) is not int or not 0 <= max_depth <= 64 or
                type(node_budget) is not int or not 1 <= node_budget <= 10_000_000):
            raise ValueError("invalid search parameters")
        self.goals, self.on_path = [False] * n, [False] * n
        for state in goal_states:
            self.goals[state] = True
        self.path, self.answer, self.passes = [], [], []
        self.nodes = self.edges = self.cutoffs = self.cycles = self.peak = 0
        self.budget = node_budget
        for limit in range(max_depth + 1):
            before = [self.nodes, self.edges, self.cutoffs, self.cycles]
            self.path.append(start)
            self.on_path[start] = True
            code = self.visit(start, limit)
            self.on_path[start] = False
            self.path.pop()
            if self.path or any(self.on_path):
                raise RuntimeError("path undo failed")
            now = [self.nodes, self.edges, self.cutoffs, self.cycles]
            self.passes.append((limit, code, [a - b for a, b in zip(now, before)]))
            if code != "CUTOFF" or limit == max_depth:
                status = {"FOUND": "FOUND", "FAILURE": "NO_SOLUTION",
                          "ABORT": "NODE_LIMIT", "CUTOFF": "DEPTH_LIMIT"}[code]
                history = [(d, s, counts.copy()) for d, s, counts in self.passes]
                return status, limit, self.answer.copy(), now + [self.peak], history
        raise RuntimeError("unreachable driver state")


def show(name, graph, goals, max_depth, budget=1_000_000):
    status, limit, path, stats, passes = IterativeDeepening(graph).run(0, goals, max_depth, budget)
    print(f"{name}: {status}, limit={limit}, path=[" + ",".join(map(str, path)) + "]")
    labels = ("nodes", "edges", "cutoffs", "cycles", "peak")
    print(", ".join(f"{k}={v}" for k, v in zip(labels, stats)) + ", restored=YES")
    print("passes=[" + ",".join(f"{d}:{s}:{c[0]}" for d, s, c in passes) + "]")


def main():
    tree = [[1, 2], [3, 4], [5], [6], [], [7], [], []]
    show("worked", tree, [7], 5)
    show("boundary goal", tree, [5], 2)
    show("root goal", tree, [0], 0, 1)
    show("dead leaf", [[]], [], 5)
    show("cycle", [[1], [0]], [], 5)
    show("transposition", [[1, 2], [2], [3], []], [3], 3)
    show("depth cap", tree, [7], 2)
    show("node cap", tree, [7], 5, 8)
    print("checks = PASS")


if __name__ == "__main__":
    main()

#include <algorithm>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
using namespace std;

struct Pass { int limit; string code; vector<long long> counts; };
struct Result { string status; int limit; vector<int> path; vector<long long> stats; vector<Pass> passes; };

class IterativeDeepening {
public:
    vector<vector<int>> graph;
    vector<bool> goals,on_path;
    vector<int> path,answer;
    vector<Pass> passes;
    long long nodes=0,edges=0,cutoffs=0,cycles=0,peak=0,budget=0;

    explicit IterativeDeepening(const vector<vector<int>>& input) : graph(input) {
        if (graph.empty() || graph.size()>128) throw invalid_argument("invalid graph size");
        size_t total=0;
        for (const auto& row:graph) {
            total+=row.size();
            for (int v:row) if (v<0 || v>=static_cast<int>(graph.size())) throw invalid_argument("invalid successor");
        }
        if (total>4096) throw invalid_argument("too many edges");
    }
    bool is_goal(int state) const { return goals[state]; }
    const vector<int>& successors(int state) const { return graph[state]; }

    string visit(int state,int remaining) {
        if (nodes>=budget) return "ABORT";
        ++nodes; peak=max(peak,static_cast<long long>(path.size())-1);
        if (is_goal(state)) { answer=path; return "FOUND"; }
        if (remaining==0) {
            for (int child:successors(state)) {
                ++edges;
                if (on_path[child]) { ++cycles; continue; }
                ++cutoffs; return "CUTOFF";
            }
            return "FAILURE";
        }
        bool saw_cutoff=false;
        for (int child:successors(state)) {
            ++edges;
            if (on_path[child]) { ++cycles; continue; }
            path.push_back(child); on_path[child]=true;
            string result=visit(child,remaining-1);
            on_path[child]=false; path.pop_back();
            if (result=="FOUND" || result=="ABORT") return result;
            saw_cutoff=saw_cutoff || result=="CUTOFF";
        }
        return saw_cutoff ? "CUTOFF" : "FAILURE";
    }

    Result run(int start,const vector<int>& goal_states,int max_depth,long long node_budget=1000000) {
        int n=static_cast<int>(graph.size());
        if (start<0 || start>=n || goal_states.size()>128 || max_depth<0 || max_depth>64 || node_budget<1 || node_budget>10000000)
            throw invalid_argument("invalid search parameters");
        for (int g:goal_states) if (g<0 || g>=n) throw invalid_argument("invalid goal");
        goals.assign(n,false); on_path.assign(n,false);
        for (int g:goal_states) goals[g]=true;
        path.clear(); answer.clear(); passes.clear();
        nodes=edges=cutoffs=cycles=peak=0; budget=node_budget;
        for (int limit=0;limit<=max_depth;++limit) {
            vector<long long> before={nodes,edges,cutoffs,cycles};
            path.push_back(start); on_path[start]=true;
            string code=visit(start,limit);
            on_path[start]=false; path.pop_back();
            if (!path.empty() || any_of(on_path.begin(),on_path.end(),[](bool b){return b;})) throw logic_error("undo failed");
            vector<long long> now={nodes,edges,cutoffs,cycles},delta(4);
            for (size_t i=0;i<4;++i) delta[i]=now[i]-before[i];
            passes.push_back({limit,code,delta});
            if (code!="CUTOFF" || limit==max_depth) {
                string status=code=="FOUND" ? "FOUND" : code=="FAILURE" ? "NO_SOLUTION" : code=="ABORT" ? "NODE_LIMIT" : "DEPTH_LIMIT";
                now.push_back(peak);
                return {status,limit,answer,now,passes};
            }
        }
        throw logic_error("unreachable driver state");
    }
};

void show(const string& name,const vector<vector<int>>& graph,const vector<int>& goals,int depth,long long budget=1000000) {
    Result r=IterativeDeepening(graph).run(0,goals,depth,budget);
    cout<<name<<": "<<r.status<<", limit="<<r.limit<<", path=[";
    for (size_t i=0;i<r.path.size();++i) { if(i) cout<<','; cout<<r.path[i]; }
    cout<<"]\n";
    vector<string> labels={"nodes","edges","cutoffs","cycles","peak"};
    for (size_t i=0;i<labels.size();++i) { if(i) cout<<", "; cout<<labels[i]<<'='<<r.stats[i]; }
    cout<<", restored=YES\npasses=[";
    for (size_t i=0;i<r.passes.size();++i) {
        if(i) cout<<',';
        const Pass& p=r.passes[i]; cout<<p.limit<<':'<<p.code<<':'<<p.counts[0];
    }
    cout<<"]\n";
}
int main() {
    vector<vector<int>> tree={ {1,2}, {3,4}, {5}, {6}, {}, {7}, {}, {} };
    show("worked",tree,{7},5);
    show("boundary goal",tree,{5},2);
    show("root goal",tree,{0},0,1);
    show("dead leaf",{ {} },{},5);
    show("cycle",{ {1}, {0} },{},5);
    show("transposition",{ {1,2}, {2}, {3}, {} },{3},3);
    show("depth cap",tree,{7},2);
    show("node cap",tree,{7},5,8);
    cout<<"checks = PASS\n";
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static final class Pass {
        int limit;
        String code;
        long[] counts;
        Pass(int limit,String code,long[] counts) { this.limit=limit; this.code=code; this.counts=counts.clone(); }
    }
    static final class Result {
        String status;
        int limit;
        List<Integer> path;
        long[] stats;
        List<Pass> passes;
        Result(String status,int limit,List<Integer> path,long[] stats,List<Pass> passes) {
            this.status=status; this.limit=limit; this.path=new ArrayList<>(path); this.stats=stats.clone();
            this.passes=new ArrayList<>();
            for(Pass p:passes) this.passes.add(new Pass(p.limit,p.code,p.counts));
        }
    }
    static final class IterativeDeepening {
        int[][] graph;
        boolean[] goals,onPath;
        List<Integer> path=new ArrayList<>(),answer=new ArrayList<>();
        List<Pass> passes=new ArrayList<>();
        long nodes,edges,cutoffs,cycles,peak,budget;

        IterativeDeepening(int[][] input) {
            if(input.length<1 || input.length>128) throw new IllegalArgumentException("invalid graph size");
            graph=new int[input.length][]; long total=0;
            for(int i=0;i<input.length;++i) {
                graph[i]=input[i].clone(); total+=graph[i].length;
                for(int v:graph[i]) if(v<0 || v>=graph.length) throw new IllegalArgumentException("invalid successor");
            }
            if(total>4096) throw new IllegalArgumentException("too many edges");
        }
        boolean isGoal(int state) { return goals[state]; }
        int[] successors(int state) { return graph[state]; }
        String visit(int state,int remaining) {
            if(nodes>=budget) return "ABORT";
            ++nodes; peak=Math.max(peak,path.size()-1);
            if(isGoal(state)) { answer=new ArrayList<>(path); return "FOUND"; }
            if(remaining==0) {
                for(int child:successors(state)) {
                    ++edges;
                    if(onPath[child]) { ++cycles; continue; }
                    ++cutoffs; return "CUTOFF";
                }
                return "FAILURE";
            }
            boolean sawCutoff=false;
            for(int child:successors(state)) {
                ++edges;
                if(onPath[child]) { ++cycles; continue; }
                path.add(child); onPath[child]=true;
                String result=visit(child,remaining-1);
                onPath[child]=false; path.remove(path.size()-1);
                if(result.equals("FOUND") || result.equals("ABORT")) return result;
                sawCutoff=sawCutoff || result.equals("CUTOFF");
            }
            return sawCutoff ? "CUTOFF" : "FAILURE";
        }
        Result run(int start,int[] goalStates,int maxDepth,long nodeBudget) {
            int n=graph.length;
            if(start<0 || start>=n || goalStates.length>128 || maxDepth<0 || maxDepth>64 || nodeBudget<1 || nodeBudget>10_000_000)
                throw new IllegalArgumentException("invalid search parameters");
            for(int g:goalStates) if(g<0 || g>=n) throw new IllegalArgumentException("invalid goal");
            goals=new boolean[n]; onPath=new boolean[n]; for(int g:goalStates) goals[g]=true;
            path.clear(); answer=new ArrayList<>(); passes.clear(); nodes=edges=cutoffs=cycles=peak=0; budget=nodeBudget;
            for(int limit=0;limit<=maxDepth;++limit) {
                long[] before={nodes,edges,cutoffs,cycles};
                path.add(start); onPath[start]=true;
                String code=visit(start,limit);
                onPath[start]=false; path.remove(path.size()-1);
                if(!path.isEmpty()) throw new IllegalStateException("path undo failed");
                for(boolean used:onPath) if(used) throw new IllegalStateException("membership undo failed");
                long[] now={nodes,edges,cutoffs,cycles},delta=new long[4];
                for(int i=0;i<4;++i) delta[i]=now[i]-before[i];
                passes.add(new Pass(limit,code,delta));
                if(!code.equals("CUTOFF") || limit==maxDepth) {
                    String status=code.equals("FOUND") ? "FOUND" : code.equals("FAILURE") ? "NO_SOLUTION" : code.equals("ABORT") ? "NODE_LIMIT" : "DEPTH_LIMIT";
                    return new Result(status,limit,answer,new long[] {nodes,edges,cutoffs,cycles,peak},passes);
                }
            }
            throw new IllegalStateException("unreachable driver state");
        }
    }
    static void show(String name,int[][] graph,int[] goals,int depth,long budget) {
        Result r=new IterativeDeepening(graph).run(0,goals,depth,budget);
        StringBuilder out=new StringBuilder(name+": "+r.status+", limit="+r.limit+", path=[");
        for(int i=0;i<r.path.size();++i) { if(i>0) out.append(','); out.append(r.path.get(i)); }
        System.out.println(out+"]"); out=new StringBuilder();
        String[] labels={"nodes","edges","cutoffs","cycles","peak"};
        for(int i=0;i<labels.length;++i) { if(i>0) out.append(", "); out.append(labels[i]).append('=').append(r.stats[i]); }
        System.out.println(out+", restored=YES"); out=new StringBuilder("passes=[");
        for(int i=0;i<r.passes.size();++i) {
            if(i>0) out.append(','); Pass p=r.passes.get(i);
            out.append(p.limit).append(':').append(p.code).append(':').append(p.counts[0]);
        }
        System.out.println(out+"]");
    }
    public static void main(String[] args) {
        int[][] tree={ {1,2}, {3,4}, {5}, {6}, {}, {7}, {}, {} };
        show("worked",tree,new int[] {7},5,1_000_000);
        show("boundary goal",tree,new int[] {5},2,1_000_000);
        show("root goal",tree,new int[] {0},0,1);
        show("dead leaf",new int[][] { {} },new int[] {},5,1_000_000);
        show("cycle",new int[][] { {1}, {0} },new int[] {},5,1_000_000);
        show("transposition",new int[][] { {1,2}, {2}, {3}, {} },new int[] {3},3,1_000_000);
        show("depth cap",tree,new int[] {7},2,1_000_000);
        show("node cap",tree,new int[] {7},5,8);
        System.out.println("checks = PASS");
    }
}

Expected standard output, identical in all three languages:

• worked: FOUND, limit=3, path=[0,2,5,7]
• nodes=18, edges=19, cutoffs=5, cycles=0, peak=3, restored=YES
• passes=[0:CUTOFF:1,1:CUTOFF:3,2:CUTOFF:6,3:FOUND:8]
• boundary goal: FOUND, limit=2, path=[0,2,5]
• nodes=10, edges=11, cutoffs=4, cycles=0, peak=2, restored=YES
• passes=[0:CUTOFF:1,1:CUTOFF:3,2:FOUND:6]
• root goal: FOUND, limit=0, path=[0]
• nodes=1, edges=0, cutoffs=0, cycles=0, peak=0, restored=YES
• passes=[0:FOUND:1]
• dead leaf: NO_SOLUTION, limit=0, path=[]
• nodes=1, edges=0, cutoffs=0, cycles=0, peak=0, restored=YES
• passes=[0:FAILURE:1]
• cycle: NO_SOLUTION, limit=1, path=[]
• nodes=3, edges=3, cutoffs=1, cycles=1, peak=1, restored=YES
• passes=[0:CUTOFF:1,1:FAILURE:2]
• transposition: FOUND, limit=2, path=[0,2,3]
• nodes=9, edges=10, cutoffs=4, cycles=0, peak=2, restored=YES
• passes=[0:CUTOFF:1,1:CUTOFF:3,2:FOUND:5]
• depth cap: DEPTH_LIMIT, limit=2, path=[]
• nodes=10, edges=12, cutoffs=5, cycles=0, peak=2, restored=YES
• passes=[0:CUTOFF:1,1:CUTOFF:3,2:CUTOFF:6]
• node cap: NODE_LIMIT, limit=2, path=[]
• nodes=8, edges=10, cutoffs=4, cycles=0, peak=2, restored=YES
• passes=[0:CUTOFF:1,1:CUTOFF:3,2:ABORT:4]
• checks = PASS

Complexity, Correctness, and Invariants

Let $b$ bound branching, $d$ be the minimum goal depth, $D$ the configured cap, and $P$ the number of attempted passes. Let $N_i$ count path occurrences at depth $i$ in the search tree after current-path cycle pruning. With unlimited resources, the number of admitted calls through the first successful limit is bounded by

$$N_{\mathrm{ID}}\le\sum_{i=0}^{d}(d-i+1)N_i.$$

A depth-$i$ occurrence can be revisited in passes $i$ through $d$; the final pass may stop early. In a regular tree with constant $b\gt1$, $N_i=b^i$, giving $O(b^d)$ admitted calls. Compared with one fully explored tree through depth $d$, the ratio of the two full-sum node counts tends to $b/(b-1)$. This statement concerns that regular-tree model, not every graph or child order. On a single chain with a goal at depth $d$, the exact count is

$$1+2+\cdots+(d+1)=\frac{(d+1)(d+2)}{2}=\Theta(d^2).$$

For the actual programs, use measured work: let $N$ be all admitted calls and $E_{\mathrm{seen}}$ all tested adjacency entries. Constructor validation and graph copying cost $O(V+E)$. A run costs $O(V+P V+N+E_{\mathrm{seen}})$, including initializing flags and checking all $V$ marks after each pass; there is at most one final refused admission. Combined construction and search therefore cost $O(V+E+P V+N+E_{\mathrm{seen}})$. The node budget bounds admissions but is not an edge-check or wall-clock budget. A node with many cycle-blocked neighbors can still perform many edge checks.

Auxiliary storage in these programs is $O(V+D+P)=O(V+D)$: goal/path flags, the recursion and active/answer paths, and pass histories. The copied graph adds $O(V+E)$ storage. A generic implicit-tree implementation can use $O(d)$ active state/iterator storage with constant-size states and lazily generated successors; materializing all children in each stack frame instead gives up to $O(bd)$ storage. Large states or expensive generation must be charged explicitly.

Best, average, worst. A root goal needs one admitted call, zero tested edges, and one pass; construction and flag initialization still cost $O(V+E)$ for this adapter. There is no distribution-independent average-case bound: solution depth, branching, successor order, and transpositions determine it. Worst-case tree work reaches the full sums above through $D$ or until a resource limit stops it; cyclic graphs can have many simple-path occurrences despite small $V$. A finite goal-free tree eventually returns failure; an infinite, finitely branching goal-free tree can deepen forever without caps.

Why the result is correct. On entry, the active path is a legal simple path from the root to the current state, the marks equal exactly its states, and its depth plus remaining depth equals the pass limit. Goal detection copies a legal witness. With zero remaining depth, an admissible child proves that the bound excluded an extension; absence of one proves this branch exhausted. With positive remaining depth, induction over the child calls gives either a witness, a cutoff somewhere, or exhaustion of every admissible branch. Undo preserves the invariant between siblings and on all return paths.

If the complete-state graph has a goal-reaching walk containing a repeated state, removing the intervening cycle yields a shorter goal-reaching walk. Thus some shortest solution is simple and current-path cycle pruning preserves one. On a finite graph, there are finitely many such paths; eventually a pass either finds a goal or exhausts them. Since all smaller limits complete before the first successful one, the found path has minimum edge count. This argument assumes no ABORT, a sufficient depth cap, and no hidden history in state identity. A local FAILURE may depend on the current prefix; only exhaustion at the root warrants NO_SOLUTION.

Variants, Pitfalls, and Optimizations

Avoid naive visited sets. On edges $0\to1$, $0\to2$, $1\to2$, $2\to3$ with goal $3$ and limit $2$, DFS first reaches $2$ along $[0,1,2]$ with no depth left. It must later revisit $2$ along $[0,2]$ with one step left to find $3$. Marking $2$ visited for the entire pass loses that shallow solution; keeping visited marks between passes is also unsound. A depth-aware transposition scheme requires a proof accounting for remaining depth, completion, and path-dependent restrictions. Current-path marking is the simple safe baseline used here.

Preserve what the bound means. Increase limits by one to retain the first-found shallowest-path guarantee. Jumping from limit $2$ to $4$ can let DFS find a depth-$4$ goal before a different depth-$3$ goal. For weighted actions, use uniform-cost search or a properly specified IDA* search with thresholds on $f=g+h$, not merely the number of recursive calls. If all edges share one positive cost, minimum depth and minimum cost agree.

Choose the representation deliberately. An explicit graph with modest $V+E$ generally favors BFS; IDDFS can repeatedly enumerate exponentially many path prefixes through a small graph. For a huge implicit state space, retain only the active path and successor iterator. If puzzle actions mutate a shared state, pair every apply with undo even on success, timeout, or cancellation. The sample's ABORT handling demonstrates the same requirement, but an exception thrown by a user-provided successor hook would need its own exception-safe cleanup.

Use move ordering for speed, without changing correctness. Stable child order makes traces reproducible; reordering children can reduce the final pass's work and change which equal-depth goal is returned. Game-playing programs also repeat depth-limited searches to improve move ordering and retain the last fully completed evaluation under a time budget. Their heuristic minimax evaluations and completed-depth policy solve a different task from this first-goal IDDFS; they do not inherit a shortest-solution claim.

Make limits honest. DEPTH_LIMIT and NODE_LIMIT mean unknown, even when the answer field is empty. A finite graph with a distant goal can need a deeper cap; a shallow graph with many transpositions can consume the node budget. For a real latency bound, add time or edge checks as well as node checks, propagate cancellation separately from failure, and keep the restoration invariant. C++ and Java use 64-bit counters; even without counter overflow, the number of paths can become impractical.

Practice Problems and Real-World Use

Start with a hand trace, then compare against an independent breadth-first oracle on small graphs. Check both the minimum edge count and the exact path under stable child order; separately test restoration, repeated runs, and the meaning of a limited result. Boundary fixtures should include a root goal, a goal exactly at the cap, an exhausted leaf, an empty goal set, self-loops, duplicate edges, and a cycle that has no reachable goal.

The programs were checked on 6,923 inputs per language: all $512$ directed three-vertex graphs with all $8$ goal subsets, $1{,}500$ randomized cyclic graphs, $1{,}000$ randomized trees, $300$ transposition-rich acyclic graphs, $13$ boundary fixtures, and $14$ invalid inputs. For all $6{,}909$ valid inputs, an independent bounded-path event oracle verified outcomes, paths, every counter, and per-pass histories; a graph BFS oracle verified shallowest-path behavior. There were $54{,}514$ path-restoration audits, and C++ and Java matched Python on the full corpus and repeated runs. The C++ corpus also passed address and undefined-behavior instrumentation; these checks support this bounded implementation rather than implying a guarantee for arbitrary adapters.

For primary background, see Poole and Mackworth's iterative-deepening discussion and the AIMA authors' search chapter. They discuss the depth/memory tradeoff and repeated-pass analysis; the exact cutoff probes, instrumentation, resource contract, code, and worked trace here are specified explicitly in this lesson.