DSA Word Search

The problem

Word Search asks whether a word can be traced through a grid of letters. A trace moves from a cell to a side neighbour, up, down, left or right. Diagonal cells are not neighbours, and one cell may appear only once in a trace.

This article uses one main board and one small board. The main board holds the rows SEA, POT and RAM. The small board holds the rows BA and ST.

board_one = [["S", "E", "A"], ["P", "O", "T"], ["R", "A", "M"]]
board_two = [["B", "A"], ["S", "T"]]
cases = [
    ("board one", "SEA", True),
    ("board one", "POT", True),
    ("board one", "RAM", True),
    ("board one", "TEAM", False),
    ("board two", "BAT", True),
    ("board two", "TAB", True),
]
for name, word, expected in cases:
    print(name, "- word", word, "expected:", expected)

Four of the six words are traceable. TEAM is not one of them. Its letters exist on the board, but they never line up as one unbroken path of side neighbours.

Intuition: the greedy walk gets stuck one step from success

A greedy walk stands on the first letter and always steps to the first neighbour holding the next letter. It never undoes a step. The board below shows where that habit leads.

The word is ABC, and a working path runs across the top row. The greedy walk tries the downward neighbour before the rightward one. The cell below A holds a B, so greedy steps down, and from there no C is reachable.

board = [["A", "B", "C"], ["B", "D", "D"], ["D", "D", "D"]]
word = "ABC"
path = [(0, 0)]
visited = {(0, 0)}
found = False
while len(path) < len(word):
    r, c = path[-1]
    stepped = False
    for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < 3 and 0 <= nc < 3 and (nr, nc) not in visited and board[nr][nc] == word[len(path)]:
            path.append((nr, nc))
            visited.add((nr, nc))
            stepped = True
            break
    if not stepped:
        break
found = len(path) == len(word)
print("greedy path:", path)
print("word found:", found)

The greedy path ends stuck under the A. The working path across the top row was one different first step away. The fix is to undo a step and try the next neighbour. Undoing a step is backtracking.

Brute force: build every walk, check it at the end

A walk is a sequence of steps between side neighbours, with revisits allowed. The brute force builds every walk of the word's length from every start cell. It checks a walk only when the walk is complete, comparing its letters with the word and its cells for repeats.

def exists_brute(board, word):
    rows = len(board)
    cols = len(board[0])
    walks = [0]
    def walk(r, c, path):
        if len(path) == len(word):
            walks[0] += 1
            letters = "".join(board[pr][pc] for pr, pc in path)
            return letters == word and len(set(path)) == len(path)
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                if walk(nr, nc, path + [(nr, nc)]):
                    return True
        return False
    for r in range(rows):
        for c in range(cols):
            if walk(r, c, [(r, c)]):
                return True, walks[0]
    return False, walks[0]

board_two = [["B", "A"], ["S", "T"]]
found, walks = exists_brute(board_two, "BAT")
print("BAT found:", found)
print("complete walks checked:", walks)

The count is small here only because BAT sits beside the first start cell. A missing word forces every walk to be built in full, because the brute force checks nothing until a walk reaches full length. Most of those walks fail on their letters alone.

The optimal solution: test each letter on arrival, mark the path

The state is the current cell, the index of the letter it must match, and a visited grid marking the cells on the current path, and the search tests the letter on arrival and unmarks each cell when its branch ends. That one sentence is the whole method.

Testing on arrival kills a wrong branch at its first wrong letter. The visited marks enforce the no-reuse rule. A word longer than the cell count is refused before any searching, because a trace cannot reuse cells to make up the length.

def exists(board, word):
    rows = len(board)
    cols = len(board[0])
    if len(word) > rows * cols:
        return False, 0
    visited = [[False] * cols for _ in range(rows)]
    calls = [0]
    def search(r, c, index):
        calls[0] += 1
        if index == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if visited[r][c] or board[r][c] != word[index]:
            return False
        visited[r][c] = True
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            if search(r + dr, c + dc, index + 1):
                return True
        visited[r][c] = False
        return False
    for r in range(rows):
        for c in range(cols):
            if search(r, c, 0):
                return True, calls[0]
    return False, calls[0]

board_one = [["S", "E", "A"], ["P", "O", "T"], ["R", "A", "M"]]
board_two = [["B", "A"], ["S", "T"]]
cases = [
    (board_one, "SEA", True),
    (board_one, "POT", True),
    (board_one, "RAM", True),
    (board_one, "TEAM", False),
    (board_two, "BAT", True),
    (board_two, "TAB", True),
]
for board, word, expected in cases:
    found, calls = exists(board, word)
    print(word, "->", found, "match:", found == expected, "- search calls:", calls)

All six cases match. The call counts stay small beside the walk counts of the brute force. Arrival testing and the visited marks cut most branches at their first step or two.

Walkthrough: tracing SEA on the main board

The walk prints each cell as it matches the next letter of SEA. The path grows one cell at a time. No wrong branch prints a line, because a cell prints only when its letter matches.

def exists_traced(board, word):
    rows = len(board)
    cols = len(board[0])
    if len(word) > rows * cols:
        return False, 0
    visited = [[False] * cols for _ in range(rows)]
    calls = [0]
    path = []
    def search(r, c, index):
        calls[0] += 1
        if index == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if visited[r][c] or board[r][c] != word[index]:
            return False
        visited[r][c] = True
        path.append((r, c))
        print("match", board[r][c], "at", (r, c), "- path:", list(path))
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            if search(r + dr, c + dc, index + 1):
                return True
        visited[r][c] = False
        path.pop()
        return False
    for r in range(rows):
        for c in range(cols):
            if search(r, c, 0):
                return True, calls[0]
    return False, calls[0]

board_one = [["S", "E", "A"], ["P", "O", "T"], ["R", "A", "M"]]
found, calls = exists_traced(board_one, "SEA")
print("word complete:", found)

The path reads straight off the match lines. It runs across the top row, one side step at a time. Each matched cell joined the path once, and no cell was revisited.

Complexity

Worst-case time is O(cells times 4^L), where L is the word length. Every cell can start a search, and each step branches toward up to four neighbours. The letter test cuts most of those branches in practice, but the bound stands for boards built to delay failure.

Space is O(cells) for the visited grid. The recursion path never holds more cells than the word has letters.

for cells, length in [(4, 3), (9, 3), (9, 4)]:
    print("cells", cells, "- word length", length, "- walks up to:", cells * 4 ** (length - 1))

Compare the bound with the call counts in section 4. The optimal search visited a small fraction of its bound on every case. Early letter tests are the reason for the gap.

Edge cases and pitfalls

A one-cell board answers at once. Its only word either matches its only letter or does not. A word needing a cell twice is impossible, because the visited marks block the second visit.

def exists(board, word):
    rows = len(board)
    cols = len(board[0])
    if len(word) > rows * cols:
        return False, 0
    visited = [[False] * cols for _ in range(rows)]
    calls = [0]
    def search(r, c, index):
        calls[0] += 1
        if index == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if visited[r][c] or board[r][c] != word[index]:
            return False
        visited[r][c] = True
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            if search(r + dr, c + dc, index + 1):
                return True
        visited[r][c] = False
        return False
    for r in range(rows):
        for c in range(cols):
            if search(r, c, 0):
                return True, calls[0]
    return False, calls[0]

print("one cell, matching word:", exists([["A"]], "A"))
print("one cell, wrong word:", exists([["A"]], "B"))
print("word longer than the board:", exists([["B", "A"], ["S", "T"]], "BATSX"))
print("word needing a reused cell:", exists([["A", "B"], ["C", "D"]], "ABA"))

Leaving a visited mark in place after a failed branch is the classic bug in this search. The cell then stays blocked for every later path and every later start position. Words that are on the board start reporting missing, and the board itself looks guilty.