Word Search — Backtracking on Grid

A simple path, not a walk

The problem is stated over a grid board[m][n] of characters and a target word of length L. A solution is a sequence of L cells where consecutive cells are horizontally or vertically adjacent, the letter in cell i equals word[i], and no cell appears twice. That last clause is the entire difficulty.

Delete it, and the problem becomes: is there a walk of length L spelling the word? That has a clean dynamic program. Let reach[r][c][i] be true when the suffix word[i..] can be spelled starting at (r, c). Fill it backwards over i: a cell is true at index i when its letter matches word[i] and some neighbour is true at i+1. That is m·n·L states, each with four transitions — a few microseconds on any board you will ever see.

Now put the clause back. Whether the rest of the word is completable from (r, c) at index i no longer depends only on (r, c, i). It depends on which cells the prefix already consumed. Two different routes can arrive at the same cell holding the same index and face completely different residual grids — one has the escape route still free, the other burned it three steps ago. The memo key would have to include the visited set, and that set has 2^m·n values. This is why every correct solution to this problem is a search and not a table, and why the judge constraints on it are always tiny: the runtime is exponential in the word length, not in the board size.

The baseline recursion

The standard formulation seeds a depth-first search at every cell and returns on the first success. It is worth reading with the guards in mind, because their order is load-bearing.

boolean exists(char[][] board, String word) {
  for (int r = 0; r < board.length; r++)
    for (int c = 0; c < board[0].length; c++)
      if (dfs(board, r, c, word, 0)) return true;
  return false;
}
boolean dfs(char[][] board, int r, int c, String word, int idx) {
  if (idx == word.length()) return true;
  if (r < 0 || r >= board.length || c < 0 || c >= board[0].length
      || board[r][c] != word.charAt(idx)) return false;
  char tmp = board[r][c];
  board[r][c] = '#';  // mark visited
  boolean found = dfs(board, r+1, c, word, idx+1) || dfs(board, r-1, c, word, idx+1)
              || dfs(board, r, c+1, word, idx+1) || dfs(board, r, c-1, word, idx+1);
  board[r][c] = tmp;  // restore
  return found;
}

The success test comes first, before the bounds test. That ordering is what lets the last matched cell succeed without needing a legal neighbour: the recursion for the final letter fires four child calls, and every one of them enters with idx == word.length() and returns true immediately. Swap the two guards and a word that ends on a corner still works — the corner has two in-bounds neighbours — but the code now depends on that accident, and it breaks on a one-by-one board.

The bounds test comes before the character test for the ordinary reason: board[r][c] on an out-of-range index throws. In Java that is an ArrayIndexOutOfBoundsException; in C it is silent memory corruption; in Python negative indices wrap around and you get a wrong answer instead of a crash, which is worse. Python solutions must test 0 <= r < rows explicitly rather than relying on an exception.

Marking in place versus a visited array

Overwriting the cell with a sentinel is the compact way to record "this cell is on the current path". It costs no extra memory and the check is free: the letter compare that already runs will fail against the sentinel, so a visited cell is rejected by the same branch that rejects a wrong letter. Two things go wrong with it.

First, the sentinel has to be a character that cannot appear in the input. '#' is safe when the alphabet is guaranteed to be letters and is a silent correctness bug the moment it is not. The robust version in Java flips a high bit instead:

board[r][c] ^= 256;   // mark: no char below U+0100 can collide
// ... recurse ...
board[r][c] ^= 256;   // restore: XOR is its own inverse

A Java char is an unsigned 16-bit value, so toggling bit 8 moves any Latin-1 character into a range no input letter occupies, and the restore is the identical statement — you cannot get the save-and-restore pair out of sync because there is no saved value to lose.

Second, in-place marking mutates an array the caller owns. The function is not re-entrant, cannot be called on the same board from two threads, and if the restore is ever skipped the corruption persists into every later query. The alternative is a separate boolean[m][n] visited, which costs one extra array dereference per probe and leaves the board read-only. On small boards the best of both is a single long used as a bitmask over r * n + c, valid while m·n <= 64: the mark and unmark are register operations, the board is immutable, and you can fan the seed cells out across threads because nothing is shared. That last property is the real reason to prefer it — it is not primarily a speed argument.

Why the bound is 3^L and not 4^L

From the seed cell the search has four neighbours to try. From every cell after that, one of the four is the cell you just came from, and it is already marked, so at most three survive. The number of paths explored from a single seed is therefore bounded by 4 · 3^L-1, and with m·n seeds the whole search is O(m·n·3^L) time. Space is O(L) for the recursion stack when marking in place, plus O(m·n) if you keep a separate visited array.

The bound is honest but pessimistic on anything resembling real input. Each step also has to pass a character test, and on a board of mixed letters that test kills roughly all but a small fraction of branches, so the observed tree is nothing like 3^L wide. The bound is realised by an adversarial family: fill the board with a single repeated letter and ask for that letter repeated L-1 times followed by one letter that appears nowhere. Every path is explored to full depth and every one fails at the last character. This is the same shape of adversarial input that breaks the naive one-dimensional matcher — see KMP, where the fix is a failure function; no such fix transfers here, for reasons the last section gets to. Note the free prune that follows from the bound: if L > m·n the answer is false before any search, because a simple path cannot be longer than the number of cells.

Prune before you recurse

Two cheap precomputations remove most of the pathological cases, and both run in time linear in the input.

Frequency check. Tally the letters of the board and the letters of the word. If the word needs more copies of some letter than the board contains, no path can exist and you return false without a single recursive call. This costs O(m·n + L) and it converts the worst adversarial inputs — the ones that hit the 3^L bound by ending in a letter that is absent from the board — into a linear scan.

from collections import Counter

def prescreen(board, word):
    rows, cols = len(board), len(board[0])
    if len(word) > rows * cols:
        return False
    have = Counter(ch for row in board for ch in row)
    need = Counter(word)
    return all(have[ch] >= k for ch, k in need.items())

Reversal. The search is seeded from every cell whose letter equals word[0], so the number of seeds is the board count of the word's first letter. Adjacency is symmetric, which means a path spelling the word forwards is the same set of cells as a path spelling it backwards. So if the board holds more copies of word[0] than of word[L-1], search for the reversed word instead: same answer, fewer seeds, and each seed's subtree is pruned by a rarer letter earlier. On boards with a skewed letter distribution this is routinely the difference between a timeout and a fast pass.

A third prune exists and is worth knowing but rarely worth paying for: after marking, count how many unmarked cells still carry letters the remaining suffix needs, and abandon the branch if that count is below the remaining length. It is a genuine cut, but recomputing it at every node costs O(m·n) per step and usually loses to the letter test it is trying to help.

Guard placement, and why || is not |

There are two idioms for the bounds test and they are not equivalent in cost. The baseline puts it at the top of dfs, so an off-grid neighbour still costs a call, a stack frame and four comparisons before being rejected. The alternative tests before recursing:

static final int[] DR = {1, -1, 0, 0}, DC = {0, 0, 1, -1};

// the entry-guard idx == word.length() can no longer fire, so test here
if (idx == word.length() - 1) { board[r][c] = tmp; return true; }

for (int d = 0; d < 4; d++) {
  int nr = r + DR[d], nc = c + DC[d];
  if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
  if (board[nr][nc] != word.charAt(idx + 1)) continue;
  if (dfs(board, nr, nc, word, idx + 1)) { board[r][c] = tmp; return true; }
}

Testing the next character at the call site is the bigger win of the two: it turns a recursive call into two array reads. The border of an m × n board is 2(m + n) - 4 cells, so on a small board the frames you save are a small share of the total; in a hot loop over many words they add up.

Moving the character test to the call site has one consequence that is easy to miss and fatal: the entry guard if (idx == word.length()) return true; can no longer fire, because no call is ever made past the last letter. Leave it as the only success test and word.charAt(idx + 1) runs off the end of the string on every successful match — StringIndexOutOfBoundsException in Java, an IndexError in Python. The success test has to move to the top of the function as idx == word.length() - 1, and it needs its own restore, which is exactly the second exit path the next section is about.

The four-way || chain in the baseline short-circuits: the moment one subtree returns true, the remaining three are never evaluated. Write | instead of || — a genuinely common slip, since the two look alike and both are legal on booleans in Java — and the code still returns the correct answer, because logical OR of the four results is unchanged. What changes is that the early exit is gone: every found word now costs a full enumeration of the remaining subtrees. The bug survives code review and every unit test, and shows up only as a timeout on the largest case. The same trap appears in Python as any([...]) with a list comprehension, which builds all four results before testing any of them; the generator form any(... for d in range(4)) short-circuits correctly.

Restoring on every exit path

The baseline has exactly one return after the mark, so its restore cannot be skipped. The loop form above has two exits — the early return true inside the loop, and the fall-through after it — and restoring on only the second is the single most common bug in this problem.

The symptom is distinctive and misleading: the first query returns the right answer, and every query afterwards on the same board is wrong. The cells along the successful path are still holding the sentinel, so a later word that needs one of them can never match. On a judge that calls exist once per test case this passes; in a test harness that reuses the board across assertions, or in production code that answers many words against one grid, it fails in a way that looks like a flaky test.

Two disciplines prevent it. Either keep the single-exit shape — accumulate into a local, restore, then return the local — or restore in a finally block so the compiler enforces it on every path including exceptional ones:

char tmp = board[r][c];
board[r][c] = '#';
try {
  for (int d = 0; d < 4; d++)
    if (dfs(board, r + DR[d], c + DC[d], word, idx + 1)) return true;
  return false;
} finally {
  board[r][c] = tmp;   // runs on both returns
}

Restore on success too, not just on failure. It is tempting to skip it — the answer is already known — but the board belongs to the caller, and a function that hands back a corrupted argument on exactly the interesting input is a bad neighbour.

The iterative rewrite, and when it earns its keep

Recursion depth here is bounded by the word length, so stack overflow is not the motivation it is in graph traversals over large inputs. The reasons to write the explicit-stack version are different: you want to pause the search and resume it, budget it by node count, or run it somewhere with a shallow stack.

The rewrite is more than swapping a call for a push, because a backtracking frame carries state a plain DFS frame does not: which direction it is up to, and the obligation to unmark on the way out. The frame has to record all of it.

def exists_iter(board, word):
    rows, cols = len(board), len(board[0])
    DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))
    for sr in range(rows):
        for sc in range(cols):
            if board[sr][sc] != word[0]:
                continue
            stack = [[sr, sc, 0, 0]]        # r, c, idx, next direction
            seen = {(sr, sc)}
            while stack:
                r, c, idx, d = stack[-1]
                if idx == len(word) - 1:
                    return True
                if d == 4:                  # exhausted: unwind and unmark
                    stack.pop()
                    seen.discard((r, c))
                    continue
                stack[-1][3] += 1
                nr, nc = r + DIRS[d][0], c + DIRS[d][1]
                if 0 <= nr < rows and 0 <= nc < cols \
                   and (nr, nc) not in seen and board[nr][nc] == word[idx + 1]:
                    seen.add((nr, nc))
                    stack.append([nr, nc, idx + 1, 0])
    return False

Note the two places the mark changes: added on push, removed on pop. Losing that pairing is the iterative version of the missing restore, and it is harder to spot because the mark and the unmark are now twenty lines apart instead of bracketing a single call. Be honest about the trade: this is longer, slower on a JIT that inlines the recursive form well, and worth it only when resumability is a requirement.

Many words at once: one trie instead of k searches

The natural extension asks for every word from a dictionary that the grid contains. Running the single-word search k times gives O(k·m·n·3L) and repeats an enormous amount of work whenever the dictionary shares prefixes — every one of oath, oaths, oatmeal re-walks the same oat cells from the same seed.

The fix is to make the dictionary drive the walk. Build a trie of all words (see the prefix tree deep dive for the structure itself) and carry a trie node through the DFS instead of an index into one word. A step onto a cell is legal only if the current node has a child for that cell's letter, so the walk dies the instant the spelled prefix leaves the dictionary — one traversal of the grid now tests every word simultaneously, and shared prefixes are walked once.

Two prunes turn this from correct into fast. First, when you reach a node that terminates a word, emit it and then clear the terminal marker on the node. A second path spelling the same word will now walk straight past it, which deduplicates the output without a hash set and without an equality check per hit. Second, on the way back up, a node with no children and no word left on it can never contribute again — unlink it from its parent. The trie physically shrinks as words are found, so the later seeds search a smaller dictionary than the earlier ones did.

It is worth being clear about what this is not. Aho-Corasick solves multi-pattern matching over a one-dimensional text by adding failure links, so the scan never rewinds. Those links encode "where to resume in the pattern set given the suffix just read" — a question that only makes sense when the text has a fixed reading order. A grid has no such order; the next character depends on which of three neighbours you choose. The trie here is a dictionary index, not an automaton over the input.

The inputs that break naive implementations

This problem has a small, well-known set of adversarial cases, and almost every one of them targets a specific missing line.

The first row deserves emphasis because it is the failure that a reader's intuition does not catch. An implementation with the bounds check, the letter check and the recursion but no mark at all is not obviously wrong on paper and passes any test whose word has no repeated letter. It fails the moment the word repeats a letter that sits next to itself, because the search happily walks back and forth across the same pair of cells. Any test suite for this problem needs at least one word with adjacent repeats.

The empty-word case is a convention question rather than a bug: with the success test at the top of dfs, an empty word returns true from the first seed, and on an empty board it returns false because the seed loop never runs. Pick a behaviour and assert it, rather than discovering it.

Where the pattern generalises, and where it stops

The eight-neighbour variant — Boggle and most commercial word-search puzzles — changes one constant: the parent is still excluded, so branching goes from three to seven and the bound becomes O(m·n·7L). Everything else carries over unchanged, including the trie rewrite, which is how a Boggle solver enumerates a whole dictionary in one pass. Boggle adds one wrinkle worth knowing about: the Qu tile consumes two characters of the target word in a single cell, so the index advance becomes data-dependent rather than always one.

The interesting boundary is what happens as L approaches m·n. A path that uses nearly every cell is a near-spanning simple path, and the search degenerates into the same shape as enumerating Hamiltonian paths — the letters still constrain which cells can follow which, so it is not the same problem, but the pruning behaviour is: the cheap letter test stops doing any work, and what you need instead are connectivity arguments about the unvisited region. That is a different toolkit from the one this article describes.

The other boundary is the one from the opening section. Any grid problem that drops the no-revisit constraint drops out of backtracking entirely and into dynamic programming or a shortest-path traversal — counting routes, minimum-cost descent, flood fill, shortest path with obstacles. Those live in the BFS-on-grids templates, and reaching for backtracking there is a common and expensive misdiagnosis. The general framework this search instantiates — the choose, explore, unchoose discipline and the pruning vocabulary around it — is covered in backtracking; the notation for the bounds above is in Big-O notation. The one question to ask of any new grid problem is whether a cell may be re-entered. The answer picks the algorithm.