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

To do this... ... enter this pattern... ... and get these results See for yourself!
Complete a crossword entry l.......v leitmotiv lermontov Try it
Complete a crossword entry with alternatives ..i[sz]e anise arise avise avize baize ... Try it
Match ranges of letters [l-p].[m-r].[w-z] lammy lanky lapaz lardy larky larry lenny limax ... Try it
Match disallowing certain letters ....i[!stz]e abusive acarine acquire adenine affaire airline airmile airside ... Try it
Match consonants and vowels #@#@#@#@#@#@#@ pararosaniline recapitulative rehabilitative supererogative verisimilitude Try it
Find all words beginning with xo xo* xosa xoana xoanon Try it
Find all words beginning with x and ending in a x*a xema xosa xenia xhosa xoana xeroma xyloma xerasia xylopia xanthoma ... Try it
Find all words containing the sequence xj *xj* vieuxjeu boxjunction boxjellyfish boxjunctions knoxjohnston Try it
Find all words with a j as the second letter, followed somewhere by a k .j*k* sjambok djakarta sjamboks sjambokked sjambokking Try it
Find all words which contain the vowels in order *a*e*i*o*u* caesious arsenious facetious haveitout parecious abstemious aeruginous ... Try it
Find all words which contain five consecutive vowels *@@@@@* euouae zooeae euouaes miaoued cooeeing miaouing queueing queueings Try it
Find all words which consist of ‘ace’ followed by a word ace> acetic acerate acerose acetate acetone acetose acescent acetates acetones acetabula acetabular Try it
Find all words of at most six letters beginning with x and ending in a -6:x*a xema xosa xenia xhosa xoana xeroma xyloma Try it
Find all words of seven to nine letters beginning with x and ending in a 7-9:x*a xerasia xylopia xanthoma xenophya xeromata xylomata xanthoura xenarthra xenomania xeroderma xerostoma xiphosura xylophaga xylorimba Try it
Find all words of at least ten letters beginning with x and ending in a 10-:x*a xanthomata xanthopsia xenophobia xerodermia xerostomia xenoglossia xanthochroia xanthochromia xerophthalmia Try it
Find all words of exactly nine letters which, when the first and last letters are deleted, makes a reversed word 9:.<. banisters canisters denitrate ... xenograft Try it
Find all words one letter away from bonge ‘bonge binge bodge bonce bongo bongs bonne bonze bouge conge longe Try it
Complete a crossword entry where one of the crossing letters may be wrong ?‘str.g.ly scraggly scriggly stingily stodgily straggle straggly straitly strictly strigils strongly struggle Try it
Find all anagrams of triangle /triangle alerting altering integral relating tanglier triangle Try it
Find all anagrams of triangle plus one extra letter /triangle. clareting earthling faltering gnarliest ... Try it
Find words of at least seven letters made from given letters 7-:*/rpoyesdif perfidy periods prosify spidery Try it
Find all ten-letter words starting with q and ending in s which can be made from the letters of square peg in a round hole 10:q*s/squarepeginaroundhole quadruples quandaries quarendens quarenders queenhoods quinapalus Try it
Find all words that contain a q, an x, and a z /qxz* squeezebox squeezeboxes Try it
Find all words of at most eight letters that contain all the vowels -8:/aeiou* douleia eulogia miaoued moineau sequoia aboideau aboiteau aurevoir ... Try it
Find all words with a j as the penultimate or last letter *j. | *j j jo gju haj raj taj baju benj dojo fiji fuji gajo hadj haji hajj juju mojo ... Try it
Find all words starting with kn that are also words written backwards kn* & < knar knit knob knot know knub knaps knits knots knuts Try it
Find all words of at least twelve letters not containing a reversed sub-word 12-:! *<* drinkdriving flyingcircus gainstriving kicksywicksy offscourings quickthinking Try it
Find all words starting or ending with b no initial segment of which is a word ! >*. & (b* | *b) b ab ba be ... bwana bwazi climb clomb droob dweeb hbomb jacob jelab kebab kebob scrab scrub squab squib thumb vocab aplomb bhagee bhajee ... Try it

Examples using the equation solver

To do this... ... enter this pattern... ... and get these results See for yourself!
Find exactly reduplicated words AA ... agar.agar agas.agas beri.beri blah.blah... fifty.fifty goody.goody ilang.ilang never.never night.night nudge.nudge nulla.nulla quina.quina... housey.housey pretty.pretty softly.softly talkee.talkee twenty.twenty Try it
Find reduplicated words differing in the initial letter ACBC;|A|=1;|B|=1;!=AB ... r.oly.p.oly... t.ohu.b.ohu... h.ogen.m.ogen... b.oogie.w.oogie c.urlie.w.urlie f.ender.b.ender g.ender.b.ender... n.iminy.p.iminy n.olens.v.olens... c.ulture.v.ulture... p.oopers.c.oopers... Try it
Find doubly reduplicated words AABB po.po.f.f sa.sa.ra.ra ti.ti.ca.ca no.no.nse.nse nudge.nudge.wink.wink Try it
Find even-length palindromes A~A ... pe.ep po.op se.es to.ot den.ned han.nah mal.lam mar.ram pul.lup red.der... Try it
Find odd-length palindromes A.~A ... te.n.et te.v.et aga.s.aga dei.f.ied nau.r.uan rep.a.per rev.i.ver rot.a.tor sei.t.ies sem.e.mes mala.y.alam rota.v.ator Try it
Find cyclically-permuted words AB;BA ... ch.in in.ch; ch.it it.ch; ch.ou ou.ch; ... lu.lu lu.lu; ... no.no no.no; ... Try it
Find cyclically-permuted words, avoiding reduplicated words AB;BA;!=AB ... ch.in in.ch; ch.it it.ch; ch.ou ou.ch; ... s.pud pud.s; s.pun pun.s; ... Try it
Find words with an interior k misprinted as an l AkB;AlB ... sil.k.iness sil.l.iness; stal.k.ings stal.l.ings; ... squea.k.ing squea.l.ing; under.k.ing under.l.ing; precoo.k.ed precoo.l.ed; sidewal.k.s sidewal.l.s; ... undercoo.k.ing undercoo.l.ing; mil.k.ingmachine mil.l.ingmachine Try it
Find sets of five words differing only in interior vowel AaB;AeB;AiB;AoB;AuB b.a.d b.e.d b.i.d b.o.d b.u.d; b.a.g b.e.g b.i.g b.o.g b.u.g; ... cl.a.cking cl.e.cking cl.i.cking cl.o.cking cl.u.cking; tr.a.cking tr.e.cking tr.i.cking tr.o.cking tr.u.cking Try it
Find sets of five words differing only in a vowel appearing anywhere AaB;AeB;AiB;AoB;AuB;|A|=0-;|B|=0- .a. .e. .i. .o. .u.; .a.m .e.m .i.m .o.m .u.m; ... m.a. m.e. m.i. m.o. m.u.; ... b.a.d b.e.d b.i.d b.o.d b.u.d; b.a.g b.e.g b.i.g b.o.g b.u.g; ... le.a. le.e. le.i. le.o. le.u.; mo.a. mo.e. mo.i. mo.o. mo.u.; ... tr.a.cking tr.e.cking tr.i.cking tr.o.cking tr.u.cking Try it
Find words with three consecutive interior consonants misprinted as three vowels A###B;A@@@B ... mi.zzl.ing mi.aou.ing; par.tym.an par.eoe.an; stren.gth.s stren.uou.s Try it
Find six-letter words with three consecutive consonants misprinted as three vowels A###B=......;A@@@B;|A|=0-;|B|=0-
or
A###B;A@@@B;|A|=0-;|B|=0-;|AB|=3
.cyc.lic .aeo.lic; c.lyp.ed c.ooe.ed; c.lyp.es c.ooe.es; ... per.tly. per.eia.; tal.cky. tal.eae.; ten.ths. ten.iae. Try it
Find strings that can be made into words by adding red or green Ared;Agreen sea.red sea.green; sha.red sha.green Try it
Find strings that can simultaneously complete two words draA;poAy dra.g po.g.y; dra.ck po.ck.y; dra.ke po.ke.y; dra.nt po.nt.y; dra.ps po.ps.y; dra.lon po.lon.y; dra.per po.per.y Try it
Find three five-letter words that can be put together to make a word A=.....;B=.....;C=.....;ABC
or
A;B;C;|A|=5;|B|=5;|C|=5;ABC
... compo sings ticks compo.sings.ticks; ... exist entia lists exist.entia.lists; ... honey combs titch honey.combs.titch; ... north anger abbey north.anger.abbey; ... super visor ships super.visor.ships; ... thumb nails ketch thumb.nails.ketch Try it
Find a pair of words, one obtained from the other by replacing an interior jumble of blue with a jumble of orange A/blueB;A/orangeB o.belu.s o.regano.s; ba.uble.s ba.ronage.s Try it
Find pairs of words where one is the other with the last six letters reversed B=(6:*);AB;A~B
or
|B|=6;AB;A~B
... s.eagirt s.trigae; m.egasse m.essage; m.essage m.egasse; r.etinue r.eunite; r.eunite r.etinue; ... di.sserts di.stress; di.stress di.sserts; su.surrus su.surrus; sas.araras sas.sarara; ins.hallah ins.hallah; ... Try it
Find two strings, one of length at least four made from the letters of turquoise and the other of length at least two, that can be put together in either order to make words A=(4-:*/turquoise);B=(2-:*);AB;BA
or
A=(*/turquoise);|A|=4-;|B|=2-;AB;BA
ster.ne ne.ster; ques.tor tor.ques; rose.mary mary.rose; rout.seat seat.rout; ster.ling ling.ster; trous.es es.trous Try it
Find a jumble of lilac that can be extended into a word by adding one to five letters A=(/lilac);A.;A..;A...;A....;A..... ... calli.d calli.ng calli.ope calli.pers calli.grams; ... Try it
Find eight-letter words with six-way single-letter misprints, avoiding repetitions ACB;ADB;AEB;AFB;AGB;AHB;|ACB|=8;|H|=1;!=C<D<E<F<G<H s.c.atters s.h.atters s.l.atters s.m.atters s.p.atters s.w.atters; ... ro.a.sters ro.d.sters ro.i.sters ro.o.sters ro.u.sters ro.y.sters; ... unsha.d.ed unsha.l.ed unsha.m.ed unsha.p.ed unsha.r.ed unsha.v.ed Try it
Find six-letter words with their letters strictly in alphabetical order ABCDEF=......;!=A<B<C<D<E<F a.b.h.o.r.s; a.l.m.o.s.t; b.e.g.i.n.s; b.e.g.i.r.t; b.i.j.o.u.x; b.i.o.p.s.y; c.h.i.k.o.r; c.h.i.m.p.s; c.h.i.n.o.s; c.h.i.n.t.z; d.e.h.o.r.t; d.e.l.o.r.s; g.h.o.s.t.y Try it

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.

Qategories

Qategories are a new experimental feature of Qat. Find out more.

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.

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.


This page most recently updated Thu Apr 10 22:13:03 BST 2014
Qxw screen
Qxw is a free (GPL) crossword construction program. Answer treatments, circular and hex grids, jumbled entries, more besides. New release 20140331 for both Linux and Windows. More...

Practical Signal Processing front cover
My book, ‘Practical Signal Processing’, is published by Cambridge University Press. You can order it directly from them, or via amazon.co.uk or amazon.com. Paperback edition now also available. Browse before you buy at Google Books. Wydanie polskie.

If you find this site useful or diverting, please consider a donation to NASS (a UK registered charity), to KickAS (in the US), or to a similar body in your own country.

Copyright ©2004–14.
All trademarks used are hereby acknowledged.