4x4 word grid generator in Python This program should generate NxN boards where there are words going from left to right and words going from top to bottom. Words are valid if they appear in the scrabble dictionary.

For example, a valid 3x3 board would be:

ACT
TOO
EGO


as it contains ACT, TOO and EGO going across, and ATE, COG and TOO going down.

import itertools

N = 3

f = open("scrabble.txt")
words = [line.strip().upper() for line in f if len(line.strip()) == N]
words = sorted(words)
f.close()

def tuple_to_grid(t):
    for i in t:
        print(i)
    print()

found = []

for i in itertools.product(words, repeat = N):
    for j in range(N):
        down = "".join([k[j] for k in i])
        if down not in words:
            break
    else:
        tuple_to_grid(i)


N can be changed to change the size of the board. It can generate fine for 2x2 and 3x3 boards, but when it comes to 4x4 it takes hours to generate single boards.

Please comment on how to make this faster.
Your problem is here:

for i in itertools.product(words, repeat = N):


This brute-force approach is why it's taking so long. Let \$k\$ be the
number of \$N\$-letter words. For two or three letters, the time is
proportional to \$k^2\$ or \$k^3\$. Bad enough, but for four letters, it's
\$k^4\$, which is horrendous. \$k\$ is probably significantly larger for
four letters as well, depending on your word list.

So, we need to drastically prune the number of combinations to try.
There are many ways this might be done. One idea would be to prune
things a row at a time. Suppose the first row is "ACHE". Look at all
words beginning with "A". None begin with "AA" or "AQ". So the next row
can eliminate all words beginning with "A" or "Q". Similarly, second-row
second letter can't be "B" or "C" or several other things, because no
words begin with "CB" or "CC", etc. This approach should cut way down on
the combinations.