Untitled

board = """
DNG
IO0
HMB
"""

board = [list(item) for item in board.split()]

def get_word(pos, board):
    return board[pos[0]][pos[1]]

def replace_str_index(text,index=0,replacement=''):
    return '%s%s%s'%(text[:index],replacement,text[index+1:])

def get_move(pos, board):
    moves = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]
    col_len = len(board)
    row_len = len(board[0])
    res = []
    for move in moves:
        col_pos = move[0] + pos[0]
        row_pos = move[1] + pos[1]
        if 0 > col_pos or col_pos > col_len - 1 or 0 > row_pos or row_pos > row_len - 1 or board[col_pos][row_pos] == '0':
            continue
        res.append([col_pos, row_pos])
    return res

def copy_board(board):
    return [item.copy() for item in board]

def dynamic_board(pos, board, step):
    queue = []
    word = board[pos[0]][pos[1]]
    queue.append([word, copy_board(board), pos])
    res = set([])
    
    while queue:
        cur_word, cur_board, cur_pos = queue.pop(0)
        
        if len(cur_word) ==  step:
            res.add(cur_word)
            continue
        moves = get_move(cur_pos, cur_board)
        cur_board[cur_pos[0]][cur_pos[1]] = '0'
        
        for move in moves:
            new_word = cur_word + get_word(move, cur_board)
            new_board = copy_board(cur_board)
            new_board[move[0]][move[1]] = '0'
            queue.append([new_word, new_board, move])
            
    return res
            
def find_indices(list_to_check, item_to_find):
    return [idx for idx, value in enumerate(list_to_check) if value == item_to_find]

def solve(word, board, step):
    word = word.upper()
    res = set([])
    for row in range(len(board)):
        idx = find_indices(board[row], word)
        word_pos = []
        for item in idx:
            word_pos.append([row, item])
        for pos in word_pos:
            res |= dynamic_board(pos, board, step)
            
    for item in res:
        print(item)
            
solve('D', board, 3)