Word Search & Grid Backtracking

## What the search is actually doing A grid path search grows a **simple path** — a chain of adjacent cells with no cell used twice. Picture a genomics-style letter grid where each cell holds one base, and you are asking whether some target sequence can be spelled by stepping from cell to adjacent cell. The recursion's state is three things: the cell you are standing on, how much of the target you have matched, and **which cells the current path already occupies**. That third piece is what the visited mark encodes. It exists because of a problem constraint ("a cell may not be reused within one path"), not because of an efficiency trick. ## The mark is a property of the path, not of the search This is the whole answer, and the whole misconception. There are two completely different meanings people attach to the word "visited": | Meaning | Marked when | Cleared when | What it buys | |---|---|---|---| | "on the path I am building right now" | entering a cell on this path | leaving that cell, as the frame returns | correctness of the no-reuse rule | | "resolved once and for all" | first time the cell is reached | never | each cell is expanded once, giving a linear bound | The second meaning belongs to a reachability sweep — you want the set of cells connected to a start, each cell's answer is final the moment you settle it, and never clearing the mark is exactly right. The first meaning belongs to path search, where a cell that failed *on this path* may be essential *on a different one*. Carrying the second discipline into the first problem is the classic bug. ## The failure, concretely Say the robot-style scan starts at the top-left cell and follows a branch three cells deep before the fourth base fails to match. Those three cells are unwound in the call stack, but if the marks stay, they are permanently off the board. A later branch — perhaps the one that actually spells the target — arrives at cell two, finds it marked, and turns away. The function returns "no such path" and every test you wrote with a single expected match still passes, because the first match is usually found before enough cells are poisoned. The second symptom is nastier: the grid is a shared, mutable object. After one query returns, the marks left behind are still there, so the *next* query against the same grid behaves differently from the first. The bug is not in the code you are staring at; it is in the state the previous call abandoned. ## Choose, explore, un-choose The discipline that prevents both symptoms is a shape you can apply mechanically: 1. **Choose** — mark the cell as on-path. 2. **Explore** — recurse into each unmarked orthogonal neighbour. 3. **Un-choose** — un-mark the cell, then return. The un-mark belongs to step 3, after the neighbour loop, and it must be reached on **every** way out of the frame. The most common leak is an early `return true` on success that jumps past the un-mark: the answer is right, but the grid stays dirty for whoever calls next. Either funnel the result through a single exit, or repeat the un-mark on the success path. A second leak is the mark placed before a guard that can reject the cell — mark first, discover the cell does not match, return without un-marking. Guard first, mark second. ## Overwriting the cell instead of keeping a visited grid A common variant skips the separate visited grid entirely: overwrite the cell with a sentinel value that cannot appear in the alphabet, recurse, then write the original value back. It saves the auxiliary grid, but it trades away three things. It **mutates the caller's input**, so the grid cannot be shared with anything else reading it during the search; it needs a sentinel guaranteed outside the value domain, which fails the day someone adds a new symbol; and any exit path that forgets the restore corrupts the data itself rather than just a side table. The bookkeeping obligation is identical either way — only the blast radius of forgetting differs. ## Cost Un-marking is O(1) per recursive call, so it changes nothing asymptotically; it is pure correctness. What it does *not* do is bound the work: because marks are cleared, the same cell is entered again by many different partial paths, and the search stays exponential in the target's length rather than linear in the number of cells. Removing the un-mark would make the search cheaper *and* wrong — a trade nobody wants.