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!

A French-language version of Qat is also available, with the same search syntax. Essayez maintenant!

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’ mode 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’.

Examples of ordinary patterns

Examples using qategories

Examples using the equation solver

Qat syntax: ordinary patterns

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 consonant, 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.

Qat syntax: qategories

A qategory is a pattern that matches certain words, just like the conventional letter-matching patterns that Qat supports. However, a qategory matches words according to their meaning or associations rather than their constituent letters.

A qategory pattern consists of a qategory name (which must be specified exactly) followed by a colon and then a Qat pattern, all enclosed in curly brackets. Qategories can be combined with all the other features of Qat, including sub-patterns, equations and systems of equations. They cannot be used as ‘jumble fodder’ (i.e., after the slash in a pattern other than in a subpattern).

The currently-available qategories are as follows.

Note that as in the ‘color’ example in the table above you may sometimes need to use American spellings in your patterns. The shorthand equivalents listed are liable to change in future. Qategories are not supported by the French-language version of Qat.

Each search involving a qategory is accompanied by a note explaining which databases were used in that search and provides a link to relevant licensing information.

Qat syntax: the equation solver

Qat’s equation solver is based around variables, represented by capital letters from A to Z.

Equations

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.

Otherwise, 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.

In the latter case the equation in question is not included in the table of results.

Length constraints

A length constraint consists of a sequence of variables bounded on both sides by vertical bar characters |, followed by an equals sign, followed by a length specification as described under ‘Qualified patterns’ above (without the colon). The effect of this constraint is to force the total length of the given variable sequence to fall within the specified range.

Difference constraints and breaking symmetry

A difference constraint consists of an exclamation mark followed by an equals sign, followed by a sequence of variables. All these variables are constrained to have values different from one another. If a ‘less than’ symbol appears between two of the variables, the variable to its left is constrained to be ‘less than’ the variable to its right; and likewise, mutatis mutandis, for the ‘greater than’ symbol. When deciding on the order of two strings of characters, Qat compares their lengths first and then looks at their alphabetical sequence. This is thus not the same as normal dictionary ordering.

Zero-length variables

Normally variables have to be at least one character long. It is possible to override this and allow a variable to have zero length (i.e., be the empty string), but you have to allow it explicitly with a length constraint of the form |A|=0- or similar.

Qat syntax: systems

A series of equations and constraints can be written side by side, separated by semi-colons, to form a system. A system is solved by finding values for the variables that satisfy all the equations and constraints 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.

Time-outs

Although Qat uses various techniques internally to speed up its searches, it is nevertheless possible to set problems it finds quite difficult. This is particularly true when using the equation solver. There is therefore a time-out to prevent undue load on the server on which Qat runs. If you can’t find a way to express your problem so that Qat can solve it reasonably quickly, let me know using the e-mail address on the home page.