• m == board.length, n == board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board and word consist of English letters
• Matching is case-sensitive: 'A' and 'a' are different characters

Every earlier problem in this section built an abstract path — a list of chosen numbers. Here the path is a route across a grid, and the state being modified is the board itself. That makes the undo step visible in a way the earlier problems did not, which is why this is a good place to see why backtracking is called backtracking.

The obvious approach: try every cell as a start, and from each, follow neighbours matching the next character.

def explore(r, c, i):
    if board[r][c] != word[i]:
        return False
    if i == len(word) - 1:
        return True
    for nr, nc in neighbours(r, c):
        if explore(nr, nc, i + 1):        # no record of where we have been
            return True
    return False

This does not merely give wrong answers — it does not finish. Search for "ABAB" on a board containing an adjacent A and B. The search steps A to B, then from B looks at its neighbours and finds the same A, steps back, and repeats forever until the stack overflows.

The missing ingredient is memory of the current path. A cell already used by this trace must not be entered again.

The reflex from graph traversal is to keep a visited set and never clear it. That is right for reachability problems and wrong here.

The rule is that a cell cannot be reused within one path. It says nothing about different paths. If a route through cell (1,1) fails, some other route may legitimately use (1,1) — and marking it permanently visited would block that, causing valid words to be reported as absent.

So the mark must be scoped to the path currently being explored: set when the path enters a cell, cleared when the path leaves it. That is precisely the choose-explore-un-choose rhythm, with the board as the shared state.

Rather than allocating a separate marking structure, overwrite the cell with a character that cannot appear in the word, and put the original back on the way out.

def exist(board, word):
    rows, cols = len(board), len(board[0])

    def explore(r, c, i):
        if i == len(word):
            return True                       # whole word matched
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False                      # off the board
        if board[r][c] != word[i]:
            return False                      # wrong letter, or '#' from this path

        original = board[r][c]
        board[r][c] = '#'                     # CHOOSE: claim for this path

        found = (explore(r + 1, c, i + 1) or
                 explore(r - 1, c, i + 1) or
                 explore(r, c + 1, i + 1) or
                 explore(r, c - 1, i + 1))

        board[r][c] = original                # UN-CHOOSE: always restore
        return found

    for r in range(rows):
        for c in range(cols):
            if explore(r, c, 0):
                return True
    return False

From each of the M × N starting cells, the search branches up to 4 ways at each of L steps, giving O(M × N × 4ᴸ).

The bound tightens slightly. After the first move, one of the four neighbours is the cell just left, which now holds '#' and fails the character test immediately. So the real branching is 3 after the first step, giving O(M × N × 3ᴸ).

That is a worst case rarely approached, because a mismatched character prunes a branch instantly — most paths die within two or three steps. A cheap improvement worth mentioning: skip any starting cell whose letter differs from the word's first character, avoiding a call that would fail on its first line.

Board:

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

The interesting case is the one that fails, since it shows the marking doing its job.

Note the board is byte-for-byte identical to the input at the end — every mark was paired with a restore. Now contrast with "ABCCED": the same first three steps occur, but from (0,2) the neighbour (1,2) holds C matching word[3], and the trace continues through (2,2) and (2,1) to complete, returning true up the chain — with each level restoring its cell as the true propagates.

This is the section's bridge from abstract enumeration to search over a concrete structure. The skeleton has not changed; what changed is that the shared state is the input itself rather than a list being built.

The termination style matches Sudoku rather than the enumeration problems. Compare:

Word Search takes the stricter line of restoring even on success, because the board belongs to the caller. Sudoku deliberately does not, because there the modified board is the answer. Knowing which applies is a matter of asking who owns the mutated state.

Recognition signals: path on a grid, trace a sequence through cells, route without revisiting, maze with a required pattern. The tell is a no-reuse rule scoped to a single path, which is what forces marks to be temporary.

The natural follow-up is searching for many words at once, which is Word Search II — running this function once per word is too slow, and the fix is to hold all the words in a trie and walk the board against it a single time.

Train the reflex: when a search modifies shared state, every modification needs a matching restore on the way out — and if the state belongs to the caller, that restore must happen on success too.