Word Search

Return true if word can be spelled out on the m x n letter grid board by stepping from each letter to the next through cells that touch up, down, left or right.

Diagonal steps are not allowed, and no cell may be used twice in the same word.

Grid DFS with an undo — backtracking on a board.

1. Try every start. Call backtrack(r, c, 0) from each cell in row order, and stop at the first that returns true.
2. Finished? If i has run past the last letter, every letter is on the path: return true.
3. Reject. Return false for a position off the board, or a cell whose letter is not word[i] — which includes a cell marked #, because # is never a letter of the word.
4. Mark. Write # into the cell, so no deeper call on this path can use it again.
5. Explore. Try the four neighbours — down, up, right, left — with i + 1. The first one that returns true sets found and breaks.
6. Unmark. Write the letter back before returning found.

Marking the board in place is what saves a separate visited set; writing the letter back is what makes that safe.

The board is drawn exactly as the code holds it. A cell on the current path shows #, because that is what the code has written into it; the letter comes back, in amber, on the step that writes it back. The arrow is the call about to be made, a rejected cell flashes red with the reason, and a call that steps off the board lands on an empty cell outside it before returning.

Try Undo matters: the first path from the top-left A fails, and the second start only succeeds because the first one wrote its letters back.