Problem Statement
Open the Lock
Picture a padlock with 4 little wheels, and each wheel shows a digit from 0 to 9. You start with all wheels at zero, so the lock reads '0000'. One move means turning a single wheel up or down by one notch. Your job is to find the smallest number of moves needed to reach a target combination. There is a catch: some combinations are "deadends", and if a wheel ever lands on one, the lock jams and you cannot move from there. The natural way to think about this is a graph. A graph is just dots (called states) connected by lines (called edges) that show which dots you can reach from which. Here, each dot is one 4-digit combination, and a line connects two combinations when they are exactly one wheel-turn apart. Every combination has 8 neighbors, because each of the 4 wheels can be nudged up or down (4 wheels times 2 directions is 8). To find the fewest moves, we use BFS, which stands for breadth-first search. BFS explores a graph in rings: first everything reachable in 0 moves, then everything reachable in 1 move, then 2 moves, and so on, like ripples spreading out from where you dropped a stone in water. Because BFS reaches the nearest dots before the farther ones, the very first time it touches the target, it has used the smallest possible number of moves to get there. That is exactly what this problem asks for.
Signals to notice
Brute force first
DFS trying all combinations — doesn't find shortest path efficiently. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.
The key insight
BFS on the state space: each state is a 4-digit string. From each state, generate 8 neighbors (each digit ±1). Skip deadends. The first time you reach the target is the shortest path. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.
Trace it on deadends=["0201","0101","0102","1212","2002"], target="0202"
init: visited={5 deadends, '0000'}, queue=['0000'], steps=0
steps=0: pop '0000' != target; enqueue 8 neighbors (1000,9000,0100,0900,0010,0090,0001,0009) -> steps=1
steps=1: process those 8, none == target; enqueue their unseen neighbors (deadends 0201/0101/0102 stay blocked) -> steps=2
steps=2: process level (e.g. 0200,0002,...), no target; expand outward -> steps=3
steps=3: still no '0202' (its approaches via 0201/0102 are deadends, blocked) -> steps=4
steps=4: frontier reaches near target via open paths, no match yet -> steps=5
steps=5: expand; '0202' now enqueued from an allowed neighbor (e.g. 0212 or 0203) -> steps=6
steps=6: pop '0202' == target -> return 6What must stay true
BFS guarantees shortest path. Each state has exactly 8 neighbors (4 digits × 2 directions). The state space is bounded at 10,000 possible combinations. If that remains true after every update, the rest of the reasoning has a stable place to stand.
Shape of the loop
visited = set(deadends); if '0000' in visited: return -1
queue = ['0000']; visited.add('0000'); steps = 0
while queue:
for each state in current level:
if state == target: return steps
for each of 8 neighbors (digit ±1): if unseen, mark visited + enqueue
steps += 1Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Not pre-loading deadends into the visited set — deadends should be marked as visited before BFS starts so they're never explored. The fix is usually to return to the meaning of each move, not just the steps themselves.