Word Search on a Grid

Try every cell as the start of the word. From each one, walk in the four allowed directions, checking at every step that the cell is on the board and holds the next letter you need. When you reach the end of the word you have found it.

The crucial detail is that a cell cannot be used twice in the same path, because the word must follow a simple path through the grid. You enforce that by overwriting the cell with a marker while it is part of the current path, and restoring the original letter when you back out of it.

def exists(board, word):
    rows = len(board)
    cols = len(board[0])

    def search(r, c, index):
        if index == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if board[r][c] != word[index]:
            return False
        saved = board[r][c]
        board[r][c] = "#"
        found = (search(r + 1, c, index + 1) or search(r - 1, c, index + 1)
                 or search(r, c + 1, index + 1) or search(r, c - 1, index + 1))
        board[r][c] = saved
        return found

    for r in range(rows):
        for c in range(cols):
            if search(r, c, 0):
                return True
    return False


grid = [["A", "B", "C", "E"],
        ["S", "F", "C", "S"],
        ["A", "D", "E", "E"]]
print(exists(grid, "ABCCED"))
print(exists(grid, "ABCB"))

The outputs are True and False. The word ABCCED is found along the top row and then down and back left. The word ABCB is not found, because the only B reachable after the C is the one already used in the path.

The mechanism is that the marker both records the cells in the current path and prevents the search from revisiting them. Restoring the letter after the recursive calls is what allows a different path to use that cell later, and getting that restore right is the classic bug in this problem.

The trade-off to name is the search cost. In the worst case every start cell leads to an exponential exploration of the grid, so the time is exponential in the word length times the number of cells. The pruning is what makes it workable: the letter check kills most branches immediately, and the marker kills the ones that would loop. If you need to find every occurrence rather than just one, you keep searching after the first hit instead of returning early, and the cost grows with the number of matches.

Keep a list of the coordinates you have visited on the current path, append before recursing and pop when the branch fails. When the whole word is matched, the path list is the answer.

def find_word(board, word):
    rows = len(board)
    cols = len(board[0])

    def search(r, c, index, path):
        if index == len(word):
            return list(path)
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return None
        if board[r][c] != word[index]:
            return None
        board[r][c] = "#"
        path.append((r, c))
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            result = search(nr, nc, index + 1, path)
            if result is not None:
                board[r][c] = word[index]
                return result
        path.pop()
        board[r][c] = word[index]
        return None

    for r in range(rows):
        for c in range(cols):
            result = search(r, c, 0, [])
            if result is not None:
                return result
    return None


grid = [["A", "B", "C", "E"],
        ["S", "F", "C", "S"],
        ["A", "D", "E", "E"]]
print(find_word(grid, "ABCCED"))

The output is the list of six coordinates: zero zero, zero one, zero two, one two, two two and two one. That is the path A, B, C, C, E, D across the top row and then down and to the left.

The mechanism is that the path list mirrors the recursion stack. Each level appends the cell it is standing on and each failing level pops it, so when the base case fires the list contains exactly the cells of the successful path. Because the function returns a copy of the path rather than the list itself, the caller gets a stable result even though the list is mutated during the search.

The trade-off to name is that this version restores the board only on the paths it returns from, so a caller that reuses the grid after a failed search gets a board that has been left marked. Restoring on every exit, as the simpler boolean version does, is safer at the cost of a few extra assignments. If you need every occurrence rather than the first, the loop over start cells has to keep going after a hit, and the path list has to be copied each time so the results do not alias one another.