Why does searching an implicit state graph need a visited set, and what should its key be?

## The graph has cycles, and it is your job to notice When edges are stored, the cycles are visible in the data. In an implicit graph the neighbor rule looks innocent, and people forget that it produces a graph rather than a tree. It almost always produces cycles, for one boring reason: **most modeled actions are reversible.** Step right, step left. Turn a dial wheel up, turn it back down. Slide a tile, slide it back. Every reversible action is a two-cycle, so a search with no memory can bounce between two states forever. Even with no literal loop, paths reconverge. Reaching cell `(5,5)` by going down-then-right and by going right-then-down produces the same state twice, and each duplicate goes on to re-expand the entire region beyond it. Without deduplication a search over a grid does work exponential in the depth explored; with it, the work is bounded by the number of reachable states. That is the difference between a hang and a millisecond. ## What belongs in the key The key must identify a **state**, defined as everything that affects which moves are legal from here and whether this counts as the goal. Nothing more, nothing less. Three failure modes, in order of how often they show up: **Under-keying.** The node is `(cell, badge held?)` because a gate is passable only with the badge, but the code stores just the cell. The first arrival at the gate-side cell — badge-less — marks it, and the later arrival carrying the badge is pruned as "already seen". The search reports no route through a route that exists. This bug is silent: no crash, no loop, just a wrong answer on the inputs that matter. **Over-keying.** Someone stores `(cell, steps taken)` or worse, the whole path. Now every entry is unique, deduplication never fires, and you have reinvented the memoryless search with a large set attached. Memory climbs until the process dies. The tell is a visited set whose size tracks the number of *expansions* rather than the number of *distinct states*. **Non-canonical encoding.** Two encodings that denote the same state but do not compare equal. A board written as a flat sequence in one place and as nested rows in another; a dial reading stored with and without leading zeros; a set of carried items in two different orders. Every such pair silently doubles the explored region. Choose one encoding, produce it in one routine, and if the state has symmetries you are willing to exploit, normalize to a single representative — a board with eight symmetries can shrink the visited set nearly eightfold, at the cost of computing the canonical form on every state. ## Mark on insertion, not on removal A subtle but standard point. If a state is only recorded when it is taken out of the frontier, the same state can be added many times before its first removal — once per neighbor that generates it. The frontier balloons and each copy costs an expansion. Recording it at the moment it is *added* keeps at most one copy in flight. The honest caveat, and worth saying aloud: this reasoning holds when the first time you reach a state is a good enough time to commit to it. When edges carry differing costs, a later route to the same state can be genuinely cheaper, and the algorithm must be allowed to reconsider it rather than pruning on first sight. Knowing which regime you are in is the difference between a correct search and a fast wrong one. ## Where unusable states go States that cannot exist at all — a jammed wheel position, a shelf under maintenance — belong in the neighbor rule, which simply never emits them. Pre-seeding them into the visited set usually behaves the same and is a common shortcut, but it conflates "is not a node" with "already explored", which hides bugs when you later want to report why something was skipped, and it fails outright when the start state is itself unusable: the shortcut returns nothing without ever noticing the input was invalid. ## What good sounds like "Moves are reversible, so the state graph has cycles and paths reconverge; I keep a set keyed on a canonical encoding of the full state — coordinates plus whatever else changes which moves are legal — and I mark on insertion so a state is queued once. I would never fold the path or the step count into the key, because then nothing deduplicates."