import itertools

# List of columns, not rows.
# First column, first letter. Second column, second letter, etc
columns = ["stuvö", "iktka", "ergaa", "nmlan"]
# columns = ["uhsa","vtev","mäfs","ysär","nrts","oada","nedd","ssse"]
## körläges,köttyxas,tillämna,tematisk,studsigt,närbutik,drevande,ovanligt
# columns = ["tknstkdo","öriövtäe","mtralure","vlalbntd","altääusy","giimnitx","ggnesaid","aekkttss"]

word_length = len(columns) # Number of columns

print("Remember to download a swedish wordlist!")
words = open("swedish-words.txt")
length_candidates = set()
for word in words:
    if len(word.strip()) == word_length:
        # -1 since word contains a newline
        length_candidates.add(word[:-1])

print(len(length_candidates), "words of length", word_length)

# Remove impossible words given the word list
candidates = set()
for word in length_candidates:
    i = 0
    all_good = True
    for c in word:
        if not c in columns[i]:
            # print(word, "is not possible since", c, "is not in column", i)
            all_good = False
            break
        i = i + 1

    if all_good:
        candidates.add(word)

print(len(candidates), "words of length", word_length, "AND correct characters")


def works_with(possible_words, new_words, columns):

    works = set()
    for new_word in new_words:

        # print("testing ", word, "with", w)
        # Create a letter budget
        budget = []
        for column in columns:
            d = {}
            for c in column:
                if not c in d:
                    d[c] = 0
                d[c] += 1
            budget.append(d)


        # Remove letter we already use
        for possible_word in possible_words:
            for i in range(len(possible_word)):
                budget[i][possible_word[i]] -= 1

        all_good = True
        for i in range(len(new_word)):
            if budget[i][new_word[i]] == 0:
                # print("NOT POSSIBLE to use ", possible_words, "and", new_word, "! ran out of", new_word[i], "in column", i)
                all_good = False
                break

        if all_good:
            works.add(new_word)

    return works


def rec(words, candidates, columns, index):
    if index == len(columns[0]):
        return [words]

    solutions = []
    for c in candidates:
        # The (index) word must start with the letter on row (index) in the first column
        if c[0] == columns[0][index]:
            new_candidates = works_with(words + [c], candidates, columns)

            solution = rec(words + [c], new_candidates, columns, index+1)
            if solution:
                solutions.extend(solution)

    return solutions


solutions = rec([], candidates, columns, 0)
print("Found ", len(solutions), "solutions!")
for solution in solutions:
    print(solution)
'