What are some exceptional word squares (square crosswords with no blanks)?

Additional material

From an earlier version of the archive (entry square.9x9):

NECESSISM
EXISTENCE
CIRCUMFER
ESCARPING
STURNIDAE
SEMPITERN
INFIDELIC
SCENARIZE
MERGENCES

By Eric Albert, from Webster's New International Dictionary, Second
Edition, after a seven-month PC search (Games, March 1990, p. 4).

Word squares were a popular pastime at the turn of the century,
although largely outstripped (and so now nearly forgotten) due to the
invention and development of the 'real' crossword.  Word squares are a
special case of a more general "fully interlocking" word puzzle called
'forms'.  In the early years of the century they really developed a
SLEW of odd shapes and layouts.  Things like triangles:

      *
     ***
    *****
   *******

and all sorts of other odd shapes (e.g., they might do something that
looked like a four-leaf clover, or a human shape, or a windmill, or
....).

The thing that is interesting about forms is that they are VERY hard to
compose, but are generally not too hard to solve (since there is a LOT
of interlocking).  With-black-squares crosswords generally tip the
balance the other way: they're fairly easy to compose, but can be made
pretty tricky for the solver.

8x8 word squares are fairly common (although HARD to compose --- even
7x7's are fairly hard unless you're _quite_ good at it).  9x9's are
truly rare beasts: there have only been a few done, ever, and the
aficionados of this form of word-play know _every_ one, and who
composed them, and when, etc.

----

In June 1999 Graham Toal started a discussion of word square algorithms
on the word-game-programmers mailing list:

Here are some word squares.  The first is the most common form of word
square, where the words across are the same as the words down,
symmetric across the major diagonal:

  CROSSES
  RICHEST
  OCTETTE
  SHEATHE
  SETTLER
  ESTHETE
  STEERED

A more prized square is a 'double' square, where the words down are
not the same as the words across, such as:

  ABACK
  CUNHA
  HIKER
  ELLEN
  STEPS

Next we have a rather fancy kind of square where every word can be
read both forwards and backwards, such as this one:

  kramer
  romane
  amunam
  manuma
  enamor
  remark

(All these examples were generated by my program, though it appears
this latter one is a case of independent rediscovery as Darryl Francis
reports that Dmitri Borgmann, possibly among others, has already
published this one!)  Again, you'll note the symmetry down the main
diagonal, and this time also the other three diagonals!  A square like
this which was *not* symmetrical would be a rare find, for example:

  alala
  nagas
  amaga
  samen
  arara

I've also seen semi-double squares where the symmetry was down the
opposite diagonal, and of this form:

  anana
  simar
  agama
  neper
  arara

Looking up all the words in this square quite expands your
vocabulary!  Blue Throated Macaw indeed!

How do we generate squares?  Just put down a word horizontally, then
try another one underneath it, and so on, and once you've filled a
square, check that the downward words are also valid.  This takes D^L
steps, where D is the size of the dictionary and L is the length of a
word, beyond any hope for more than 2, 3, or maybe 4 letters.

The next trick: after each row, check the downward stems.  Some
placements will generate the initial letters of a downward word which
cannot form a real word, eg 'x' below a 'v' as in

  VAGUS
  XENON

- we know there are no words starting in 'VX....', so we don't need to
try anything in the next three rows for that combination.  A
dawg-based spelling checker is an ideal tool for checking that the
initial stem of a word is valid.

Next: each partially formed vertical word has only a limited number of
options available at the next free position, so that a word placed
horizontally might be limited effectively by a regular expression such
as [aei][vblkm][erosp][e][dy].  The dawg node you reach at the end of
each downward stem lists all the allowed letters in that position, so
instead of iterating over all the words in the dictionary, walk the
trie a letter at a time, trimming the horizontal placement the second
we find a letter that cannot be placed.  (Our Scrabble programmers will
notice the similarity to 'cross checks' of vertical words when playing
a horizontal Scrabble move.)  Taken together these two optimisations
make the word square problem tractable up to about 6x6 squares.  One
further low-level optimisation is to keep a 2-D array of dawg nodes so
that as we add each row, we only have one step to calculate for each
column.  With this help, it's just barely possible to enumerate all
7x7 squares, if you have a powerful CPU and lots of time.

Tony Augarde's book, The Oxford Guide to Word Games, gives the
following (unsuccessful) attempt at a 10x10 square by Frank Rubin:

  accomplish
  cooperancy
  copatentee
  opalescent
  metenteron
  prestation
  lancetooth
  interiorly
  scenootl
  hyetnnhy

Frank Rubin must be using a different algorithm, because the one I
explained above would never have generated the intermediate prefixes
'scenoo' or 'hyetnn'; in fact placement would never have gone beyond
trying metenteron.  I suspect he is assuming the result will be a
single square (one which reads down the same as across) and placing
each word vertically and horizontally at the same time.

When I first ran the code on a relatively small dictionary, I
generated:

  356 2-letter squares from a list of 64 words
  221756 3-letter squares from a list of 626 words
  3718565 4-letter squares from a list of 2344 words
  314261 5-letter squares from a list of 4138 words
  7121 6-letter squares from a list of 6254 words
  12 7-letter squares from a list of 8517 words
  no 8 letter squares from a list of 10344 words
  no 9 letter squares from a list of 6148 words

With a larger word list I found 56976 6-squares, and 6174 7-squares,
but the latter run was aborted before completion as it was clearly
going to take months.  From a vocabulary that was approximately 4
times larger, we build about 8 times as many 6-squares, so there's a
more than linear win from a larger word list.

It was suggested by Darryl Francis that building the squares bottom up
rather than top down could allow more trimming early, since the ends
of words include many common affixes such as -ed, -ing.  However, it
turned out that generating word squares from the bottom up takes
between maybe 2 to 5 times longer on some of the ones I tried.  (A
quick&dirty algorithm for bottom-up generation: reverse the letters of
the words in your word list, use the same top-down code, then print
the result backwards.)

Another idea: generate all top "halves" and all bottom "halves" of a
square separately, then marry them up.  If we generate 10x6 top halves
and 10x6 bottom halves rather than 10x5's, the two halves overlap in
two words, so matching them up can be done for all halves at once by a
simple sort, of order S log S.  After a week of testing a 10x10
decomposed into 10x6 I have no partial solutions yet.

Currently our 10-letter vocabulary is 52000 words, all from
respectable sources (ie no junk words from Unix spelling checkers).

-- Graham Toal (gtoal@gtoal.com)

I have only seriously programmed a *single* word square finder (words
across same as those down), and that was years ago.  I expect that,
given a PC with today's fast chips and copious memory, my program could
enumerate all *single* squares in any reasonably-sized database in
under an hour, and perhaps in under a minute.  If I recall correctly,
increasing the size of the database after a certain point only
increases the time linearly.

I found the first single-dictionary (single) 9-square and Chris Long
found the second (and third?).  The single word square problem has been
solved for years in terms of programming.  I'm interested in finding a
single 10-square and have just been waiting for a big enough database.
Then it'll be an afternoon of computer time.  The double word square
problem is another story.  Perhaps.

Much bigger databases than 52000 10-letter words exist.  Just the
number of 10-letter words from the OED is much larger than that.

I'd be interested if you have any data on "Albert's Conjecture" (made
by me in the 1980s): Given a large database, it will take much longer
to search the entire space of double squares than that of single
squares but, when you're done, you'll have found more double squares.
Is this true?

-- Eric Albert (ealbert@world.std.com)

Taking Frank Rubin's approach of generating only single squares,
coupled with highly optimised trimming from the DAWG, we seem to have
built a very fast generator indeed, even on my creaking 486: the
generation for both 6's and 7's completed, running in parallel, in less
than 15 minutes.  The problem now seems to reduce to finding more
acceptable words.  Or cheat, and do a polyglottal square :-)  However,
it remains as difficult as I stated to produce a general solution
capable of generating all the double squares too, for 7x7 or greater.

I think I may have come up with a new algorithm for arbitrary size
double word squares, which reduces it to a word *ladder* problem.  The
trick is to calculate words which can be placed adjacent to each other
on a row-by-row basis, *ignoring* the context of previous rows.  Make a
list of tuples (row 0 word, row 1 word) of every successful placement
of two words.  Then, using only the words which were generated as row
1 words, find for each which other word can be placed below it,
forgetting whatever was in row 0, and list these as (row 1 word, row 2
word); repeat up to (row n-2 word, row n-1 word).  Then perform a tree
walk from one row to the next, linking (row 0 word, row 1 word) with
(row 1 word, row 2 word) where they have the same row 1 word, and so on
to the full depth of the square.  This will generate many squares
which are not correct word squares, but the same pruning down the
vertical axis using a dawg as before will chop that down to size.
Generating each row is an N^2 operation, so performing N of them is an
N^3 operation, MUCH better than N^10 or even N^6 as described earlier.

-- Graham Toal

The support of a word square is defined as the number of words needed,
on the average, to produce a single square.  The support for an
n-square can be calculated by the following scaling formula:

  Support = (no. of n-letter words)/(nth root of the number of squares
  found with these)

Given these two quantities, one can always determine an experimental
support value, and attempt to extrapolate these values to larger n.

Chris Long developed a theoretical support model which can be applied
to either single or double word squares.  In his model, he assumed a
hypothetical universe of "words" constructed by drawing letters
independently and at random from the alphabet using English-language
text probabilities (E = .13, T = .10, etc.):

  Support = (15.8) raised to the power (n-1)/2  single word square
  Support = (15.8) raised to the power n/2      double word square

Thus, a double word square is as hard to construct as the next larger
single word square.  It has been found that at least for small squares,
the theoretical support is only about 2/3 of the actual support
corresponding to English words.  Because of this, it may be necessary
to assemble a stockpile of some 350,000 10-letter words (theoretical
support 247,718) to find a 10-square.

Jeff Grant has generated the best example known of a 10-square (by
hand, involving various coined words), as well as the double 8-square
TRATTLED / HEMERINE / APOTOMES / METAPORE / NAILINGS / ALOISIAS /
TENTMATE / ASSESSED.  Tetalite is a variety of calcite in Chester's
Dictionary of the Names of Minerals (1896).  Limonias is an old name
for Serapias Longifolia or Cephalanthera Longifolia, in J.C. Willis's
A Dictionary of the Flowering Plants and Ferns 8th Edition (1973).  All
other words can be found in the Merriam-Webster Unabridged or the OED.

-- Ross Eckler (wordways@juno.com)

Steve Gordon (SAGordon@primenet.com) proposed letter-at-a-time search
with 2N cooperating iterators through a DAWG of the N-letter words, one
for each row R1..RN and each column C1..CN:

For each square (i, j), IF i <= j, THEN Ri places a letter on the
square using its own thread through the DAWG and Cj must either use
that letter in its own thread through the DAWG or reject it (causing Ri
to backtrack).  IF i > j, then the roles are reversed, with Cj taking
precedence over Ri.  The number of parallel dominant active threads
corresponds to the diagonals of the N x N square, giving the sequence
1, 2, 3, ..., N, ..., 3, 2, 1.  Whenever the last square gets filled in
by RN and CN agrees with it, then a new solution has been found.  Every
"double" solution will actually be found twice - it and its reflection.

The key to the efficiency is how effectively the constraints prune
down fruitless attempts on higher numbered rows and columns.  The
columns that are already further developed than any given row should
have a much lower branching factor in their DAWGs, so let their DAWG
generate those squares and use the row DAWG to verify the fit instead
of the other way around.  The search also restarts easily from a
checkpoint, and can be split among volunteers by the letter at (1,1).

-- Steve Gordon

It's almost identical to the algorithm I described, but choosing only
single squares was the most major optimisation of any I had tried, for
very little loss.  Rather than splitting the work per letter, simply
splitting the space of initial top-line placements into equal chunks
for N processors (eg processor #1 tries all words starting
AARDVARK-LONESOME and processor #2 handles LONGBOAT-ZYMOLOGY) ought to
allow almost perfect decomposition of the problem.  Perhaps we would be
better served to try fitting words across rows which have the lowest
branching ratio - which may turn out to be in the middle of the word.

-- Graham Toal

[ Editor: posted under the subject "A Better Word Cube". ]

presto rushes escort shovel terete ostler
rushes untame staler halite emetin serene
escort staler cagily olives relent trysts
shovel halite olives vivers eterne lessee
terete emetin relent eterne tinner entera
ostler serene trysts lessee entera reseal

All words are in the Official Scrabble Players Dictionary.  In fact,
this is the only such cube (with the minor fact that "reseal" can be
either "reseat" or "reseau").

-- Chris Long <clong@remus.rutgers.edu>, October 1993

[ Editor: this is a 6x6x6 cube of letters, shown as a 6x6 array of
words: the k-th letter of the word in line i, position j is the cell
(i,j,k).  The array is symmetric (the word at (i,j) equals the word at
(j,i)), e.g. the first letters of line 1 spell "presto" again. ]

[ Editor: a comment on the German 7x7 square in this entry: ]

>  waelzte
>  abhauen
>  ehrtest
>  latente
>  zuenden
>  testest
>  entente

"entente" has no meaning in German. It is senseless.  And the other
words are very exclusive forms of verbs, except "latente", which is an
adjective.

-- Christoph Enzinger <leo@cosy.sbg.ac.at>