Do you have to build a sliding-tile puzzle's state graph before you can search it?

## The state space is a graph you never see The hardest step in a modeling interview is not the traversal — it is recognizing that a problem with no obvious network in it is still a graph. The recognition test has three parts: - Is there a **situation** you can describe completely and compare for equality? That is a node. - Is there an **atomic legal action** that turns one situation into another? That is an edge. - Is there a **target situation**, or a property a situation must have? That is the goal test. A sliding-tile board passes all three. The situation is the full arrangement of tiles including where the blank sits. The action is sliding one tile into the blank — equivalently, moving the blank one square. The target is the ordered arrangement. That is a graph, and everything a graph algorithm can do applies to it, without a single stored edge. ## Why nobody builds it The branching factor is small: the blank has 2 legal moves from a corner, 3 from an edge square, 4 from the middle. But the node count is brutal. A 3-by-3 board has 9! = 362,880 arrangements. From any given start, exactly 181,440 of them are reachable — the permutation parity of the tiles combined with the blank's position is invariant under legal moves, so the space splits into two components that never meet. This is why a scrambled puzzle can be provably unsolvable rather than merely hard. A 4-by-4 board has 16!/2 ≈ 10^13 reachable arrangements. No machine builds that. Yet a search from a start eight moves from the goal expands only a few thousand nodes. That gap — between the size of the space and the size of the explored region — is the entire argument for implicit graphs. **Materializing costs you the whole space; generating on demand costs you only what you touch.** ## The successor routine is the graph In place of stored adjacency you carry three things: a start state, a successor routine, and a goal test. Anything else that a stored graph would give you has to be recovered another way. Two consequences worth stating in an interview: - **You cannot enumerate all nodes cheaply.** Algorithms that begin "for every node in the graph" — computing a global property, iterating to find unvisited components — do not transfer. Implicit-graph work is reachability work from a known start. - **You cannot cheaply ask "is X adjacent to Y?"** in general; you generate X's neighbors and look. For most searches that is all you ever needed. ## When materializing does pay The on-demand answer is not universal, and a good candidate says where it flips. Consider a four-wheel dial mechanism where a reading is four digits and one click of one wheel is an edge. That space is exactly 10^4 = 10,000 readings, each with 8 neighbors — one click up or down on each of four wheels, wrapping at the ends. Building it is trivial and finishes in milliseconds. If a service answers thousands of queries a day against the same fixed dial and the same fixed set of unusable readings, one build amortizes across all of them and every query becomes a lookup. For a single one-off query, the generator is simpler, allocates nothing, and touches only the readings the search actually reaches. The decision rule that falls out: **materialize when the space is small, fixed, and traversed repeatedly; generate when it is large, sparsely explored, or defined by rules that change per request.** The size of the state space relative to the explored region is the number that decides it, not taste. ## Where unusable states live If certain arrangements are forbidden — a jammed wheel position, a shelf under maintenance — the natural home is the successor routine: it simply does not emit them, so they are not nodes. Seeding them into the visited set instead is a common shortcut that usually behaves identically, but it conflates "cannot exist" with "already explored", and it has one real bug: if the start itself is forbidden, the shortcut quietly reports no solution for the wrong reason. ## The sentence to have ready "A node is a whole board arrangement, an edge is one legal slide, and the graph is the move rule — so I search from the start and generate neighbors as I go, because the space is 181,440 reachable arrangements on a 3-by-3 board and about 10^13 on a 4-by-4." That answer shows the modeling, the cost awareness, and the reason for the choice, in one breath.