9.19

Idea
A word (or Babbage) square is a list of [math]k[/math]-letter words
  S = (w₀, … , w_k-1) such that ∀ i,j : w_i[j] = w_j[i].
Fixing the first word to the given word [math]w[/math] turns the search into a constrained back-tracking problem.

Prefix table
To prune early, store every dictionary word of length [math]k[/math] in a map
  prefixes[p] → list of words that start with string p (Trie or defaultdict(list)).
Only those words that match the current column prefixes are considered in each step.

Recursive procedure
Let square be the current list of rows (initially [ w ]).
Current depth d = len(square).
Required prefix for the next row = column d formed so far:
  prefix = ''.join(square[i][d] for i in range(d)).
For every candidate word in prefixes[prefix]:
  append it to square, recurse; on return pop it out.
When d = k the square is complete – emit a copy.

Complexities
Building the prefix table: O(n·k).
Search: O(S·k²) where S is the number of squares produced (each validity check takes O(k)).

Reference Python 3 implementation

from collections import defaultdict def babbage_squares(first_word, dictionary): k = len(first_word) # keep only words of the right length words = [w for w in dictionary if len(w) == k] # build prefix table pref = defaultdict(list) for w in words: for i in range(k + 1): pref[w[:i]].append(w) squares, square = [], [first_word] def backtrack(): d = len(square) if d == k: squares.append(tuple(square)) return prefix = ''.join(square[i][d] for i in range(d)) for cand in pref[prefix]: square.append(cand) backtrack() square.pop() backtrack() return squares

Usage example

dict_words = {'hair','aide','idle','reef', 'alto','item','romb', ...} print(*babbage_squares('hair', dict_words), sep='\n')

The function returns the two squares shown in the statement and any other squares that begin with the same first row.

Back to Chapter 9