Qat

Qat lets you search for words matching a given pattern. It is the ideal tool for the discerning setter or solver of crosswords and other word puzzles. Try it now!

Qat can find individual words matching simple and compound patterns (much like grep, Word Matcher and similar tools); beyond that, it also has an ‘equation solver’ that can find sets of words that simultaneously satisfy given constraints. Using this feature you can, for example, find pairs of words that are single-letter (or multiple-letter) misprints of one another, words that share common segments or that differ from one another in specified ways, words containing the same segments in different orders, and much more besides. See the examples below; a more formal explanation of the pattern syntax appears at the bottom of this page.

Examples

In all the following examples, ‘word’ means ‘word or phrase’.

Specification of Qat’s syntax

The words and phrases in Qat’s dictionary are treated as if all accents, spaces and punctuation characters are removed, and all capitals converted to lower case.

Elements

• A single character matches itself.
• A full stop matches any single character.
• A set of characters in square brackets, such as [klmn], matches any one of the specified letters. Ranges can be specified (so [k-n] is equivalent to [klmn] and [a-cx-z] is equivalent to [abcxyz]) and a set can be negated using an exclamation mark inside the opening square bracket: [!a] matches any letter except a.
• The ‘commercial at’ symbol @ stands for any vowel and is equivalent to [aeiou].
• The hash symbol # stands for any consonsant, including y, and is equivalent to [!aeiou].
• An asterisk matches any sequence of zero or more characters.
• The ‘greater than’ symbol > stands for any word of two letters or more in the current dictionary. The ‘less than’ symbol < stands for the reverse of any word of two letters or more in the current dictionary.
• A digit from 0 to 9 matches any letter, the same one throughout the pattern. Different digits match different letters.
• A pair of round brackets enclosing a simple or compound pattern (see below) match that pattern.

Simple patterns

A simple pattern can consist of:

• a sequence of elements, which must all be matched in the order given, or
• a slash followed by a sequence of elements, which must all be matched but in any order, or
• a first sequence of elements followed by a slash followed by a second sequence of elements: the first sequence must be matched in the order given, while matches can be drawn from the second sequence in any order. It is not necessary in this case for the whole of the second sequence to be matched.

Compound patterns

Compound patterns can be built from simple patterns using the tilde ~, exclamation mark !, ampersand & and vertical bar | characters. Using p and q to represent simple (or other compound) patterns, you can use these four operators to form the following compound patterns:

• ~p which matches exactly those words matched by p reversed;
• !p which matches exactly those words not matched by p;
• p & q which matches exactly those words matched by both p and q; and
• p | q which matches exactly those words matched by either p or q or both.

The three operators are applied in the order of precedence shown: for example,

p | !q & r

matches those words which match p, as well as those which match r but not q. Round brackets can be used to alter the order in which the operators are applied:

(p | !q) & r

matches those words which both match r and which either match p or fail to match q.

p | !(q & r)

matches those words which either match p or which fail to match both q and r.

Qualified patterns

A simple or compound pattern can be qualified by prepending a misprint specification. This can be a backquote ` character, which forces one of the single-character elements in the pattern (before the slash, if any) not to match, or a question mark followed by a backquote ?` which allows the option of one of the single-character elements not matching.

A pattern can be further qualified by prepending a length specification. This can be:

• a number followed by a colon, which allows only matches of that length, or
• a number followed by a hyphen and a colon, which allows only matches of at least that length, or
• a hyphen followed by a number and a colon, which allows only matches of at most that length, or
• a number followed by a hyphen, another number and a colon, which allows only matches in the specified range of lengths.

A misprint specification must precede a length specification if both are given.

The equation solver

Qat’s equation solver is based around variables, represented by capital letters from A to Z. An equation consists of a left-hand side (LHS) optionally followed by an equals sign = and a right-hand side (RHS).

The LHS consists of a sequence of variables and qualified patterns. Qat will try to assign strings of characters to the variables so that the whole LHS matches the RHS. If no RHS is given, the LHS must form a word.

The RHS can be:

• a qualified pattern, which matches any word that fits that pattern, or
• a qualified pattern enclosed by round brackets, which matches any sequence of letters that fits that pattern.

Two or more equations can be written side by side, separated by semi-colons, to form a system. A system of equations is solved by finding values for the variables that satisfy all the equations simultaneously.

Dictionaries

There is a choice of dictionaries to search; more information about them is available here. The default, UKACD, is suitable for most UK crosswords and similar puzzles.

Notes

It is possible to set Qat problems it finds quite difficult, especially using the equation solver. There is a time-out to prevent undue load on the server on which it runs. If you can’t express your problem in a way Qat can solve reasonably quickly, let me know using the e-mail address on the home page.