A puzzle page shows a rectangle of letters. You may start on any cell and trace a path by stepping up, down, left or right (never diagonally), and a path may not visit the same cell twice. Write can_trace(grid: list[str], word: str) -> bool that says whether some path spells word, one letter per cell.
grid is a list of equal-length strings, one per row.
grid = ["cat",
"oxe",
"dog"]
can_trace(grid, "coda") # False (no cell next to the "d" holds an "a")
can_trace(grid, "cod") # True (down, down)
can_trace(grid, "taxed") # False (the "e" isn't next to the "d")
can_trace(grid, "catego") # True (right, right, down, down, left)
can_trace(["aa"], "aaa") # False (a cell can't be used twice)
Constraints: 1 <= rows, cols <= 30, 1 <= len(word) <= 12, only lowercase letters.
Aim for O(rows · cols · 3^len(word)) in the worst case, and much less in practice: a path that has stopped matching the word should be abandoned right away rather than extended.
Show hint
try every cell as a start. From a cell that matches word[i], mark it as in use, try the four neighbours for word[i + 1], and unmark it when you come back so other paths can use it.