Write a function that determines whether a string is a valid guess in a Boggle board, as per the rules of Boggle. A Boggle board is a 2D array of individual characters, e.g.:
```python
[ ["I","L","A","W"],
  ["B","N","G","E"],
  ["I","U","A","O"],
  ["A","S","R","L"] ]
```
Valid guesses are strings which can be formed by connecting adjacent cells (horizontally, vertically, or diagonally) without re-using any previously used cells.

For example, in the above board "BINGO", "LINGO", and "ILNBIA" would all be valid guesses, while "BUNGIE", "BINS", and "SINUS" would not.

Your function should take two arguments (a 2D array and a string) and return true or false depending on whether the string is found in the array as per Boggle rules.

Test cases will provide various array and string sizes (squared arrays up to 150x150 and strings up to 150 uppercase letters). You do not have to check whether the string is a real word or not, only if it's a valid guess.

Difficulty: interview

Starter code:

def find_word(board, word):
	

Solutions:
def find_word(board, word):
    grid = [l+[''] for l in board] + [[''] * (len(board[0]) + 1)]
    def rc(x, y, i):
        if i == len(word): return True
        if grid[x][y] != word[i]: return False
        grid[x][y] = ''
        r = any(rc(x + u, y + v, i + 1)
                for u in range(-1, 2)
                for v in range(-1, 2))
        grid[x][y] = word[i]
        return r
    return any(rc(x, y, 0)
               for x in range(len(board))
               for y in range(len(board[x])))

def find_word(board, word):
    def make(i, j, string, f=1, visited=None):
        if not visited : visited = []
        visited = [[k, l] for k, l in visited if board[k][l] in string]
        if [i, j] in visited or not word.startswith(string): return False
        if not f:
            if 0 <= i < len(board) and 0 <= j < len(board) : string += board[i][j]
            else : return string == word
        if string == word : return True
        visited.append([i, j])
        return any([make(i, j + 1, string, 0, visited),
                    make(i, j - 1, string, 0, visited),
                    make(i - 1, j, string, 0, visited),
                    make(i + 1, j, string, 0, visited),
                    make(i - 1, j + 1, string, 0, visited),
                    make(i - 1, j - 1, string, 0, visited),
                    make(i + 1, j + 1, string, 0, visited),
                    make(i + 1, j - 1, string, 0, visited)])
    return any(make(i, k, l) for i, j in enumerate(board) for k, l in enumerate(j) if l == word[0])

def find_word(board, word, trail=None):
    if not word:
        return True
    if not trail:
        board = {(row, col): item for row, line in enumerate(board) for col, item in enumerate(line)}
        valid_first = [k for k, v in list(board.items()) if v == word[0]]
        return any(find_word(board, word[1:], [coord]) for coord in valid_first)
    else:
        x, y = trail[-1]
        neighbors = [(x-1, y-1), (x-1, y), (x-1, y+1), (x, y-1), (x, y+1), (x+1, y-1), (x+1, y), (x+1, y+1)]
        valid_next = [p for p in neighbors if p in board and p not in trail and board[p] == word[0]]
        return any(find_word(board, word[1:], trail + [coord]) for coord in valid_next)


def find_word(board, word):    
    P = {(i,j):e for j, r in enumerate(board) for i, e in enumerate(r)}

    chains, word = [[p] for p in P if P[p] == word[0]], word[1:]
        
    while word and chains:
        c, word, newchains = word[0], word[1:], []
        for chain in chains:
            i, j = chain[-1]
            neighbours = [(i+a, j+b) for a in range(-1, 2) for b in range(-1, 2)]
            newchains += [chain +[p] for p in neighbours if c == P.get(p, None) and p not in chain]
        chains = newchains

    return len(chains) > 0

from collections import defaultdict

MOVES = {(0,1), (0,-1), (1,0), (-1,0), (1,1), (-1,1), (1,-1) ,(-1,-1)}

def find_word(board, word):
    dct = defaultdict(set)
    for x,r in enumerate(board):
        for y,c in enumerate(r): dct[c].add((x,y))
            
    paths = [ [pos] for pos in dct[word[0]] ]
    for c in word[1:]:
        if not paths or c not in dct: return False
        paths = [path[:] + [nextPos] for path in paths 
                                     for nextPos in { pos for pos in dct[c] - set(path) 
                                                          if tuple( z2-z1 for z1,z2 in zip(pos, path[-1])) in MOVES }]
    return bool(paths)

def find_neighbors(row_c, col_c, board, word, path):
    if len(path) == len(word):
        return True, path
    y_d = [i for i in range(max(0, row_c - 1), min(len(board), row_c + 2))]
    x_d = [i for i in range(max(0, col_c - 1), min(len(board), col_c + 2))]
    neighbors = [(y, x) for y in y_d for x in x_d]
    for index in neighbors:
        if index not in path and board[index[0]][index[1]] == word[len(path)]:
            path.append(index)
            result = find_neighbors(index[0], index[1], board, word, path)
            if result[0]:
                return True, path
            else:
                path = result[1]
            path = path[:-1]
    return False, path


def find_word(board, word):
    for row_c, row in enumerate(board):
        for col_c, l in enumerate(row):
            path = []
            if l in word and find_neighbors(row_c, col_c, board, word, path)[0]:
                return True
    return False

def find_word(board, s):
    
    def seekFrom(x,y):
        bd[x][y] = ''
        ret = next(dfs(x,y), False)
        bd[x][y] = s[0]
        return ret
    
    def dfs(x,y,i=1):
        if i==len(s): yield True
        else:
            candidates = ( (x+dx,y+dy) for dx in range(-1,2) for dy in range(-1,2) 
                                       if (dx or dy) and 0<=x+dx<len(bd) and 0<=y+dy<len(bd[0]) and bd[x+dx][y+dy]==s[i] )
            for a,b in candidates:
                bd[a][b] = ''
                yield from dfs(a,b,i+1)
                bd[a][b] = s[i]
    
    bd = list(map(list, board))
    return any( seekFrom(x,y) for x,r in enumerate(board) for y,c in enumerate(r) if c==s[0] )

import numpy as np

def find_word(board, word, seen=[]):
    board = np.array(board)
    inds = np.argwhere(board == word[0])
    if seen:
        inds = inds[[list(ind) not in seen for ind in inds]]
        last = seen[-1] 
        inds = inds[[max(row) == 1 for row in abs(inds - last)]]

    if len(word) == 1:
        return len(inds) > 0
    return any(find_word(board, word[1:], seen=seen + [list(ind)]) for ind in inds)


def check_valid(letter_locations, board, word):
    if len(letter_locations) == len(word): return True
    (x,y) = letter_locations[-1]
    next_char = word[len(letter_locations)]
    valid = False
    for i in range(-1,2):
        for j in range(-1,2):
            if i == 0 and j == 0: continue
            if y+i < 0 or x+j < 0 or y+i >= len(board) or x+j >= len(board[0]): continue
            if board[y+i][x+j] == next_char and (x+j,y+i) not in letter_locations:
                letter_locations.append((x+j,y+i))
                valid = valid or check_valid(letter_locations, board, word)
                letter_locations.pop()
    return valid

def find_word(board, word):
    valid = False
    if word == "": return True
    for y, row in enumerate(board):
        for x, letter in enumerate(row):
            if letter == word[0]:
                valid = valid or check_valid([(x,y)], board, word)
    return valid

def find_word(board, word, cursor = None):
    if not word:
        return True
    workboard = [row[:] for row in board]
    sy, sx, ey, ex = 0, 0, len(board), len(board[0])
    if cursor:
        cx, cy = cursor
        workboard[cy][cx] = "-"
        sy = max(sy, cy - 1)
        sx = max(sx, cx - 1)
        ey = min(ey, cy + 2)
        ex = min(ex, cx + 2)
    for     y, row  in enumerate(workboard[:ey][sy:]):
        for x, cell in enumerate(      row[:ex][sx:]):
            if cell == word[0] and find_word(workboard, word[1:], (x + sx, y + sy)):
                return True
    return False