Untitled

def helper_paths_n_word(n, board, words, current_path, paths,current_st):
    if len(current_st) > n:
        return

    last_cell = current_path[-1]
    last_row, last_col = last_cell

    # Define the eight possible directions
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)]

    if len(current_st) == n:
        if current_st in words:
            paths.append(current_path[:])  # Append a copy of the current_path
        return

    # Explore adjacent cells
    for r1, r2 in directions:
        new_row, new_col = last_row + r1, last_col + r2
        if 0 <= new_row < len(board) and 0 <= new_col < len(board[new_row]):
            new_cell = (new_row, new_col)
            if new_cell not in current_path:
                current_path.append(new_cell)  # Append the new_cell to current_path
                current_st+=board[new_row][new_col]
                helper_paths_n_word(n, board, words, current_path, paths,current_st)
                current_path.pop()  # Remove the new_cell from current_path
                current_st=current_st[:len(current_st)-1]


def find_length_n_words(n: int, board: Board, words: Iterable[str]) -> List[Path]:
    paths = []
    for row in range(len(board)):
        for col in range(len(board[row])):
            current_st = ""
            start_cell = (row, col)
            helper_paths_n_word(n, board, words, [start_cell], paths,current_st)

    return paths