BFS on Implicit Graphs, in depth: designing states, generating neighbours, visited-set memory, the 8-puzzle, bidirectional search and when the state space is too big

What makes a graph implicit

An implicit graph is given by three things: one or more start states, a successor function neighbors(state), and a goal test. Nodes are created when the search first generates them and are never stored as an adjacency structure. The graph may be infinite; BFS only touches the part within the answer's distance.

BFS answers the minimum number of moves because it explores in layers: every state at distance d is dequeued before any state at distance d + 1. That guarantee requires every move to cost the same. If moves have two costs, 0 and 1, use 0-1 BFS; if they have arbitrary non-negative costs, use Dijkstra's algorithm. Implicit generation works with both.

The template, and two details that matter

from collections import deque

def bfs(starts, neighbors, is_goal):
    """Shortest path in an implicit unweighted graph. Returns the list of states, or None."""
    parent = {s: None for s in starts}          # doubles as the visited set
    for s in starts:
        if is_goal(s):
            return [s]
    queue = deque(starts)
    while queue:
        state = queue.popleft()
        for nxt in neighbors(state):
            if nxt in parent:                     # seen: skip (marked when first generated)
                continue
            parent[nxt] = state
            if is_goal(nxt):                      # test at generation: saves a whole layer
                path = [nxt]
                while parent[path[-1]] is not None:
                    path.append(parent[path[-1]])
                return path[::-1]
            queue.append(nxt)
    return None

Two details distinguish a correct and efficient implicit BFS from one that merely works on small inputs. First, mark a state visited when it is generated, not when it is dequeued. Marking on dequeue lets the same state enter the queue once per predecessor, and on a densely connected state space the queue grows many times larger than the number of distinct states.

Second, test the goal when a state is generated. Testing on dequeue is also correct, but it first generates the whole next layer, which at branching factor 10 is ten times the states you needed. The parent map doubles as the visited set and rebuilds the path.

Designing the state: everything that changes the future, nothing else

A state must contain every piece of information that affects which moves are legal next or whether the goal is reached. Leave something out and BFS merges situations that are not equivalent, which gives wrong answers: a robot at cell (3, 4) holding key a and the same robot without it are different states, because one can open door A. Put something extra in, such as the number of moves taken or the full path, and states that are equivalent look distinct, so the visited set never deduplicates them and the search explodes.

The classic augmentation is a bitmask of collected items or used resources. A maze with six key types has rows * cols * 64 states; a grid where you may break up to k walls has rows * cols * (k + 1). Each extra dimension multiplies the space, so check the product against your memory budget before writing code.

# Grid with doors 'A'..'F' and keys 'a'..'f': state = (row, col, keys_held_bitmask)
def neighbors(state, grid):
    r, c, keys = state
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nr, nc = r + dr, c + dc
        if not (0 <= nr < len(grid) and 0 <= nc < len(grid[0])):
            continue
        cell = grid[nr][nc]
        if cell == "#":
            continue
        if "A" <= cell <= "F" and not keys & (1 << (ord(cell) - ord("A"))):
            continue                               # locked door, key not held
        nkeys = keys | (1 << (ord(cell) - ord("a"))) if "a" <= cell <= "f" else keys
        yield (nr, nc, nkeys)

Symmetry reduction works the other way: map states equivalent under rotation, reflection or relabelling to one canonical representative before inserting them. It can shrink the space by the symmetry group's size, if the canonicalization is exact.

Encoding states for speed and memory

In Python a tuple of nine small integers costs roughly 120 bytes plus about a hundred for its dictionary entry, so a hundred million states are out of reach. Encoding states as integers changes the constant: a 3x3 board fits in 36 bits (nine 4-bit cells), a grid position with a key mask packs as (r * cols + c) << 6 | keys, and integers hash fast and compactly. In C++, Java or Rust, the same packing turns the visited set into a flat bit array when states can be ranked densely into the range 0 to N - 1, which costs one bit per possible state.

Choose the representation that makes neighbour generation cheap; swapping two nibbles in a 36-bit integer beats building new tuples. Measure states per second on a small instance to estimate run time.

Worked example: the 8-puzzle

The 8-puzzle has 9! = 362,880 arrangements of eight tiles and a blank, but a parity argument splits them in half. Each move slides a tile horizontally or vertically. A horizontal move does not change the order of tiles read row by row; a vertical move jumps a tile over two others, changing the inversion count by an even amount. So on a 3-wide board the parity of the inversion count never changes, and exactly 181,440 positions are reachable from the goal. Checking parity first answers unsolvable instances instantly instead of exhausting the whole half of the space.

GOAL = (1, 2, 3, 4, 5, 6, 7, 8, 0)
ADJ = {0: (1, 3), 1: (0, 2, 4), 2: (1, 5), 3: (0, 4, 6), 4: (1, 3, 5, 7),
       5: (2, 4, 8), 6: (3, 7), 7: (4, 6, 8), 8: (5, 7)}

def solvable(board):                        # 3x3: solvable iff the inversion count is even
    tiles = [t for t in board if t]
    inv = sum(1 for i in range(len(tiles)) for j in range(i + 1, len(tiles)) if tiles[i] > tiles[j])
    return inv % 2 == 0

def neighbors(board):
    z = board.index(0)
    for k in ADJ[z]:                         # slide a neighbouring tile into the blank
        b = list(board)
        b[z], b[k] = b[k], b[z]
        yield tuple(b)

start = (8, 6, 7, 2, 5, 4, 3, 0, 1)
if solvable(start):
    path = bfs([start], neighbors, lambda b: b == GOAL)
    print(len(path) - 1, "moves")           # this is one of the hardest positions: 31 moves

Run from the start above, BFS reports 31 moves, the maximum for any solvable 8-puzzle position, after visiting essentially the entire reachable space of 181,440 states. The same approach does not scale up a size: the 15-puzzle has 16!/2, about 1.05 times 10 to the 13th, reachable states, and a visited set that large does not fit in memory. For 4-wide boards the parity rule also changes, because a vertical move then jumps three tiles, so solvability depends on the inversion count together with the blank's row.

Generating neighbours efficiently

Neighbour generation is the inner loop, and its cost is easy to underestimate. In a word ladder, the obvious generator tries every position and every letter, then checks the dictionary: 26 times L candidates per word, most of which are not words. A precomputed bucket index turns this around: each word is filed under its wildcard patterns, and a word's neighbours are the other members of its buckets.

from collections import defaultdict

def build_buckets(words):
    buckets = defaultdict(list)                     # "h*t" -> ["hat", "hit", "hot", "hut"]
    for w in words:
        for i in range(len(w)):
            buckets[w[:i] + "*" + w[i + 1:]].append(w)
    return buckets

def word_neighbors(word, buckets):
    for i in range(len(word)):
        for other in buckets[word[:i] + "*" + word[i + 1:]]:
            if other != word:
                yield other

Precompute whatever makes the successor function return only legal states, such as walls, bounds or the position adjacency in the ADJ table above. When most generated candidates are rejected, the generator, not the queue, is the bottleneck.

Multi-source BFS

When the question is the distance from the nearest of many sources, such as the distance from every cell to the closest exit or the time for rot to spread from several cells, put all sources in the queue at distance 0 before starting. BFS then grows all frontiers together, and each state is labelled with its distance to the nearest source in one pass, instead of one search per source.

Bidirectional BFS, and the stopping rule people get wrong

If moves are reversible and the goal is a single known state, search forward from the start and backward from the goal at the same time. With branching factor b and answer depth d, one search visits on the order of b to the power d states; two searches that meet in the middle visit about twice b to the power d/2. For b = 10 and d = 12 that is a trillion versus two million.

The common bug is stopping as soon as a newly generated state is found in the other side's visited set. The first contact is not necessarily on a shortest path: another state in the same layer may meet the other side one step earlier. The correct rule is to finish expanding the whole current layer, take the minimum of dist_a[s] + 1 + dist_b[t] over all meeting edges found, and return that.

def bidirectional_bfs(start, goal, neighbors):    # neighbors must be symmetric (undirected moves)
    if start == goal:
        return 0
    dist_a, dist_b = {start: 0}, {goal: 0}
    front_a, front_b = [start], [goal]
    while front_a and front_b:
        if len(front_a) > len(front_b):            # always grow the smaller side
            front_a, front_b, dist_a, dist_b = front_b, front_a, dist_b, dist_a
        best, nxt = None, []
        for s in front_a:                          # expand the WHOLE layer before stopping
            for t in neighbors(s):
                if t in dist_b:
                    cand = dist_a[s] + 1 + dist_b[t]
                    best = cand if best is None else min(best, cand)
                if t not in dist_a:
                    dist_a[t] = dist_a[s] + 1
                    nxt.append(t)
        if best is not None:
            return best
        front_a = nxt
    return None

Expanding the smaller frontier keeps the sides balanced. For the path itself, keep parent maps on both sides and join them at the best meeting edge. Irreversible moves need a predecessor function for the backward side.

Sizing the state space before searching

Before running BFS, multiply the state's components (positions times masks times counters), discount by reachability arguments such as parity, and multiply by bytes per visited entry. Compare that with memory, and the states-per-second rate with your time.

A* with an admissible heuristic (one that never overestimates the remaining moves, such as summed Manhattan distances in sliding puzzles) explores far fewer states when the heuristic is informative. IDDFS (iterative deepening DFS) needs memory proportional to depth only, re-exploring shallow layers instead. Explicit-state model checkers such as TLA+'s TLC are, at heart, BFS over system states, which is why they report the shortest trace to a violated invariant.

Failure modes

• Missing state component. Wrong answers that look plausible, typically on test cases with keys, budgets or toggles. Ask what information a move consults, and put all of it in the state.
• Path or step count inside the state. Deduplication never fires and memory grows without bound. Keep those in the parent or distance map.
• Marking visited on dequeue. Queue sizes many times larger than the state count, then memory exhaustion.
• Mutable states as keys. Use immutable or encoded states.
• Unequal move costs treated as equal. BFS returns the fewest moves, not the cheapest path. Switch to 0-1 BFS or Dijkstra.
• Early stop in bidirectional search. Answers that are one or two moves too long on some inputs. Finish the layer and take the minimum.
• Unsolvable instances searched exhaustively. Check invariants such as parity first.

What to do next

1. Write the state as a tuple, then list every fact a move or goal test reads and confirm each one is in it.
2. Estimate the reachable state count and the bytes per visited entry before writing the search.
3. Start from the template: mark visited and test the goal at generation, and keep a parent map for paths.
4. Encode states as integers once the logic is correct, and measure states per second on a small instance.
5. Precompute adjacency or buckets so the successor function only yields legal states.
6. For a single known goal with reversible moves, try bidirectional BFS with the full-layer stopping rule.
7. If the estimate exceeds memory, move to A* with an admissible heuristic or IDDFS, and read the backtracking guide for pruning techniques.