Finding a path of letters
In the word search problem you have a grid of letters and must decide whether a target word can be spelled by moving through adjacent cells, up, down, left, or right. Each cell may be used at most once within a single path.
Depth-first with marking
For every cell that matches the word's first letter, launch a depth-first search that tries to match successive letters:
- If the current cell does not match the expected letter, fail this branch.
- If every letter is matched, report success.
- Otherwise mark the cell as visited, recurse into the four neighbours, then unmark it on the way out.
The temporary mark, often writing a sentinel character into the cell, stops the path from revisiting a cell. Restoring the original letter after recursion is the crucial backtracking step.
Trimming the search
Quick rejections help: if the grid lacks enough of some letter the word needs, give up immediately. Starting only from cells equal to the first letter avoids pointless searches.
Key idea
Word search is a depth-first walk from matching cells through adjacent neighbours, temporarily marking visited cells so a path never reuses one, and restoring them when backtracking.