State-space graph modelling and sparsification

Many problems do not mention graphs at all. You see a puzzle, a puzzle-like constraint, or a counting problem. But underneath, a state graph is hiding. Each unique configuration is a node. Each legal move or transition is an edge. The problem asks for the shortest path, the minimum cost, or simply whether one state can reach another.

The trouble is that the full state graph is often huge. A puzzle with 10 positions and 4 possible values per position has $4^{10}$ states. A movement problem on a $100 \times 100$ grid where you collect items from $2^{20}$ different subsets creates an even larger graph. You cannot build it all.

You do not need to. Search only from the start, add only the edges that connect a state you might actually visit, and keep only the distances you need. This is called sparsification: you search a tiny fraction of the full state graph, and it is enough.

What is a state?

A state is a snapshot of the configuration at one moment. In a puzzle, a state might be the positions of all pieces. In a navigation problem, a state is your location plus anything you have collected. In a number transformation puzzle, a state is the current number.

Two states are the same if and only if all their components match. State A and state B are different if even one component differs.

An example: moving through rooms

Imagine a warehouse with three rooms connected by corridors. You start in room A and want to reach room C. Each room has a cost to enter: room A costs 0 (you start there), room B costs 5, and room C costs 3. You can move from A to B, from B to C, and from C back to B (the corridors are bidirectional).

A simple shortest-path search from A to C takes you A to B (cost 5) to C (cost 3 + 5 = 8).

Now extend the problem. The warehouse has items in each room. You want to visit some set of items with minimum total cost. If you must collect the item in room C but not the item in room B, then room B's cost is wasted unless you pass through it to reach C. But if you must collect items in both B and C, then you go A to B to C.

In this version, a state is a pair: (which room you are in, which items you have collected). The start state is (A, no items). A goal state is (any room, all required items collected). Transitions are moves between rooms. Each transition has a cost: the cost to enter the destination room.

If you must collect 3 items in different rooms, there are $3 \times 2^3 = 24$ possible states: 3 possible rooms, and each of 8 subsets of items. Not all 24 are reachable from the start. If the start room is A and you can only collect from B and C, then you will never have an item from A in your collected set. You will visit only about 9 reachable states. The full state graph has 24 states; the reachable subgraph has about 9.

Building the graph on the fly

You do not write down the entire state graph. Instead, you build it as you search.

1. Start with the initial state. Set its distance to 0.
2. Use a priority queue (a min-heap) to process states in order of increasing distance.
3. Pop the state with the smallest distance. For each outgoing edge, compute the next state and its distance. If it is a new state or you have found a shorter path to it, add it to the queue.
4. Stop when you pop the goal state, or when the queue is empty.

This is Dijkstra's algorithm applied to the state graph.

An example: collecting checkpoints

You are navigating a graph of 4 rooms: A, B, C, D. The edges and costs are:

• A to B: cost 2
• B to C: cost 3
• A to D: cost 1
• D to C: cost 2

You start in A and must visit both B and C (in any order). Your state is (current room, set of checkpoints visited). The start state is (A, ).

1import heapq2import sys3
4
5def main() -> None:6    input_data = sys.stdin.read().split()7    if not input_data:8        return9
10    idx = 011    n_rooms = int(input_data[idx])12    n_edges = int(input_data[idx + 1])13    n_checkpoints = int(input_data[idx + 2])14    idx += 315
16    # Build adjacency list17    adj = [[] for _ in range(n_rooms)]18    for _ in range(n_edges):19        u = int(input_data[idx])20        v = int(input_data[idx + 1])21        cost = int(input_data[idx + 2])22        idx += 323        adj[u].append((v, cost))24        adj[v].append((u, cost))25
26    # Read checkpoints to collect27    checkpoints = []28    for _ in range(n_checkpoints):29        checkpoints.append(int(input_data[idx]))30        idx += 131
32    checkpoint_set = frozenset(checkpoints)33    start_state = (0, frozenset())34    best = {}35
36    pq = [(0, start_state)]37    while pq:38        dist, state = heapq.heappop(pq)39        room, collected = state40
41        if state in best:42            continue43        best[state] = dist44
45        if collected == checkpoint_set:46            sys.stdout.write(str(dist) + "\n")47            return48
49        for next_room, cost in adj[room]:50            new_collected = collected | (51                frozenset([next_room])52                if next_room in checkpoints53                else frozenset()54            )55            next_state = (next_room, new_collected)56            next_dist = dist + cost57
58            if next_state not in best:59                heapq.heappush(pq, (next_dist, next_state))60
61    sys.stdout.write("-1\n")62
63
64if __name__ == "__main__":65    main()

4 4 2
0 1 2
1 2 3
0 3 1
3 2 2
1 2

5

The program uses a tuple (room, frozenset(checkpoints)) to represent each state. The distance from A to B is 2, then from B to C is 3, for a total of 5. But the path A to D to C is 1 + 2 = 3, then back from C to B is 3, for a total of 6. So the better order is B then C: total distance 5.

Common mistakes

One mistake is to represent a state inefficiently. If you use a string or a sorted list of items, the hashing and comparison take time. Use a frozenset for unordered collections or a tuple of integers for bit-packed sets. If states are represented poorly, the search becomes slow even though the number of reachable states is small.

Another mistake is to forget that you are searching a sparse graph. You may compute the full state graph in your head: "there are $2^{20}$ possible item subsets". But if your start state can only reach a tiny fraction of them, you will never compute the others. Count the states you actually explore, not the theoretical maximum. If the search is too slow, the issue is your state encoding or your pruning, not the full graph size.

A third mistake is to re-explore the same state from different paths. Once you have found the shortest path to a state, do not process it again. Use a seen set to track distances you have already computed. If a new path arrives with a longer distance, skip it.

Recap

State-space modelling turns a puzzle or configuration problem into a shortest-path search. A state encodes the full configuration at one moment. The graph has one edge per legal transition. You build the graph on the fly using Dijkstra's algorithm, exploring only the reachable states. The key is recognizing which component of the problem should be part of the state, so that your state space is small enough to search.