board3 = [["d","c","e","b","d","e","d","a"],
          ["c","a","e","a","d","d","e","e"],
          ["a","c","r","d","b","i","c","b"],
          ["c","b","a","n","a","r","i","e"],
          ["a","e","d","e","r","i","d","e"],
          ["a","a","a","m","i","a","d","e"],
          ["b","d","n","b","b","b","k","o"],
          ["d","a","e","e","b","e","o","o"],
          ["b","b","c","a","b","b","p","a"],
          ["a","c","b","a","c","a","d","d"]]


class MatrixPookHrook:
    def __init__(self, mtx):
        self.mtx = self.prepare_matrix(mtx)
        
    def prepare_matrix(self, mtx):
        out, idx = {}, 0
        for _l, lst in enumerate(mtx):
            for _w, ltr in enumerate(lst):
                out[idx], out[idx]['letter'] = {}, ltr
                out[idx]['left'] = (lst[_w-1], idx-1) if _w else None
                out[idx]['right'] = (lst[_w+1], idx+1) if _w != len(lst)-1 else None
                out[idx]['up'] = (mtx[_l-1][_w], len(mtx[_l-1])*(_l-1)+_w) if _l else None
                if _l != len(mtx)-1 and len(mtx[_l+1]) > _w:
                    out[idx]['down'] = (mtx[_l+1][_w], len(mtx[_l])*(_l+1)+_w)
                else:
                    out[idx]['down'] = None
                idx += 1
        return out
        
    def find_one_word(self, word, out=None):
        # возвращает индексы матрицы, так если бы матрица была плоским списком
        def rectal_search(word, ltr_idx, mtx_idx, res=[], fork=[]):
            _tmp = self.mtx[mtx_idx]
            if ltr_idx or _tmp['letter'] == word[ltr_idx]:
                res.append(mtx_idx)
                ltr_idx += 1
                if ltr_idx == len(word):
                    return res
                for r in ('left', 'right', 'up', 'down'):
                    if _tmp[r] and _tmp[r][0] == word[ltr_idx] and _tmp[r][1] not in res:
                        fork.append((ltr_idx, _tmp[r][1]))
                if fork:
                    ltr_idx, mtx_idx = fork.pop()
                    res = res[:ltr_idx]
                    return rectal_search(word, ltr_idx, mtx_idx, res, fork)
            
        for idx in self.mtx:
            out = rectal_search(word, 0, idx)
            if out:
                return out
        return None
        
    def find_words(self, word_lst):
        out = []
        for w in words3:
            if self.find_one_word(w):
                out.append(w)
        return out

words3 = ["ab","nariman", "poook", "ededa","d"]

mtx = MatrixPookHrook(board3)
#print(mtx.find_one_word("nariman"))
print(mtx.find_words(["ab","nariman", "poook", "ededa","d"]))