Word Search

Check whether a word can be formed by neighboring board cells without reusing a cell.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Word Search: A recursive path owns its marked cells; failed directions return false, and every accepted cell is restored before that call returns.

Input and goalCheck whether a word can be formed by neighboring board cells without reusing a cell.

Start the outer scanFor the shown board and word ABCCED, the outer generator first calls search(0, 0, 0); A matches word[0].

Astart ABCESFCSADEE

wordABCCEDcallsearch(0, 0, 0)checkboard[0][0] = A = word[0]

Recognize it

A word must be assembled as one neighboring-cell path, choices branch in four directions, and a cell may be used once per candidate path but may be reused by later candidates.

Keep true

At search(row, col, index), every # cell is exactly one character of the current prefix word[0:index]. Before returning, the call restores its own cell, so sibling branches and later starts see the original board.

Reuse it

For path-constrained search, choose one option, mark only the state owned by that choice, recurse, then undo before returning. The same choose-explore-unchoose discipline applies to mazes, permutations, and constraint search.

Pattern: Backtracking on a grid.

Simple idea: Start from each cell. Temporarily mark a chosen cell so the current path cannot use it again. Restore it before returning.

def word_search(board: list[list[str]], word: str) -> bool:
   if not word:
      return True
   if not board or not board[0]:
      return False

   def search(row: int, col: int, index: int) -> bool:
      if index == len(word):
         return True
      if not (0 <= row < len(board) and 0 <= col < len(board[0])):
         return False
      if board[row][col] != word[index]:
         return False

      char = board[row][col]
      board[row][col] = "#"
      found = (
         search(row + 1, col, index + 1)
         or search(row - 1, col, index + 1)
         or search(row, col + 1, index + 1)
         or search(row, col - 1, index + 1)
      )
      board[row][col] = char
      return found

   return any(
      search(row, col, 0)
      for row in range(len(board))
      for col in range(len(board[0]))
   )

Cost: $O(rows\times cols\times 4^L)$ time and $O(L)$ space, where $L$ is word length.