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.

Source: codewars | Difficulty: MEDIUM
Tags: Complete search

Data structures

Ad-hoc

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