Search over states: position plus extra state

intermediateCommon atGoogleMetaAmazonRead firstBreadth-first searchShortest pathsBit manipulationPractise in the Sandbox →

Graph search works on any state graph: a node is “everything that affects what you can do next”, an edge is one legal move. When position alone isn’t enough (you also carry keys, have some budget left, face a direction, have used some fuel), the node becomes a tuple like (row, col, keys), and the visited set must be keyed by the whole tuple. Run BFS (or Dijkstra) as usual; the cost is the number of states, e.g. O(R · C · 2ᵏ) for k keys.

The idea in plain words

Picture a maze with a locked door and a key in a side corridor. You walk to the key, then walk back the way you came, through the door. Plain grid BFS can’t find that route: it marks the corridor cells visited on the way in and refuses to walk them again.

But you weren’t the same “you” on the way back. You were holding a key. Standing at cell (2, 1) without the key and standing there with it are two different situations, with different futures. Treat them as different nodes.

That’s the whole technique:

1. Define the state: the smallest tuple that fully determines which moves are possible from here and what they cost.
2. Search the state graph: BFS if every move costs the same, Dijkstra if not.
3. Key the visited set (or distance map) by the full state.

A useful picture: the grid is copied once per value of the extra state, and you’re searching a stack of layers. Picking up a key moves you to a different layer.

See it

Step through the corridor maze. Each mini-grid is one layer of the visited set: the cells reached while holding a particular set of keys. Picking up key a jumps the search into the {a} layer, where the corridor is fresh again. Then switch the visited set to cell only and watch the search get stuck right after grabbing the key.

The visited set grows a dimension

click to edit, then step

CorridorRooms

layer: holding keys { }

a

b

0

A

B

E

layer: holding keys {a}

a

b

S

A

B

E

layer: holding keys {b}

a

b

S

A

B

E

layer: holding keys {a, b}

a

b

S

A

B

E

queue, 1 states

(2,0) { }

states seen1

upper bound3·9·2² = 108

queue1

current state / final routejust discoveredin the queuevisited in this layer

A state is (row, col, keys held). Two visits to the same cell with different keys are different states, so the visited set has one layer per key set.

↺◀▶ Play▶1 / 21

Edit the grid: place a key behind its own door, or move E. The counter shows the upper bound on states, R · C · 2²: the search space has 4 times as many nodes as the grid.

When to reach for it

The problem says…	Extra state	Why
“collect keys / items; doors need keys”	bitmask of items held	What you hold changes which moves are legal.
“you may break / skip / remove up to k obstacles”	remaining budget (0..k)	Same cell with more budget left has more options.
“turning costs extra”, “momentum”, “can’t reverse”	facing direction	The cost of the next move depends on the last one.
“visit all of these special nodes” (small count)	bitmask of visited targets	Classic shortest Hamiltonian-style search over ≤ ~15 targets.
puzzles: sliding tiles, water jugs, lock wheels	the whole configuration	There is no “position”: the state is the configuration.
“the tank holds f units of fuel”	fuel left	The resource limits future moves.
“two robots / players move together”	both positions	The pair is the state.

How it works

1. Choose the state. List everything that affects legal moves or their cost. Drop anything derivable from the rest.
2. Bound the state space. Multiply the ranges: R · C · 2ᵏ, or (A + 1)(B + 1) jug amounts. If it’s too big, find redundant parts to drop.
3. Generate transitions. From a state, produce every legal next state. Moves that change the extra state (picking up a key) are just edges between layers.
4. Search with visited keyed by the full state. Return when a state satisfies the goal test, which often looks only at part of the state (any keys, at the exit).

The state doesn’t have to include a position at all. Two jugs of 3 and 5 litres, and you want exactly 4: the state is the pair of amounts, and every fill, empty or pour is an edge.

Python

jug_steps.py

from collections import deque


def jug_steps(cap_a: int, cap_b: int, target: int) -> int:
    """Fewest fill/empty/pour moves until either jug holds exactly target litres, or -1."""
    start = (0, 0)                         # 1. a state is the pair of amounts, not a position
    dist = {start: 0}
    queue = deque([start])
    while queue:
        a, b = queue.popleft()
        if target in (a, b):
            return dist[(a, b)]
        pour_ab = min(a, cap_b - b)        # how much fits when pouring A into B
        pour_ba = min(b, cap_a - a)
        for nxt in [(cap_a, b), (a, cap_b), (0, b), (a, 0),       # 2. every legal move
                    (a - pour_ab, b + pour_ab), (a + pour_ba, b - pour_ba)]:
            if nxt not in dist:            # 3. visited set over STATES: at most (A+1)(B+1)
                dist[nxt] = dist[(a, b)] + 1
                queue.append(nxt)
    return -1                              # 4. every reachable state tried


if __name__ == "__main__":
    assert jug_steps(3, 5, 4) == 6         # the Die Hard 3 puzzle
    assert jug_steps(2, 6, 5) == -1        # gcd(2, 6) = 2 never divides 5
    assert jug_steps(4, 9, 0) == 0
    print("ok")

TypeScript

jug_steps.ts

import assert from "node:assert/strict";

/** Fewest fill/empty/pour moves until either jug holds exactly target litres, or -1. */
export function jugSteps(capA: number, capB: number, target: number): number {
  const key = (a: number, b: number) => a * (capB + 1) + b; // encode the pair as one number
  const dist = new Map<number, number>([[key(0, 0), 0]]); // 1. a state is the pair of amounts
  const queue: [number, number][] = [[0, 0]];
  for (let head = 0; head < queue.length; head++) {
    const [a, b] = queue[head];
    const d = dist.get(key(a, b))!;
    if (a === target || b === target) return d;
    const ab = Math.min(a, capB - b), ba = Math.min(b, capA - a);
    const moves: [number, number][] = [[capA, b], [a, capB], [0, b], [a, 0], [a - ab, b + ab], [a + ba, b - ba]]; // 2.
    for (const [na, nb] of moves) {
      if (!dist.has(key(na, nb))) { // 3. visited set over STATES: at most (A+1)(B+1)
        dist.set(key(na, nb), d + 1);
        queue.push([na, nb]);
      }
    }
  }
  return -1; // 4. every reachable state tried
}

assert.equal(jugSteps(3, 5, 4), 6); // the Die Hard 3 puzzle
assert.equal(jugSteps(2, 6, 5), -1); // gcd(2, 6) = 2 never divides 5
assert.equal(jugSteps(4, 9, 0), 0);
console.log("ok");

C#

jug_steps.cs

if (JugSteps(3, 5, 4) != 6) throw new Exception("Die Hard 3 puzzle");
if (JugSteps(2, 6, 5) != -1) throw new Exception("impossible case");
if (JugSteps(4, 9, 0) != 0) throw new Exception("already done");
Console.WriteLine("ok");

// Fewest fill/empty/pour moves until either jug holds exactly target litres, or -1.
static int JugSteps(int capA, int capB, int target)
{
    var dist = new Dictionary<(int A, int B), int> { [(0, 0)] = 0 };   // 1. state = pair of amounts
    var queue = new Queue<(int A, int B)>([(0, 0)]);
    while (queue.Count > 0)
    {
        var (a, b) = queue.Dequeue();
        int d = dist[(a, b)];
        if (a == target || b == target) return d;
        int ab = Math.Min(a, capB - b), ba = Math.Min(b, capA - a);
        (int, int)[] moves = [(capA, b), (a, capB), (0, b), (a, 0), (a - ab, b + ab), (a + ba, b - ba)]; // 2.
        foreach (var next in moves)
            if (dist.TryAdd(next, d + 1)) queue.Enqueue(next);           // 3. visited over STATES
    }
    return -1;                                                           // 4. all states tried
}

With a position, the extra state rides along in the tuple. Keys go in a bitmask: bit i set means key i is held, and picking one up is keys | (1 << i).

Python

fewest_moves.py

from collections import deque


def fewest_moves(grid: list[str]) -> int:
    """S to E in a grid with walls '#', keys 'a'-'d' and doors 'A'-'D'. A door needs its key."""
    rows, cols = len(grid), len(grid[0])
    sr, sc = next((r, c) for r in range(rows) for c in range(cols) if grid[r][c] == "S")
    start = (sr, sc, 0)                    # 1. state = (row, col, bitmask of keys held)
    seen = {start}
    queue = deque([(start, 0)])
    while queue:
        (r, c, keys), d = queue.popleft()
        if grid[r][c] == "E":
            return d
        for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
            if not (0 <= nr < rows and 0 <= nc < cols) or grid[nr][nc] == "#":
                continue
            ch, nk = grid[nr][nc], keys
            if "A" <= ch <= "D" and not keys >> (ord(ch) - ord("A")) & 1:
                continue                   # 2. locked door: this move doesn't exist yet
            if "a" <= ch <= "d":
                nk |= 1 << (ord(ch) - ord("a"))   # 3. picking up a key changes the state
            if (nr, nc, nk) not in seen:   # 4. same cell + different keys = new state
                seen.add((nr, nc, nk))
                queue.append(((nr, nc, nk), d + 1))
    return -1


if __name__ == "__main__":
    corridor = ["#a####b##",
                "#.####.##",
                "S...A..BE"]
    assert fewest_moves(corridor) == 16    # detour up for each key, then back down
    assert fewest_moves(["SA.E", "####"]) == -1
    print("ok")

TypeScript

fewest_moves.ts

import assert from "node:assert/strict";

/** S to E in a grid with walls '#', keys 'a'-'d' and doors 'A'-'D'. A door needs its key. */
export function fewestMoves(grid: string[]): number {
  const rows = grid.length, cols = grid[0].length;
  let sr = 0, sc = 0;
  grid.forEach((row, r) => { const c = row.indexOf("S"); if (c >= 0) { sr = r; sc = c; } });
  const id = (r: number, c: number, k: number) => (r * cols + c) * 16 + k; // 1. (row, col, keys) as one int
  const seen = new Set([id(sr, sc, 0)]);
  const queue: [number, number, number, number][] = [[sr, sc, 0, 0]];
  for (let head = 0; head < queue.length; head++) {
    const [r, c, keys, d] = queue[head];
    if (grid[r][c] === "E") return d;
    for (const [nr, nc] of [[r - 1, c], [r + 1, c], [r, c - 1], [r, c + 1]]) {
      if (nr < 0 || nc < 0 || nr >= rows || nc >= cols || grid[nr][nc] === "#") continue;
      const ch = grid[nr][nc];
      let nk = keys;
      if (ch >= "A" && ch <= "D" && !((keys >> (ch.charCodeAt(0) - 65)) & 1)) continue; // 2. locked door
      if (ch >= "a" && ch <= "d") nk |= 1 << (ch.charCodeAt(0) - 97); // 3. a key changes the state
      if (!seen.has(id(nr, nc, nk))) { // 4. same cell + different keys = new state
        seen.add(id(nr, nc, nk));
        queue.push([nr, nc, nk, d + 1]);
      }
    }
  }
  return -1;
}

const corridor = ["#a####b##", "#.####.##", "S...A..BE"];
assert.equal(fewestMoves(corridor), 16); // detour up for each key, then back down
assert.equal(fewestMoves(["SA.E", "####"]), -1);
console.log("ok");

C#

fewest_moves.cs

string[] corridor = ["#a####b##", "#.####.##", "S...A..BE"];
if (FewestMoves(corridor) != 16) throw new Exception("corridor");   // a detour up for each key
if (FewestMoves(["SA.E", "####"]) != -1) throw new Exception("locked");
Console.WriteLine("ok");

// S to E in a grid with walls '#', keys 'a'-'d' and doors 'A'-'D'. A door needs its key.
static int FewestMoves(string[] grid)
{
    int rows = grid.Length, cols = grid[0].Length;
    var start = Enumerable.Range(0, rows).SelectMany(r => Enumerable.Range(0, cols).Select(c => (R: r, C: c, Keys: 0)))
        .First(s => grid[s.R][s.C] == 'S');                             // 1. state = (row, col, keys)
    var seen = new HashSet<(int, int, int)> { start };
    var queue = new Queue<((int R, int C, int Keys) S, int D)>([(start, 0)]);
    while (queue.Count > 0)
    {
        var ((r, c, keys), d) = queue.Dequeue();
        if (grid[r][c] == 'E') return d;
        foreach (var (nr, nc) in new[] { (r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1) })
        {
            if (nr < 0 || nc < 0 || nr >= rows || nc >= cols || grid[nr][nc] == '#') continue;
            char ch = grid[nr][nc];
            int nk = keys;
            if (ch is >= 'A' and <= 'D' && ((keys >> (ch - 'A')) & 1) == 0) continue; // 2. locked door
            if (ch is >= 'a' and <= 'd') nk |= 1 << (ch - 'a');          // 3. a key changes the state
            if (seen.Add((nr, nc, nk))) queue.Enqueue(((nr, nc, nk), d + 1)); // 4. new state?
        }
    }
    return -1;
}

Encoding states

Tuples work as dict/set keys in Python. In C#, value tuples (int, int, int) hash correctly in HashSet. In TypeScript, a Set of arrays compares by reference, so encode the state as a string ("3,4,5") or, faster, a single integer like (r * cols + c) * 2^k + keys.

What it costs

State	Number of states	BFS time
(row, col)	R·C	O(R·C)
(row, col, k-bit key mask)	R·C·2ᵏ	O(R·C·2ᵏ)
(row, col, remaining budget 0..k)	R·C·(k + 1)	O(R·C·k)
(row, col, direction)	4·R·C	O(R·C)
(node, visited-targets mask) over m targets	V·2ᵐ	O(E·2ᵐ)

The rule is simple: time and memory are proportional to the number of reachable states times the moves per state. Before coding, multiply the ranges and check against the limits. 50 × 50 × 2⁶ = 160,000 states is fine. 50 × 50 × 2²⁰ ≈ 2.6 billion is not.

Variations you’ll meet

• Dominance pruning. For a budget, reaching a cell with more budget left dominates reaching it with less. Keep best_budget[r][c] and skip a state that’s no better. This shrinks the search below the full product.
• Weighted moves. Use Dijkstra over states (heap of (cost, state)), or 0-1 BFS when costs are 0 or 1.
• Bidirectional search for puzzles with a known goal configuration (sliding tiles).
• A* with a heuristic on the position part of the state.
• Implicit state graphs. Don’t build them. Generate neighbours on the fly, and only for states you actually pop.
• DP view. A state-space search over a DAG of states (when states only “increase”, like a growing mask) is dynamic programming; see DP over bitmasks.

Pitfalls

• Visited keyed by position only. The search gets stuck or returns a wrong answer, exactly as in the viz.
• State too big. Including derivable information (like the path so far, or the step count) multiplies states for nothing and can make every state unique.
• State too small. Leaving out something that affects future moves (direction when turning costs extra) gives wrong answers.
• Goal test on the full state when only part matters: “reach E with any keys” must not require a specific key set.
• Forgetting the start state’s extra parts, like a key lying on the start cell or an initial budget.
• Mutable state objects as keys (lists in Python, arrays in JS). Use tuples, strings or packed integers.

In the interview

• Say it explicitly: “Position alone isn’t enough, because holding a key changes which moves are legal. My state is (row, col, mask).”
• Bound it out loud: “R·C·2ᵏ states, each with 4 moves, so O(R·C·2ᵏ).” Check it against the constraints you were given.
• Point out which parts the goal test reads.
• Expected follow-ups: weights on moves (Dijkstra over states), many more keys (look for dominance or a different decomposition), return the actual route (parent map over states), or “now a budget instead of keys”.

Check yourself

Check yourself

pick one

On a grid, going straight is free but every 90° turn costs 1. What should a search node contain?

A(row, col): direction is just a detail of the pathB(row, col, facing): the cost of the next move depends on which way you faceC(row, col, number of turns so far)

Check yourself

pick one

A 20 × 20 grid has 10 different keys. How many (row, col, keys) states can there be?

A400B4,000CAbout 410,000DAbout 400 × 10!

Check yourself

pick one

Should the number of steps taken so far be part of the BFS state?

AYes, it affects the answerBNo: BFS already tracks distance, and adding it makes every visit a new state so nothing is ever prunedCOnly for weighted graphs

Practice on your own

These are classic textbook exercises, not gym questions:

• The 3- and 5-litre water jug puzzle: print the actual sequence of moves.
• Solve the 8-puzzle (3 × 3 sliding tiles) with BFS; count reachable configurations.
• Open a 4-wheel combination lock while avoiding a list of dead-end codes.
• Shortest path that visits every node of a small graph (n ≤ 12), starting anywhere.
• A knight on a chessboard that must also collect a coin before reaching the goal.

Go deeper

• Russell and Norvig, Artificial Intelligence: A Modern Approach, chapter 3 “Solving Problems by Searching”: states, actions, transition models and goal tests.
• cp-algorithms: 0-1 BFS, useful for state graphs with 0/1 costs.
• Red Blob Games: Introduction to A*, on graph search beyond grids.
• Skiena, The Algorithm Design Manual, “Combinatorial Search”: state-space size estimates and pruning.

Related

Breadth-first searchThe engine, unchanged: only the node type grows.

Shortest pathsDijkstra and 0-1 BFS over states when moves have costs.

Bit manipulationPacking a set of keys into an integer.

Dynamic programming: advancedBitmask DP, the same state space viewed as a recurrence.