Word Search — The Mosaic Floor

Boss 6: The Mosaic Floor

Every un-choose so far popped a list. This boss's un-choose heals a board: the shared state is a two-dimensional grid that every branch reads and writes, and the restore-exactly discipline gets its sternest test. If you fought the Treasure Grid at the end of the Tries dungeon, this is that boss's inner engine, met on its own terms, one word, no trie, nothing between you and the mark/unmark law.

The story

The museum's entrance mosaic:

A  B  C  E
S  F  C  S
A  D  E  E

Legend: the founder's motto "ABCCED" can be traced through it, stepping only to adjacent tiles (up/down/left/right), never standing on the same tile twice within the trace.

Verify it: start at the top-left A. B is right of it. C right of that. Second C? Below the first. E? Below that C. D? Left of that E. A→B→C→C→E→D, all adjacent, all distinct tiles. Legend confirmed.

Now try "SEE": the S at top-right... E below it, E below that (or left of it). Confirmed too. And "ABCB": A→B→C fine, then B again, the only adjacent B is the one already chalked. Dies. Every start dies. False.

The chalk is the story's key mechanic. While tracing, you mark your current tile so the trace can't loop back onto itself. When a tile's every continuation fails, you wipe the mark and retreat, because that tile being off-limits was only true for the trace that stood on it. Another route through the hall may legitimately pass there. Chalk is path-local truth, and wiping is what keeps it path-local.

The problem, dressed up properly

Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

LeetCode 79. One word, one boolean, the single-target version of what the Tries finale did for 30,000 words at once.

The naive attempt

Enumerate all paths of length len(word) and compare? The path count is exponential and almost all of them are garbage from their first tile. The only sane framing is the guided walk, extend the trace only where the next letter matches, so the naive-vs-real distinction here is subtler, and it's about the chalk. The tempting shortcut: track visited tiles in a set copied per branch (visited | {(r,c)} passed down). Correct! And it allocates a fresh set at every one of the potentially exponential steps. Mutating one shared board with mark/unmark does the same job with zero allocation, that's the upgrade this boss exists to drill.

The weapon: chalk, four doors, wipe

From every tile, attempt a trace. Each recursive step holds a position and an index into the word:

1. Tile letter ≠ word[i]? Dead. Return false. (Off-board counts as dead, guard first.)
2. i is the last letter? The whole word matched. True, all the way up.
3. Otherwise: chalk the tile (overwrite it with a sentinel #, the visited-set trick without the set), recurse into the four neighbors for letter i+1, then wipe (restore the letter), and report whether any neighbor succeeded.

def exist(board: list[list[str]], word: str) -> bool:
    rows, cols = len(board), len(board[0])
 
    def trace(r, c, i):
        if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != word[i]:
            return False
        if i == len(word) - 1:
            return True
        board[r][c] = '#'                      # chalk
        found = (trace(r+1, c, i+1) or trace(r-1, c, i+1) or
                 trace(r, c+1, i+1) or trace(r, c-1, i+1))
        board[r][c] = word[i]                  # wipe, ALWAYS
        return found
 
    return any(trace(r, c, 0)
               for r in range(rows) for c in range(cols))

Two details carrying real weight:

The or chain short-circuits, first successful neighbor stops the rest, but the wipe happens after the chain regardless of outcome. Success or failure, the board is restored before returning. A trace that succeeds and leaves chalk behind corrupts nothing today (we return immediately), but the discipline matters the moment this code grows a "find all traces" cousin, wipe unconditionally and never think about it again.

The sentinel # can never equal word[i], so a chalked tile fails the letter check naturally. The visited-check and the letter-check are the same comparison. That's the whole visited-set, deleted.

Watching it work

word = "ABCB", starting at the top-left A, the failing case, because failure shows the machinery:

trace(0,0,'A') ✓ chalk A
  trace(0,1,'B') ✓ chalk B
    trace(0,2,'C') ✓ chalk C
      trace(1,2,'B')? tile is C ✗
      trace(0,3,'B')? tile is E ✗
      trace(-1,..)? off board ✗
      trace(0,1,'B')? tile is # ✗   ← the chalk blocks the loop-back
    wipe C → false
    trace(1,1,'C')? tile is F ✗
  wipe B → false
wipe A → false
(every other A on the board: same fate)
→ False ✓

The fourth check is the entire reason chalk exists: the trace tried to bend back onto its own B, met #, and died honestly. And after each level's failure, the wipe restored the letter, by the time the outer loop tries the next starting tile, the mosaic is pristine.

Gotchas

1. Wiping inside the failure branch only. Restore must be unconditional, after the neighbor attempts, before the return. Gating it on found leaves chalk on successful paths, and any later caller (the all-matches variant, the next test case in a shared runner) inherits a vandalized board.

2. Checking neighbors before recursing instead of guarding on entry. Both work, but validating at the top of trace (bounds + letter in one place) means the four recursive calls need no conditions at all. Scattered guards at every call site is where off-by-one bounds bugs breed.

3. A visited set that never un-visits. The set-based version needs visited.remove((r,c)) exactly where the wipe goes. Forgetting it makes tiles permanently consumed by failed traces, false negatives on boards where routes cross. Same law, different costume.

4. Mutating the caller's board, permanently. The chalk trick modifies the input mid-run and restores it by the end, which is fine, if every wipe runs. In environments where mutation of inputs is forbidden outright, say so and fall back to the set, correctness of contract beats cleverness.

5. Single-letter words. word = "A" must return true on any board containing A, the i == len-1 check fires before any chalk. If your version chalks first and checks later, trace it on one letter before submitting.

Complexity

From each of m·n starting tiles, the trace branches at most 3 ways per step (the fourth neighbor is your chalked past) for L = len(word) steps.

Time: O(m · n · 3^L). Space: O(L) recursion depth, zero extra per-branch allocation, the board is the bookkeeping.

Boss down. XP gained.

ABCCED traces clean through the mosaic, the curator photographs the chalk line before you wipe it, and the founder's legend survives inspection.

What you walked away with:

• Backtracking on shared mutable state: chalk (mutate), explore, wipe (restore), the list-pop law generalized to boards
• The sentinel trick: overwrite-with-# makes visited-check and letter-check one comparison, no set, no allocation
• Wipe unconditionally, success and failure alike; path-local truth must not outlive the path
• Guard at entry, recurse bare, bounds bugs hate consolidation

Next up: Boss 7 — The Banner Cuts. A single ribbon of letters and a pair of scissors: cut it into pieces so every piece reads the same forwards and backwards. The choices stop being items or tiles and become cut positions, and a palindrome check guards every snip. Backtracking meets Dungeon 2's oldest trick.