depth first search - python

import re

def find_word(board, word):
    side_len_board = len(board[0])

    # pad the board with zeros at the front and back so that my index lookup method does not go out of bounds
    board_padded_front = [['0' for i in range(side_len_board)]] * 2
    board_padded_front += board
    padding_back = [['0' for i in range(side_len_board)]] * 2
    board_padded = board_padded_front + padding_back

    # rollup of board into single string for easier checkup later
    board_string = ''
    for row in board_padded:
        s = ''.join(row)
        board_string += s

    # Return early if a character of the word is not in the board at all
    if not all(c in board_string for c in word):
        return False
    if len(word)==1:
        return word in board_string

    # find the start indices of the first character in the word
    start_idxes = [m.start() for m in re.finditer(word[0], board_string)]
    for idx in start_idxes:
        if depth_first_search(board_string, side_len_board, word[1:], idx):
            return True
    return False

def get_adjacent_indices(start_idx, side_len_board):
    return (start_idx - side_len_board - 1,
            start_idx - side_len_board,
            start_idx - side_len_board + 1,
            start_idx - 1,
            start_idx + 1,
            start_idx + side_len_board - 1,
            start_idx + side_len_board,
            start_idx + side_len_board + 1)

def depth_first_search(board_string, side_len_board ,word, start_idx):
    char_to_check = word[0]
    adjacent_indices = get_adjacent_indices(start_idx, side_len_board)

    # if we are at the edge of the board we need to remove some "adjanced" indicies
    new_list = []
    # left edge:
    if start_idx % side_len_board == 0:
        for i in range(len(adjacent_indices)):
            if i not in (0, 3, 5):
                new_list.append(adjacent_indices[i])
    # right edge:
    elif start_idx % side_len_board == side_len_board-1:
        for i in range(len(adjacent_indices)):
            if i not in (2, 4, 7):
                new_list.append(adjacent_indices[i])
    if new_list:
        adjacent_indices = new_list

    # get all characters in adj indices
    chars_in_adj_indices = [board_string[i] for i in adjacent_indices]
    # check if looked for char is in adj. chars > there can be more than 1 match
    match_indices = [adjacent_indices[m.start()] for m in re.finditer(char_to_check, ''.join(chars_in_adj_indices))]

    # if there is no match at all, then this can be aborted.
    if not match_indices:
        return False

    # mask last char so we don't find it again
    l = (list(board_string))
    l[start_idx] = '0'
    board_new = ''.join(l)

    # this set will store the DFS results at all steps
    res_set = []
    if len(word) > 1:
        # as long as any word is left, we recursively call the DFS
        # we store those DFS iterations results in the result set to not abort before we reach a valid branch
        for idx in match_indices:
            res_set.append( depth_first_search(board_new, side_len_board, word[1:], idx) )

        # if the result set contains any True value that means one of the branches reached the final True return value
        # and contains a valid branch which reflects the word. In that case we overall can return True
        if any(res_set):
            return True

    # if we reached the end of the word and still have matches left, then we have a valid boggle word
    # return this so it will be catched in the res_set of the prior iteration of DFS
    if len(word) == 1:
        return True



test_board = \
[   ["E","A","R","A","V"],
    ["N","L","E","C","D"],
    ["I","A","I","S","T"],
    ["B","Y","O","R","L"],
    ["Z","P","I","E","S"]]

testBoard = [
    ["E", "A", "R", "A"],
    ["N", "L", "E", "C"],
    ["I", "A", "I", "S"],
    ["B", "Y", "O", "R"]
]

print(find_word(testBoard, "ALIBZ"))