Word SearchBacktracking on a grid

01Why it exists

Reach for it when you see:Grids, adjacent cells, each cell usable once, finding one path or every path, marking what you have visited, the four directions, turning back when a route dead-ends.

02The core idea

Grid backtracking turns the "choice" of backtracking into which direction to step. Starting from one cell, check whether its letter is word[i]; if it is, look for word[i+1] in the four neighbouring cells, and if any direction succeeds the whole search succeeds. This is the same thing as DFS on a graph, and the difference lies in how visited is handled: DFS looking for connected components never re-enters a cell once it has been visited, whereas grid backtracking has to clear the mark on the way back, because one cell may appear in several different paths — it just cannot appear twice in the same path.

The cheapest way to mark is to edit the board itself: rewrite the letter as # on entry and put it back on exit. Since # never equals a letter, the "already visited" test and the "wrong letter" test collapse into the single line board[r][c] != word[i]. If you would rather not touch the input, keep a separate visited array; the logic is identical.

The three steps are still make the choice (mark), recurse (four directions) and undo the choice (clear the mark). The pruning here is "return immediately if the letter is wrong", and since the test happens the moment you enter a cell, a failing branch never expands its four directions at all. Two more speedups are common: count the letters on the board up front and return false straight away if the board cannot supply what the word needs; and if the word's first letter is more common on the board than its last, search the word backwards, which leaves far fewer starting cells.

Complexity: m×n starting cells, each going at most L levels deep (L being the word's length), with 4 directions per level (3 if you never step straight back), giving an upper bound of O(m·n·4ᴸ). Space is the recursion depth, O(L). To find many words on the same board (Word Search II), do not search them one at a time: put every word into a trie and walk the trie alongside the DFS, so one search matches all the words at once.

03The algorithm

1. 1Call dfs(r, c, 0) for every cell (r, c) of the board; if any of them returns true, the word is there.
2. 2Prune first inside dfs(r, c, i): return false if the position is out of bounds or board[r][c] != word[i].
3. 3If i == len(word) - 1, the last letter matched too, so return true.
4. 4Make the choice: set board[r][c] to #, recurse with dfs(nr, nc, i + 1) into the neighbours above, right, below and left, and return true as soon as one of them does.
5. 5Undo the choice: whatever the outcome, restore the original letter to board[r][c] before leaving. Restore it on success too — do not leave the board dirty.

04Interactive demo

Searching a 3×4 grid for "SEE". Starting cells are scanned from the top-left, and every S branches out in four directions. Watch the marks get cleared after all three directions out of the first S fail, and then, starting from the second S, watch the upper E dead-end and only the lower E succeed once the mark has been restored.

05Code

Word Search with in-place marking, plus the variant that lists every path through a maze (using a visited array, and recording rather than returning when it reaches the goal, so the search continues).

# Word Search (LeetCode 79): DFS on a grid. A visited cell is temporarily rewritten to '#' and restored on the way back
def exist(board, word):
    rows, cols = len(board), len(board[0])

    def dfs(r, c, i):
        if board[r][c] != word[i]:            # wrong letter in this cell
            return False
        if i == len(word) - 1:                # the last letter matched too
            return True
        ch = board[r][c]
        board[r][c] = "#"                     # make the choice: mark the cell as visited
        for dr, dc in ((-1, 0), (0, 1), (1, 0), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and dfs(nr, nc, i + 1):
                board[r][c] = ch              # restore even on success, do not leave the board dirty
                return True
        board[r][c] = ch                      # undo the choice: clear the mark
        return False

    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))


# Variant: list every path through a maze from start to goal (0 is open, 1 is a wall)
def all_paths(maze, start, goal):
    rows, cols = len(maze), len(maze[0])
    ans = []
    path = []
    visited = [[False] * cols for _ in range(rows)]

    def dfs(r, c):
        path.append((r, c))
        visited[r][c] = True
        if (r, c) == goal:
            ans.append(path[:])
        else:
            for dr, dc in ((-1, 0), (0, 1), (1, 0), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and maze[nr][nc] == 0 and not visited[nr][nc]:
                    dfs(nr, nc)
        visited[r][c] = False                 # clear the mark: another path may still pass through this cell
        path.pop()

    dfs(*start)
    return ans


if __name__ == "__main__":
    board = [list("ABCE"), list("SFCS"), list("ADEE")]
    print(exist(board, "SEE"), exist(board, "ABCCED"), exist(board, "ABCB"))   # True True False
    maze = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
    print(len(all_paths(maze, (0, 0), (2, 2))))                              # 2

06Practice

• LeetCode 79Word SearchMedium
• LeetCode 1219Path with Maximum Gold (every finished path has to clear its marks)Medium
• LeetCode 130Surrounded Regions (DFS without clearing the marks — compare the difference)Medium
• LeetCode 212Word Search II (paired with a trie)Hard
• LeetCode 980Unique Paths III (list every path that covers all the empty cells)Hard
• LeetCode 2328Number of Increasing Paths in a Grid (strictly increasing means no backtracking, so drop the marks and memoise instead)Hard