DFS-based exhaustive word grid search I have implemented an exhaustive depth-first grid search that searches for all possible words in the 8 connected regions. Is there any way I can make this faster or memory efficient than it is now?
I feel like passing a copy of the seen set in dfs(xx, yy, seen.copy(), word + grid[x][y]) is an overhead that can possibly be avoided.
Or is my algorithm completely wrong and I should use something else?
This is not a code site challenge, I am just trying to implement this out of curiosity.
My first question on code review so let me know if there is something that I can add to make this better.
Also can this be made more &quot;pythonic&quot;?
def possible_directions(x, y):
    &quot;&quot;&quot;
    Returns at most 8 connected co-ordinates for given `x` and `y`
    &quot;&quot;&quot;
    for xx in range(-1, 2):
        for yy in range(-1, 2):
            if not xx and not yy:
                continue
            if 0 &lt;= x + xx &lt; len(grid) and 0 &lt;= y + yy &lt; len(grid[x]):
                yield x + xx, y + yy

def dfs(x, y, seen, word = ''):
    &quot;&quot;&quot;
    Recursive Generator that performs a dfs on the word grid
    seen = set of seen co-ordinates, set of tuples
    word = word to yield at each recursive call
    &quot;&quot;&quot;
    if (x, y) in seen:
        return
    yield word + grid[x][y]
    seen.add((x, y))
    for xx, yy in possible_directions(x, y):
        yield from dfs(xx, yy, seen.copy(), word + grid[x][y])



grid = [['c', 'f', 'u', 'c'], ['e', 'a', 't', 'e'], ['b', 'h', 'p', 'y'], ['o', 'n', 'e', 'p']] # word grid, can be any size, n x n

for x in range(len(grid)):
    for y in range(len(grid[x])):
        for i in dfs(x, y, set()):
            print(i)
This is fairly tight; I don't think there's much more performance to pull out without dropping into C. That said:
possible_directions
First, I would rename this to neighbors or successors; it's not really about direction but about the nodes in the graph that come next or are adjacent to your current node.
Second, you can reduce the number of branches and arithmetic operations a little:
for xx in range(max(0, x - 1), min(x + 1, len(grid)):
    for yy in range(max(0, y - 1), min(y + 1, len(grid[x])):
        if xx == x and yy = y: continue
        yield xx, yy

Third, you can prevent many no-op calls of dfs by doing your seen check in this function rather than in the dfs base case. That is, pass seen to this function and modify your yield line to something like
if (xx, yy) not in seen: yield xx, yy

dfs
You compute word + grid[x][y] many times (once + once per neighbor). You should memoize this before yielding it (Python may already perform this optimization for you but I doubt it).
I don't think a set of tuples is the best implementation for seen.  You can't really avoid the copy of seen that I can see, and the lookups are not as fast as they could be. You already implicitly require that every row is the same length (0 &lt;= y + yy &lt; len(grid[x]), not 0 &lt;= y + yy &lt; len(grid[x + xx])) and that seems like a sensible restriction in any case. I suggest a bit array of some sort (e.g. bitarray, which I've never used but seems to fit the bill), which will allow fast setting, checking, and copying of seen (instead of seen[x][y], check and set seen[y * len(grid) + x]).
Best practice here would probably be to have a wrapper function that does not take a seen or word argument, but initializes them for a call to your recursive helper, something like
def dfs(x, y):
    return dfs_recursive(x, y, set(), '')