33.07Intermediate / Advanced5 topics17 min5 interactive animations

Implicit graph searches

Many puzzles are graphs that are never written down: states are vertices and moves are edges, and BFS over the states finds the fewest moves.

Learning goals

Model a puzzle as states and moves and run BFS without building the graph
Solve word ladder and a combination lock with BFS over states
Move on a grid with direction arrays and bounds checks
Encode a state as a bitmask when the state is a set of 0/1 flags

Prerequisites

Breadth-first searchHash sets and mapsBit manipulation

A Rubik's cube has far too many positions to store as a graph, yet BFS can still find the shortest solution of smaller puzzles, because it only needs to generate the neighbours of the state it is looking at.

33.07.1

State-space BFS

An **implicit graph** is defined by a rule, not a list: a *state* is a vertex, and a function next(state) returns the states one move away. BFS needs only the start, a way to test the goal, and that function. A hash map from state to distance replaces the visited array and records distances.

The cost is the number of states reachable before the goal is found, times the cost of generating neighbours. If states are too many, search from both ends or use A* (in a later chapter). The *Combination lock* and *Switch puzzle* options in the animation are small examples.

Java

1static <S> int minMoves(S start, S goal, Function<S, List<S>> next) {   // fewest moves, or -1
2    Map<S, Integer> dist = new HashMap<>();
3    Deque<S> queue = new ArrayDeque<>();
4    dist.put(start, 0);
5    queue.add(start);
6    while (!queue.isEmpty()) {
7        S state = queue.poll();
8        if (state.equals(goal)) return dist.get(state);
9        for (S nb : next.apply(state))
10            if (!dist.containsKey(nb)) { dist.put(nb, dist.get(state) + 1); queue.add(nb); }
11    }
12    return -1;
13}

BFS on implicit graphs: word ladder, lock, switch configurations

Interactive · edit the input

word graph (edges appear when the search examines them) · 7 vertices · 0 edges

hit

hot

dot

dog

lot

log

cog

Being expandedDiscoveredVisitedTarget / on the answerDead end

queue

hit

Setup

Words are vertices; two words are neighbours when they differ in exactly one letter and the next word is in the list. No edge list is built: the neighbours of a word are generated by changing one letter at a time. Count the words in the chain, so hit counts as 1.

Step 1 / 8

Java

1int ladderLength(String begin, String end, Set<String> words) {   // number of words in the shortest chain
2    Deque<String> q = new ArrayDeque<>(); Map<String, Integer> dist = new HashMap<>();
3    q.add(begin); dist.put(begin, 1);
4    while (!q.isEmpty()) {
5        String u = q.poll();
6        if (u.equals(end)) return dist.get(u);
7        char[] c = u.toCharArray();
8        for (int i = 0; i < c.length; i++) {
9            char keep = c[i];
10            for (char x = 'a'; x <= 'z'; x++) {  // neighbours are generated, never stored
11                c[i] = x;
12                String v = new String(c);
13                if (words.contains(v) && !dist.containsKey(v)) { dist.put(v, dist.get(u) + 1); q.add(v); }
14            }
15            c[i] = keep;
16        }
17    }
18    return 0;
19}
20int openLock(Set<String> dead, String start, String target) {     // a lock of any number of wheels
21    if (dead.contains(start)) return -1;
22    Deque<String> q = new ArrayDeque<>(); Set<String> seen = new HashSet<>();
23    q.add(start); seen.add(start);
24    for (int turns = 0; !q.isEmpty(); turns++) {          // one iteration per BFS level
25        for (int k = q.size(); k > 0; k--) {
26            String u = q.poll();
27            if (u.equals(target)) return turns;
28            for (int i = 0; i < u.length(); i++)
29                for (int d : new int[]{1, 9}) {           // turn one wheel up or down
30                    char[] c = u.toCharArray();
31                    c[i] = (char) ('0' + (c[i] - '0' + d) % 10);
32                    String v = new String(c);
33                    if (!dead.contains(v) && seen.add(v)) q.add(v);
34                }
35        }
36    }
37    return -1;
38}
39int minPresses(int start, int n) {               // bits as an int; pressing bit i flips i-1, i, i+1
40    int[] dist = new int[1 << n]; Arrays.fill(dist, -1);
41    Deque<Integer> q = new ArrayDeque<>(); q.add(start); dist[start] = 0;
42    while (!q.isEmpty()) {
43        int u = q.poll();
44        if (u == 0) return dist[u];
45        for (int i = 0; i < n; i++) {
46            int mask = (1 << i) | (i > 0 ? 1 << (i - 1) : 0) | (i + 1 < n ? 1 << (i + 1) : 0);
47            int v = u ^ mask;
48            if (dist[v] == -1) { dist[v] = dist[u] + 1; q.add(v); }
49        }
50    }
51    return -1;
52}

Live state

0 states visited

begin

hit

end

cog

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L3	begin=hit end=cog	Words are vertices; two words are neighbours when they differ in exactly one letter and the next word is in the list. No edge list is built: the neighbours of a word are generated by changing one letter at a time. Count the words in the chain, so hit counts as 1.
2	L13	u=hit chain length=1 discovered=hot	Dequeue hit (chain length 1): one-letter neighbours not seen before: hot.
3	L13	u=hot chain length=2 discovered=dot lot	Dequeue hot (chain length 2): one-letter neighbours not seen before: dot, lot.
4	L13	u=dot chain length=3 discovered=dog	Dequeue dot (chain length 3): one-letter neighbours not seen before: dog.
5	L13	u=lot chain length=3 discovered=log	Dequeue lot (chain length 3): one-letter neighbours not seen before: log.
6	L13	u=dog chain length=4 discovered=cog	Dequeue dog (chain length 4): one-letter neighbours not seen before: cog.
7	L13	u=log chain length=4 discovered=none	Dequeue log (chain length 4): no unseen one-letter neighbour in the list.
8	L6	return=5	cog dequeued with 5 words in the chain: the shortest transformation has 5 words (4 changes).

33.07.2

Word ladder

In **word ladder** each word in the list is a vertex, and two words are joined if they differ in exactly one letter. Find the fewest changes to turn the begin word into the end word, where every step must be a word from the list. The graph is never built: to find neighbours, try replacing each position with each letter a to z and keep the results that are in the word set.

If the end word is not in the list the answer is none; the animation's second preset shows that case. With L letters and W words the work is about W x L x 26 set lookups of L-letter strings.

Java

1static int ladderSteps(String begin, String end, Collection<String> words) {   // number of one-letter changes, or -1
2    Set<String> dict = new HashSet<>(words);
3    if (!dict.contains(end)) return -1;
4    Map<String, Integer> dist = new HashMap<>();
5    Deque<String> queue = new ArrayDeque<>();
6    dist.put(begin, 0);
7    queue.add(begin);
8    while (!queue.isEmpty()) {
9        String w = queue.poll();
10        if (w.equals(end)) return dist.get(w);
11        char[] cs = w.toCharArray();
12        for (int i = 0; i < cs.length; i++) {
13            char keep = cs[i];
14            for (char c = 'a'; c <= 'z'; c++) {
15                if (c == keep) continue;
16                cs[i] = c;
17                String nb = new String(cs);
18                if (dict.contains(nb) && !dist.containsKey(nb)) { dist.put(nb, dist.get(w) + 1); queue.add(nb); }
19            }
20            cs[i] = keep;                                          // restore before the next position
21        }
22    }
23    return -1;
24}

BFS on implicit graphs: word ladder, lock, switch configurations

Interactive · edit the input

word graph (edges appear when the search examines them) · 7 vertices · 0 edges

hit

hot

dot

dog

lot

log

cog

Being expandedDiscoveredVisitedTarget / on the answerDead end

queue

hit

Setup

Step 1 / 8

Java

1int ladderLength(String begin, String end, Set<String> words) {   // number of words in the shortest chain
2    Deque<String> q = new ArrayDeque<>(); Map<String, Integer> dist = new HashMap<>();
3    q.add(begin); dist.put(begin, 1);
4    while (!q.isEmpty()) {
5        String u = q.poll();
6        if (u.equals(end)) return dist.get(u);
7        char[] c = u.toCharArray();
8        for (int i = 0; i < c.length; i++) {
9            char keep = c[i];
10            for (char x = 'a'; x <= 'z'; x++) {  // neighbours are generated, never stored
11                c[i] = x;
12                String v = new String(c);
13                if (words.contains(v) && !dist.containsKey(v)) { dist.put(v, dist.get(u) + 1); q.add(v); }
14            }
15            c[i] = keep;
16        }
17    }
18    return 0;
19}
20int openLock(Set<String> dead, String start, String target) {     // a lock of any number of wheels
21    if (dead.contains(start)) return -1;
22    Deque<String> q = new ArrayDeque<>(); Set<String> seen = new HashSet<>();
23    q.add(start); seen.add(start);
24    for (int turns = 0; !q.isEmpty(); turns++) {          // one iteration per BFS level
25        for (int k = q.size(); k > 0; k--) {
26            String u = q.poll();
27            if (u.equals(target)) return turns;
28            for (int i = 0; i < u.length(); i++)
29                for (int d : new int[]{1, 9}) {           // turn one wheel up or down
30                    char[] c = u.toCharArray();
31                    c[i] = (char) ('0' + (c[i] - '0' + d) % 10);
32                    String v = new String(c);
33                    if (!dead.contains(v) && seen.add(v)) q.add(v);
34                }
35        }
36    }
37    return -1;
38}
39int minPresses(int start, int n) {               // bits as an int; pressing bit i flips i-1, i, i+1
40    int[] dist = new int[1 << n]; Arrays.fill(dist, -1);
41    Deque<Integer> q = new ArrayDeque<>(); q.add(start); dist[start] = 0;
42    while (!q.isEmpty()) {
43        int u = q.poll();
44        if (u == 0) return dist[u];
45        for (int i = 0; i < n; i++) {
46            int mask = (1 << i) | (i > 0 ? 1 << (i - 1) : 0) | (i + 1 < n ? 1 << (i + 1) : 0);
47            int v = u ^ mask;
48            if (dist[v] == -1) { dist[v] = dist[u] + 1; q.add(v); }
49        }
50    }
51    return -1;
52}

Live state

0 states visited

begin

hit

end

cog

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L3	begin=hit end=cog	Words are vertices; two words are neighbours when they differ in exactly one letter and the next word is in the list. No edge list is built: the neighbours of a word are generated by changing one letter at a time. Count the words in the chain, so hit counts as 1.
2	L13	u=hit chain length=1 discovered=hot	Dequeue hit (chain length 1): one-letter neighbours not seen before: hot.
3	L13	u=hot chain length=2 discovered=dot lot	Dequeue hot (chain length 2): one-letter neighbours not seen before: dot, lot.
4	L13	u=dot chain length=3 discovered=dog	Dequeue dot (chain length 3): one-letter neighbours not seen before: dog.
5	L13	u=lot chain length=3 discovered=log	Dequeue lot (chain length 3): one-letter neighbours not seen before: log.
6	L13	u=dog chain length=4 discovered=cog	Dequeue dog (chain length 4): one-letter neighbours not seen before: cog.
7	L13	u=log chain length=4 discovered=none	Dequeue log (chain length 4): no unseen one-letter neighbour in the list.
8	L6	return=5	cog dequeued with 5 words in the chain: the shortest transformation has 5 words (4 changes).

33.07.3

Lock puzzle

A **combination lock** has digit wheels. One move turns one wheel up or down by one, and 9 wraps to 0 and back. The state is the whole digit string, so with k wheels there are 10^k states and each has 2k neighbours. Some states are **dead ends** that the lock refuses; they are simply never entered (and if the start is one, there is no solution).

Marking a dead end as already visited is the neat way to forbid it. The animation's lock presets use two wheels; the dead-end preset forces a longer route around the blocked states.

Java

1static int lockMoves(String start, String target, Set<String> dead) {   // fewest wheel turns, or -1
2    if (dead.contains(start)) return -1;
3    Set<String> seen = new HashSet<>(dead);                            // dead ends count as already visited
4    Deque<String> queue = new ArrayDeque<>();
5    Map<String, Integer> dist = new HashMap<>();
6    seen.add(start);
7    dist.put(start, 0);
8    queue.add(start);
9    while (!queue.isEmpty()) {
10        String s = queue.poll();
11        if (s.equals(target)) return dist.get(s);
12        for (int i = 0; i < s.length(); i++)
13            for (int turn : new int[]{1, 9}) {                         // +1 and -1 (mod 10)
14                char[] cs = s.toCharArray();
15                cs[i] = (char) ('0' + (cs[i] - '0' + turn) % 10);
16                String nb = new String(cs);
17                if (seen.add(nb)) { dist.put(nb, dist.get(s) + 1); queue.add(nb); }
18            }
19    }
20    return -1;
21}

BFS on implicit graphs: word ladder, lock, switch configurations

Interactive · edit the input

word graph (edges appear when the search examines them) · 7 vertices · 0 edges

hit

hot

dot

dog

lot

log

cog

Being expandedDiscoveredVisitedTarget / on the answerDead end

queue

hit

Setup

Step 1 / 8

Java

1int ladderLength(String begin, String end, Set<String> words) {   // number of words in the shortest chain
2    Deque<String> q = new ArrayDeque<>(); Map<String, Integer> dist = new HashMap<>();
3    q.add(begin); dist.put(begin, 1);
4    while (!q.isEmpty()) {
5        String u = q.poll();
6        if (u.equals(end)) return dist.get(u);
7        char[] c = u.toCharArray();
8        for (int i = 0; i < c.length; i++) {
9            char keep = c[i];
10            for (char x = 'a'; x <= 'z'; x++) {  // neighbours are generated, never stored
11                c[i] = x;
12                String v = new String(c);
13                if (words.contains(v) && !dist.containsKey(v)) { dist.put(v, dist.get(u) + 1); q.add(v); }
14            }
15            c[i] = keep;
16        }
17    }
18    return 0;
19}
20int openLock(Set<String> dead, String start, String target) {     // a lock of any number of wheels
21    if (dead.contains(start)) return -1;
22    Deque<String> q = new ArrayDeque<>(); Set<String> seen = new HashSet<>();
23    q.add(start); seen.add(start);
24    for (int turns = 0; !q.isEmpty(); turns++) {          // one iteration per BFS level
25        for (int k = q.size(); k > 0; k--) {
26            String u = q.poll();
27            if (u.equals(target)) return turns;
28            for (int i = 0; i < u.length(); i++)
29                for (int d : new int[]{1, 9}) {           // turn one wheel up or down
30                    char[] c = u.toCharArray();
31                    c[i] = (char) ('0' + (c[i] - '0' + d) % 10);
32                    String v = new String(c);
33                    if (!dead.contains(v) && seen.add(v)) q.add(v);
34                }
35        }
36    }
37    return -1;
38}
39int minPresses(int start, int n) {               // bits as an int; pressing bit i flips i-1, i, i+1
40    int[] dist = new int[1 << n]; Arrays.fill(dist, -1);
41    Deque<Integer> q = new ArrayDeque<>(); q.add(start); dist[start] = 0;
42    while (!q.isEmpty()) {
43        int u = q.poll();
44        if (u == 0) return dist[u];
45        for (int i = 0; i < n; i++) {
46            int mask = (1 << i) | (i > 0 ? 1 << (i - 1) : 0) | (i + 1 < n ? 1 << (i + 1) : 0);
47            int v = u ^ mask;
48            if (dist[v] == -1) { dist[v] = dist[u] + 1; q.add(v); }
49        }
50    }
51    return -1;
52}

Live state

0 states visited

begin

hit

end

cog

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L3	begin=hit end=cog	Words are vertices; two words are neighbours when they differ in exactly one letter and the next word is in the list. No edge list is built: the neighbours of a word are generated by changing one letter at a time. Count the words in the chain, so hit counts as 1.
2	L13	u=hit chain length=1 discovered=hot	Dequeue hit (chain length 1): one-letter neighbours not seen before: hot.
3	L13	u=hot chain length=2 discovered=dot lot	Dequeue hot (chain length 2): one-letter neighbours not seen before: dot, lot.
4	L13	u=dot chain length=3 discovered=dog	Dequeue dot (chain length 3): one-letter neighbours not seen before: dog.
5	L13	u=lot chain length=3 discovered=log	Dequeue lot (chain length 3): one-letter neighbours not seen before: log.
6	L13	u=dog chain length=4 discovered=cog	Dequeue dog (chain length 4): one-letter neighbours not seen before: cog.
7	L13	u=log chain length=4 discovered=none	Dequeue log (chain length 4): no unseen one-letter neighbour in the list.
8	L6	return=5	cog dequeued with 5 words in the chain: the shortest transformation has 5 words (4 changes).

33.07.4

Grid movement

On a grid the neighbours of cell (r, c) are (r + dr, c + dc) for each pair in a **direction array**: four pairs for up, down, left and right, eight if diagonals are allowed. Each neighbour must be checked to lie inside the grid and not be a wall before it is used. Everything else is ordinary BFS, with the distance stored per cell.

Because all moves cost 1, BFS gives the shortest path. If a move can cost more, such as mud or stairs, BFS no longer applies and you need Dijkstra. The BFS-on-a-grid animation shows the queue of cells and the distance field.

Java

1static int shortestInGrid(boolean[][] open, int sr, int sc, int tr, int tc, int[][] dirs) {   // moves, or -1
2    int rows = open.length, cols = open[0].length;
3    if (!open[sr][sc] || !open[tr][tc]) return -1;
4    int[][] dist = new int[rows][cols];
5    for (int[] row : dist) Arrays.fill(row, -1);
6    Deque<int[]> queue = new ArrayDeque<>();
7    dist[sr][sc] = 0;
8    queue.add(new int[]{sr, sc});
9    while (!queue.isEmpty()) {
10        int[] cell = queue.poll();
11        if (cell[0] == tr && cell[1] == tc) return dist[tr][tc];
12        for (int[] d : dirs) {
13            int nr = cell[0] + d[0], nc = cell[1] + d[1];
14            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;      // off the grid
15            if (!open[nr][nc] || dist[nr][nc] != -1) continue;               // wall or already reached
16            dist[nr][nc] = dist[cell[0]][cell[1]] + 1;
17            queue.add(new int[]{nr, nc});
18        }
19    }
20    return -1;
21}

BFS on a grid: shortest path and multi-source distances

Interactive · edit the input

grid · 3 × 5

01234

▇

Cell being expandedReached (distance shown)WallSource

queue (front first)

(0,0)

Setup

Start at the top-left cell with distance 0.

Step 1 / 14

Java

1static int shortestPath(int[][] g) {                     // 4-directional moves, 0 = wall
2    int R = g.length, C = g[0].length;
3    int[][] dist = new int[R][C]; for (int[] row : dist) Arrays.fill(row, -1);
4    Deque<int[]> queue = new ArrayDeque<>();
5    // single source: (0, 0); multi-source: every cell equal to 2, all at distance 0
6    dist[0][0] = 0; queue.offer(new int[]{0, 0});
7    while (!queue.isEmpty()) {
8        int[] cur = queue.poll();
9        for (int[] d : new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}) {
10            int r = cur[0] + d[0], c = cur[1] + d[1];
11            if (r < 0 || r >= R || c < 0 || c >= C || g[r][c] == 0 || dist[r][c] != -1) continue;
12            dist[r][c] = dist[cur[0]][cur[1]] + 1;           // first arrival is the shortest, because BFS goes level by level
13            queue.offer(new int[]{r, c});
14        }
15    }
16    return dist[R - 1][C - 1];                               // -1 when unreachable; multi-source: max over all cells
17}

Live state

sources

No condition evaluated on this step

Execution trace (dry run table)Show 14 steps

Step	Line	State	What happens
1	L5	sources=1	Start at the top-left cell with distance 0.
2	L12	cell=(0,0) dist=0	Expand (0,0) at distance 0: reached (0,1)=1.
3	L12	cell=(0,1) dist=1	Expand (0,1) at distance 1: reached (1,1)=2.
4	L12	cell=(1,1) dist=2	Expand (1,1) at distance 2: reached (1,2)=3, (2,1)=3.
5	L12	cell=(1,2) dist=3	Expand (1,2) at distance 3: reached (1,3)=4, (2,2)=4.
6	L12	cell=(2,1) dist=3	Expand (2,1): every open neighbour is already reached or blocked.
7	L12	cell=(1,3) dist=4	Expand (1,3) at distance 4: reached (0,3)=5, (1,4)=5, (2,3)=5.
8	L12	cell=(2,2) dist=4	Expand (2,2): every open neighbour is already reached or blocked.
9	L12	cell=(0,3) dist=5	Expand (0,3) at distance 5: reached (0,4)=6.
10	L12	cell=(1,4) dist=5	Expand (1,4) at distance 5: reached (2,4)=6.
11	L12	cell=(2,3) dist=5	Expand (2,3): every open neighbour is already reached or blocked.
12	L12	cell=(0,4) dist=6	Expand (0,4): every open neighbour is already reached or blocked.
13	L12	cell=(2,4) dist=6	Expand (2,4): every open neighbour is already reached or blocked.
14	L16	return=6	The bottom-right cell is 6 steps away, the minimum, because BFS reaches cells in order of distance.

33.07.5

0/1 configuration states

When a state is a row of on/off flags, store it as the bits of an integer: n switches give 2^n states, small enough to keep a distance array indexed by the mask. A move is then an XOR with a mask. In the animation's **switch puzzle**, pressing switch i flips it and its neighbours on both sides, and the aim is to reach all switches off.

The neighbour of state s through press i is s ^ press[i], where press[i] has the bits of the switch and its neighbours set. This turns a puzzle with 16 states into a graph with 16 vertices, and a BFS gives the fewest presses or reports that the pattern cannot be solved.

Java

1static int minPresses(int n, int start) {                         // fewest presses to reach 0, or -1; bit i is switch i
2    int[] press = new int[n];
3    for (int i = 0; i < n; i++) {
4        press[i] = 1 << i;
5        if (i > 0) press[i] |= 1 << (i - 1);
6        if (i + 1 < n) press[i] |= 1 << (i + 1);
7    }
8    int[] dist = new int[1 << n];
9    Arrays.fill(dist, -1);
10    Deque<Integer> queue = new ArrayDeque<>();
11    dist[start] = 0;
12    queue.add(start);
13    while (!queue.isEmpty()) {
14        int s = queue.poll();
15        if (s == 0) return dist[s];
16        for (int i = 0; i < n; i++) {
17            int nb = s ^ press[i];
18            if (dist[nb] == -1) { dist[nb] = dist[s] + 1; queue.add(nb); }
19        }
20    }
21    return -1;
22}

BFS on implicit graphs: word ladder, lock, switch configurations

Interactive · edit the input

word graph (edges appear when the search examines them) · 7 vertices · 0 edges

hit

hot

dot

dog

lot

log

cog

Being expandedDiscoveredVisitedTarget / on the answerDead end

queue

hit

Setup

Step 1 / 8

Java

1int ladderLength(String begin, String end, Set<String> words) {   // number of words in the shortest chain
2    Deque<String> q = new ArrayDeque<>(); Map<String, Integer> dist = new HashMap<>();
3    q.add(begin); dist.put(begin, 1);
4    while (!q.isEmpty()) {
5        String u = q.poll();
6        if (u.equals(end)) return dist.get(u);
7        char[] c = u.toCharArray();
8        for (int i = 0; i < c.length; i++) {
9            char keep = c[i];
10            for (char x = 'a'; x <= 'z'; x++) {  // neighbours are generated, never stored
11                c[i] = x;
12                String v = new String(c);
13                if (words.contains(v) && !dist.containsKey(v)) { dist.put(v, dist.get(u) + 1); q.add(v); }
14            }
15            c[i] = keep;
16        }
17    }
18    return 0;
19}
20int openLock(Set<String> dead, String start, String target) {     // a lock of any number of wheels
21    if (dead.contains(start)) return -1;
22    Deque<String> q = new ArrayDeque<>(); Set<String> seen = new HashSet<>();
23    q.add(start); seen.add(start);
24    for (int turns = 0; !q.isEmpty(); turns++) {          // one iteration per BFS level
25        for (int k = q.size(); k > 0; k--) {
26            String u = q.poll();
27            if (u.equals(target)) return turns;
28            for (int i = 0; i < u.length(); i++)
29                for (int d : new int[]{1, 9}) {           // turn one wheel up or down
30                    char[] c = u.toCharArray();
31                    c[i] = (char) ('0' + (c[i] - '0' + d) % 10);
32                    String v = new String(c);
33                    if (!dead.contains(v) && seen.add(v)) q.add(v);
34                }
35        }
36    }
37    return -1;
38}
39int minPresses(int start, int n) {               // bits as an int; pressing bit i flips i-1, i, i+1
40    int[] dist = new int[1 << n]; Arrays.fill(dist, -1);
41    Deque<Integer> q = new ArrayDeque<>(); q.add(start); dist[start] = 0;
42    while (!q.isEmpty()) {
43        int u = q.poll();
44        if (u == 0) return dist[u];
45        for (int i = 0; i < n; i++) {
46            int mask = (1 << i) | (i > 0 ? 1 << (i - 1) : 0) | (i + 1 < n ? 1 << (i + 1) : 0);
47            int v = u ^ mask;
48            if (dist[v] == -1) { dist[v] = dist[u] + 1; q.add(v); }
49        }
50    }
51    return -1;
52}

Live state

0 states visited

begin

hit

end

cog

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L3	begin=hit end=cog	Words are vertices; two words are neighbours when they differ in exactly one letter and the next word is in the list. No edge list is built: the neighbours of a word are generated by changing one letter at a time. Count the words in the chain, so hit counts as 1.
2	L13	u=hit chain length=1 discovered=hot	Dequeue hit (chain length 1): one-letter neighbours not seen before: hot.
3	L13	u=hot chain length=2 discovered=dot lot	Dequeue hot (chain length 2): one-letter neighbours not seen before: dot, lot.
4	L13	u=dot chain length=3 discovered=dog	Dequeue dot (chain length 3): one-letter neighbours not seen before: dog.
5	L13	u=lot chain length=3 discovered=log	Dequeue lot (chain length 3): one-letter neighbours not seen before: log.
6	L13	u=dog chain length=4 discovered=cog	Dequeue dog (chain length 4): one-letter neighbours not seen before: cog.
7	L13	u=log chain length=4 discovered=none	Dequeue log (chain length 4): no unseen one-letter neighbour in the list.
8	L6	return=5	cog dequeued with 5 words in the chain: the shortest transformation has 5 words (4 changes).

Practice ladder

Now try it yourself

Easy

Find if Path Exists in Graph

Medium

Word Ladder
Open the Lock
Minimum Genetic Mutation
Shortest Path in Binary Matrix

Advanced

Word Ladder II
Sliding Puzzle
Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

Key takeaways

A puzzle is an implicit graph: states are vertices and moves are edges; BFS over states gives the fewest moves.
A hash map or array of distances replaces the visited set; dead ends are just visited states.
Check bounds and walls for every grid neighbour; BFS shortest paths need equal move costs.
Encode on/off states as bitmasks and moves as XOR.