def insert_horizontal_candidate(horiz, tmp, w):

    for j in range(10):

            new_s += horiz[tmp[-1]+1:]
            return new_s


def insert_vertical_candidate(vertic, tmp, w, j):
    new_s = ''
    for i in range(10):
        if i in tmp:
            if new_s.find(w) != -1:
                continue
            new_s += w
        else:
            new_s += vertic[i][j]
    return new_s



def crosswordPuzzle(crossword, words):

    if type(words) != list and words.find(';') > 0:
        words = words.split(';')
    
    if len(words) == 0:#if empty candidates word return crossword
        return crossword
    
    for i in range(10):#try insert first horizontal candidates
        horiz = crossword[i]
        if horiz.find('-') != -1:
            index_of_possible_fields = []
            for j in range(10):
                if horiz[j] != '+':
                    index_of_possible_fields.append(j)
                if len(index_of_possible_fields) > 0 and (horiz[j] == '+' or j == 9):
                    mask = ''.join([horiz[j2] for j2 in index_of_possible_fields])

                    for word in words:
                        if len(word) == len(mask):
                            can_use = 0
                            for j3 in range(len(word)):
                                if (mask[j3] == '-') or (mask[j3] != '-' and word[j3] == mask[j3]):
                                    can_use += 1
                            
                            if can_use == len(word):
                                crossword2 = crossword.copy()

                                crossword2[i] = insert_horizontal_candidate(crossword2[i], index_of_possible_fields, word)

                                new_words = [w2 for w2 in words if w2 != word]

                                tmp_cross = crosswordPuzzle(crossword2, new_words)
                                success = True
                                
                                for c in tmp_cross:
                                    if c.find('-') != -1:
                                        success = False
                                if success:#if returned crossword don't have empty spaces
                                    return tmp_cross
                    index_of_possible_fields = []

    for j in range(10):#then try insert vertical candidates(at this moment crossword will be without empty horizontal)
        vertic = ''.join([crossword[i][j] for i in range(10)])
        if vertic.find('-') != -1:
            index_of_possible_fields = []
            for i in range(10):
                if vertic[i] != '+':
                    index_of_possible_fields.append(i)
                
                if len(index_of_possible_fields) > 0 and (vertic[i] == '+' or i == 9 ):
                    mask = ''.join([vertic[i2] for i2 in index_of_possible_fields])
                    for word in words:
                        if len(word) == len(mask):
                            can_use = 0
                            for j3 in range(len(word)):
                                if (mask[j3] == '-') or (mask[j3] != '-' and word[j3] == mask[j3]):
                                    can_use += 1
                            
                            if can_use == len(word):
                                crossword2 = crossword.copy()
                                new_s = insert_vertical_candidate(crossword2, index_of_possible_fields, word, j)
                                for i2 in range(10):
                                    crossword2[i2] = crossword2[i2][:j] + new_s[i2] + crossword2[i2][j+1:]
                                new_words = [w2 for w2 in words if w2 != word]
                                tmp_cross = crosswordPuzzle(crossword2, new_words)
                                success = True
                                for c in tmp_cross:
                                    if c.find('-') != -1:
                                        success = False
                                if success:#if returned crossword don't have empty spaces
                                    return tmp_cross
                    index_of_possible_fields = []
    return crossword