Here’s a simple toy project – find all the word squares – a word square is a n x n matrix of letters where each row and column is a word. I used brute force approach and no recursion (to make it harder), so this algorithm may be easily improved. Let’s get the words:

words = [ w.strip() for w in open("myfavoritedictfile.txt", "r").readlines() ]

Let’s define the class for the word square. Being lazy, I will not define a class at all.

import collections
Square = collections.namedtuple('Square', ['n', 'hlist', 'vlist'])

Hlist is the list of horizontal words. Vlist is for vertical ones.

Let’s check if the new word can be added – we need to verify each cell where it crosses another word. This is symmetrical, hence we need only one function and swap the lists if needed.

def add(list1, list2, w):
k = len(list1)
for i, e in enumerate(list2):
if e[k] != w[i]:
return False
list1.append(w)
return True

Now the actual function that fills the word square and returns the results as the iterables.

def fill_iter(n, words):
count = 0
z = Square(n, [], [])
nw = len(words)
stk = [ 0 ]
while 0 < len(stk) <= 2 * n:
count += 1
if len(stk) % 2:
r = add(z.vlist, z.hlist, words[stk[-1]])
else:
r = add(z.hlist, z.vlist, words[stk[-1]])
if count % 1000000 == 0:
print(count, z, words[stk[-1]])
if r:
if len(z.hlist) == len(z.vlist) == n:
yield z
r = False
if len(stk) % 2:
z.vlist.pop()
else:
z.hlist.pop()
else:
stk.append(0)
if not r:
stk[-1] += 1
while stk[-1] == nw:
stk.pop()
if len(stk) == 0:
return None
if len(stk) % 2:
z.vlist.pop()
else:
z.hlist.pop()
stk[-1] += 1
return None

Since this approach is very slow, let’s reduce the search space a bit. Here’s how to get all the 5-letter words that remain valid words if read backwards e.g BUS-SUB. If we limit ourselves to these words our word square will be a “magic” word square (almost, since we do not check the diagonal). And finally – run!

s5 = set(w for w in words if len(w) == 5)
rw5 = [w for w in s5 if w[::-1] in s5 ]
for z in fill_iter(5, rw5):
print(z)

Just a few selected examples in Polish:

Square(n=5, hlist=['igrom', 'glebo', 'rener', 'obelg', 'morgi'], vlist=['igrom', 'glebo', 'rener', 'obelg', 'morgi'])

Square(n=5, hlist=['momus', 'odoru', 'motor', 'urodo', 'surom'], vlist=['momus', 'odoru', 'motor', 'urodo', 'surom'])

Square(n=5, hlist=['kinaz', 'imaga', 'nagan', 'agami', 'zanik'], vlist=['kinaz', 'imaga', 'nagan', 'agami', 'zanik'])