· By John Kavanagh

Understanding the Backtracking Approach: Solving the 'Word Search' Problem

A photograph of blurred horizontal bands of blue, gold, white, and dark green.
Image by Taylor Leopold, licensed from Unsplash.

The 'Word Search' problem is a classic backtracking question because it asks us to explore many possible paths whilst being careful not to reuse the same cell in a single attempt. It is not enough to move through the grid; we also need to undo our choices correctly when a path fails.

That undo step is what makes this a backtracking problem rather than a simple traversal.


What the Problem is Asking

We are given a grid of characters and a target word. Starting from any cell, we may move horizontally or vertically to adjacent cells. The goal is to determine whether the word can be formed, with the restriction that a cell cannot be reused in the same path.

This means we need to try possibilities, reject dead ends, and then restore the board state for the next attempt.


Why Backtracking Fits

Backtracking is useful when:

  • we are exploring a search space
  • we make a choice
  • we recursively continue
  • we undo that choice if it fails

That is exactly the structure of Word Search. Every character match opens several possible next moves, and any one of them might be correct.


TypeScript Solution

export const exist = (board: string[][], word: string): boolean => {
  const rows = board.length;
  const cols = board[0]?.length ?? 0;
  if (word.length > rows * cols) {
    return false;
  }
  const dfs = (row: number, col: number, index: number): boolean => {
    if (index === word.length) {
      return true;
    }
    if (
      row < 0 ||
      col < 0 ||
      row >= rows ||
      col >= cols ||
      board[row][col] !== word[index]
    ) {
      return false;
    }
    const current = board[row][col];
    board[row][col] = '#';
    const found =
      dfs(row + 1, col, index + 1) ||
      dfs(row - 1, col, index + 1) ||
      dfs(row, col + 1, index + 1) ||
      dfs(row, col - 1, index + 1);
    board[row][col] = current;
    return found;
  };
  for (let row = 0; row < rows; row += 1) {
    for (let col = 0; col < cols; col += 1) {
      if (dfs(row, col, 0)) {
        return true;
      }
    }
  }
  return false;
};

Walk One Path through by Hand

This is the part that often makes backtracking click. Suppose the first letter matches at a given cell. We then ask a narrower version of the same question: can the rest of the word be formed from one of the neighbouring cells?

If the answer becomes "no", we undo the visit and return to the previous stack frame so another path can be tried.

That means every recursive call is doing the same three things:

  • check whether the current position is valid
  • mark the current choice as used
  • try the next possibilities

If none of those possibilities work, we restore the cell and back out. That is the rhythm of the whole algorithm.

Take a board whose top row is AAA and bottom row is AAB, and search for AAB. Starting at the top‑left A fails: neither adjacent A has a neighbouring B. During that attempt, the top‑middle A is marked and then restored. The next starting cell is that same top‑middle A; moving down to the middle A and right to B now succeeds. Without restoration, the first failed attempt would have removed the successful starting point.


The Most Important Detail: Restore State

The line that restores the cell is crucial:

board[row][col] = current;

Without it, one failed path would corrupt the board for later paths. This is the most common mistake in backtracking code, and it is why the technique rewards disciplined thinking more than raw speed.

This is also why I think Word Search is such a useful teaching problem. The recursion itself is not the hard part. The discipline around state is the hard part.


Complexity and Pruning

Let R and C be the board dimensions, and L the word length. A safe upper bound is O(R * C * 4^L): we try each starting cell and may explore up to four directions per step. After the first move, at most three directions can continue a path because the previous cell is already marked, so this bound deliberately overcounts. The live recursion depth is O(L), giving O(L) working space without a separate visited matrix. The initial length check rejects words longer than the board's R * C cells.

What matters is pruning as early as possible:

  • reject out‑of‑bounds moves immediately
  • reject character mismatches immediately
  • stop as soon as the whole word is matched
  • return early when the word is longer than the number of board cells

These small decisions reduce unnecessary recursion and keep the solution readable.


In‑Place Marking versus a Visited Matrix

It can sound as if we need a separate visited matrix every time. We can do that, but marking and restoring the board in place is often simpler and more space‑efficient.

The trade‑off is that we are temporarily mutating the input. In an interview or algorithm setting, that is usually fine as long as we restore the value before returning. In production application code, we might be more cautious about mutating shared data, but for this problem the in‑place approach is a very tidy fit.

In this implementation, the restoration happens before returning the saved result, on successful paths as well as failed ones. The temporary # marker is safe because the official board and word contain only English letters. If that input contract changes, the marker needs reconsidering too.


Where Backtracking Gets Messy

It can be tempting to think that backtracking is just brute force. It is more precise than that. It is structured search with disciplined undo logic.

The code goes off course when we stop being strict about the base case, the bounds checks, or state restoration. That is why these problems can feel slippery. A tiny lapse in one of those details does not make the idea wrong, it just makes the implementation unreliable.

If we want to compare the implementation here with the original problem statement, these references are the right place to start:


Wrapping Up

The Word Search problem is really about learning to trust the backtracking pattern: choose, recurse, undo. Once that rhythm becomes familiar, the solution feels much less intimidating. More importantly, it becomes reusable across many other search problems that follow the same structure.

Key Takeaways

  • Word Search is a natural backtracking problem because paths must be explored and undone.
  • Early pruning keeps the recursion far more manageable.
  • Restoring visited state is the detail that makes the whole approach correct.
  • In‑place marking is a neat solution here as long as the board state is restored.

Have a complex web platform issue?

Tell me what is blocked, what has changed, and what needs to be true after the fix. I'll come back with a practical next step.