Cossword utilizes a Trie for finding valid words. A Trie is a tree
based data structure for compact storage of a dictionary. Words that
start with the same letters share a path in the Trie. For example, a
Trie containing SIN, SINE, SING, PIN, PINE and PING looks like this:

				*
			       / \
                              P   S
                             /     \
                            I       I
                           /         \
                          N           N
                         / \         / \
                        E   G       E   G

A leaf denotes the end of a word, but there are also word ends at
inner nodes; usually a word end is represented with an extra flag in
every node [1].

For the actual word search, the tree recursively searched, subject to
the restrictions of the rack and the board. The search starts on an
_anchor_, which is a square adjacent to an existing letter on the
board. According to the rules, each new word has to have at least one
letter adjacent to an existing one; the anchor is the leftmost of all
those tiles.

Starting from the anchor, edges in the tree are selected until either
a terminal is reached or no more legal words are possible. Suppose you
have space of the form .I.., and a P, a N and a G on the rack. The
algorithm will yield PIN and PING, and immediately cut off the 'S'
subtree.

Till now we can only generate words that *start* on the anchor. To get
words that *cross* the anchor, we extend the dictionary: With a word,
e. g. LANGUAGE, we also add:

ANGUAGE#L
NGUAGE#AL
GUAGE#NAL
UAGE#GNAL
AGE#UGNAL
GE#AUGNAL
E#GAUGNAL

i. e. for each representation xy with x, y nonempty, also y#rev(x).
'#' is just an arbitrary letter not occuring in the alphabet. This
way, when we start at the root going down the 'A' edge, we select not
only every word starting with an 'A', but also every word with an 'A'
*anywhere* in the word. When we encounter a '#' when scanning to the
right, we can jump back and continue searching to the left of the
anchor. (This is the reason that x is reversed: so we know where to
put the next character without knowing the length of the word).

This idea is from Steven Gordon <magordon@ecuvax.cis.ecu.edu>; he
called it a GADDAG. More information can be found in
http://www.gtoal.com/wordgames/documents/gaddag.txt.



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

Footnotes:

[1] For practical implementations, a lot of space can be saved by
merging identical subtrees, like this:


				*
			       / \
                              P   S
                               \ /  
                                I
                                |
                                N
                               / \
                              E   G

The resulting data structure is sometimes called a DAWG (directed
acyclic word graph). Note that this merging step doesn't affect the
algorithms on the tree at all, since there is no pointer to the
parent of a node.

If the Trie is static, i. e. no new words will be added once it is
generated, an extra efficient memory layout can be used: all nodes are
placed continuously in an array, and siblings are next to each other.
Then each node can be represented with only 32 bits:

struct TrieNode {
  int  letter           : 8;
  int  firstChildOffset : 22;
  bool isTerminal       : 1;
  bool isLastSibling    : 1;
};

for sufficiently small dictionaries (n < 2^22 = 4 million nodes,
enough for perhaps 1 million entries).

See TrieNode.hh for details.