Word Search & Pruning

The Idea

Spelling a word in a letter grid is backtracking on a board instead of a list. From the current cell, the four neighbours are the branches.

Two lines do the pruning. The first rejects a cell whose letter is wrong or that is off the board, killing that whole subtree immediately. The second writes a blocking marker into the cell before recursing and restores it afterwards, so one path cannot reuse a letter while a different path still can.

Real-World Example

Highlighting a found word on a word-search puzzle app. The board is small but the naive route count is enormous, so the app only survives because a mismatched letter ends a branch after a single comparison.

The Code

grid = [["s", "n", "a"], ["b", "a", "k"], ["t", "p", "o"]]
def find(r, c, word, k):
    if k == len(word): return True
    if not (0 <= r < 3 and 0 <= c < 3) or grid[r][c] != word[k]:
        return False                       # off the board or wrong letter
    grid[r][c] = "#"                       # blocked for this path only
    ok = any(find(r + dr, c + dc, word, k + 1)
             for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)))
    grid[r][c] = word[k]                   # un-choose
    return ok

print(find(0, 0, "snap", 0), find(0, 0, "snip", 0))

print(find(0, 0, "snap", 0), find(0, 0, "snip", 0))