Open the Lock: BFS Shortest Path on State Graph

You have a lock with 4 circular wheels, each displaying a digit from 0 to 9. You start at "0000" and need to reach a target combination. Each move turns one wheel by one slot (0 goes to 1 or 9, 9 goes to 0 or 8). Some combinations are deadends that permanently jam the lock. Find the minimum number of moves to reach the target, or return -1 if it is impossible.

This is LeetCode 752: Open the Lock, and it is one of the cleanest examples of BFS on a state-space graph. The trick is recognizing that each 4-digit combination is a node, each single-digit turn is an edge, and "minimum moves" is just "shortest path in an unweighted graph."

Problem statement

Given a list of deadends (combinations that lock the wheels permanently) and a target string, return the minimum number of turns needed to go from "0000" to target. If you land on a deadend at any point, that path is blocked. If the target is unreachable, return -1.

Approach: BFS on state space

Think of every possible 4-digit combination (from "0000" to "9999") as a node in a graph. Two nodes share an edge if they differ by exactly one digit, and that digit differs by exactly 1 (wrapping around: 0 and 9 are adjacent). That gives each node up to 8 neighbors (4 wheels times 2 directions).

BFS from "0000" explores combinations level by level. Level 0 is just "0000". Level 1 is every combination one turn away. Level 2 is everything two turns away. The first time BFS reaches the target, the current level is the answer. Deadends act as walls: when BFS tries to visit a deadend, it skips that node entirely.

This works because BFS always finds the shortest path in an unweighted graph. Every edge has cost 1 (one turn), so the first arrival at any node is guaranteed to be via the shortest route.

from collections import deque

def open_lock(deadends: list[str], target: str) -> int:
    dead = set(deadends)
    if "0000" in dead:
        return -1

    visited = {"0000"}
    queue = deque([("0000", 0)])

    while queue:
        combo, dist = queue.popleft()

        if combo == target:
            return dist

        for i in range(4):
            digit = int(combo[i])
            for delta in (1, -1):
                new_digit = (digit + delta) % 10
                neighbor = combo[:i] + str(new_digit) + combo[i + 1:]
                if neighbor not in visited and neighbor not in dead:
                    visited.add(neighbor)
                    queue.append((neighbor, dist + 1))

    return -1

Visual walkthrough

Let's trace BFS through a concrete example: deadends = ["0201", "0101", "0102", "1212", "2002"], target = "0202". Watch how BFS expands level by level, skipping deadends, until it finds the shortest path.

The key observation: BFS hit deadends "0101", "0102", and "0201" during expansion and simply skipped them. It found an alternate route to "0202" through "0200" in just 3 turns. Because BFS explores all nodes at distance d before any node at distance d+1, the first time it sees "0202" is guaranteed to be the shortest path.

Complexity analysis

The state space is bounded by 10^4 = 10,000 total combinations. BFS visits each at most once. For each combination, generating 8 neighbors costs O(4) for string manipulation. The total is O(10,000 * 4) which is effectively O(1) since the input size does not change. In practice, BFS often terminates well before visiting all 10,000 states.

Building blocks

1. BFS shortest path on an implicit graph

The core pattern is BFS where you generate neighbors on the fly instead of building an adjacency list upfront:

queue = deque([(start, 0)])
visited = {start}

while queue:
    state, dist = queue.popleft()
    if state == target:
        return dist
    for neighbor in get_neighbors(state):
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append((neighbor, dist + 1))

This template appears in Word Ladder (neighbors are one-letter-apart words), sliding puzzles (neighbors are board states after one tile move), and many other "minimum moves" problems. The only thing that changes between problems is how get_neighbors works.

2. Circular digit neighbor generation

The lock-specific neighbor generation turns each of the 4 wheels forward and backward:

for i in range(4):
    digit = int(combo[i])
    for delta in (1, -1):
        new_digit = (digit + delta) % 10
        neighbor = combo[:i] + str(new_digit) + combo[i + 1:]

The modular arithmetic (digit + delta) % 10 handles the wrap-around: turning 9 forward gives 0, and turning 0 backward gives 9 (since (0 - 1) % 10 = 9 in Python). This same circular-neighbor idea appears in any problem with wrap-around indexing or cyclic structures.

Edge cases

• "0000" is a deadend: Return -1 immediately. You cannot even start since the initial state is locked.
• Target is "0000": Return 0. You are already at the target with zero moves.
• Target is a deadend: Return -1. The target itself is unreachable since landing on it locks the wheels.
• No path exists: BFS exhausts the queue without finding the target. Return -1. This happens when deadends form a wall that completely separates "0000" from the target.
• Empty deadends list: The problem simplifies to pure BFS with no blocked nodes. The shortest path is guaranteed to exist.

From understanding to recall

You have seen how BFS on a state graph solves Open the Lock. The neighbor generation with modular arithmetic, the deadend check, the visited set that prevents revisiting states. It all clicks when you read through it. But in an interview, you need to write the 4-wheel loop, the (digit + delta) % 10 expression, and the BFS template from memory.

Spaced repetition makes those details automatic. CodeBricks drills the BFS-on-implicit-graph building block and the circular-neighbor-generation pattern independently. You type each piece from scratch at increasing intervals until the code flows out without hesitation. When a state-space BFS problem appears in your interview, you do not pause to reconstruct the logic. You just write it.

Related posts

• Word Ladder - Another BFS shortest path on an implicit graph, where words are nodes and single-letter changes are edges
• Number of Islands - Grid BFS/DFS traversal showing how implicit graphs arise from 2D structures
• Clone Graph - Graph traversal with a hash map, demonstrating the visited-set pattern that BFS relies on