KNIGHT'S-TOUR LETTER SQUARES

by Mike Keith
Word Ways, 1999

 

In this article, I present a new subject for logological study: the knight's-tour letter square. Such a square is constructed by first creating a knight's tour on the chessboard, in which each square of the chessboard is visited exactly once by successive knight's moves. Normally, knight's tours are displayed by numbering the squares of the chessboard with the numbers 1 through 64 to show the knight's path. Here, however, we label the knight's tour with successive letters of the alphabet: A, B, C, ... Z, and after Z comes A again, and so on. For the standard 8x8 board the whole alphabet will be used twice plus the letters A through L a third time. (The problem can be generalized to other square and rectangular boards, in which case we just use the sequence A-Z as many times as required.)

We can now ask many questions about the resulting squares, such as:

• What is the longest word we can form along a straight line? We can, for instance, permit only words that read left to right or top to bottom orthogonally, or we can also allow diagonals and backward words, as in a word-search puzzle.

• What is the largest value of n for which we can form an N-letter word on an nxn board?

• What is the largest number of (different) words we can form? What is the largest number if we also require at least one k-letter word for each k up to n? What is the largest number of k-letter words that can be made?

One interesting facet of this problem is the degree to which it seems to require computer assistance. Generating knight's tours--at least, a lot of them--by hand is not a trivial task, so a computer is a great boon to exploring the knight's tour universe. The results in this article are just a beginning--no doubt many of them can be improved on by using different methods of constructing knight's tours or more intelligent heuristics.

Some Results

At first glance, it is not at all obvious whether an eight-letter word can be constructed on the 8x8 board, so this was the first problem I tackled. I wrote a program to generate many knight's tours at random, using the rule for constructing knight's tours devised by Warnsdorff in 1823: for the next square on the tour, choose the unoccupied square from which a knight attacks the fewest unoccupied squares. If, on any turn, there is more than one such square, choose one of them at random. Each tour is then checked for the presence of an eight-letter word in a row or column. After generating about a million random tours, the eight-letter words UNSHAVEN and ARCHIVAL emerged:

	M T Q B W D O F		E T W F G J Y H
	R C L O P G X C		V E F Y X G T K
	U N S H A V E N		S D U H U L I Z
	D K P S H Y B U		D G Z K X M L S
	Q V G J I T M Z		A R C H I V A L
	H E R C F I L A		F C J W N I R M
	W D G J Y J A L		Q B A D O P K B
	F I X E B K Z K		B E P O J C N Q

The first A and last L on the tour are underlined. Only two other eight-letter words were found: PERORATE and EPIDURAL.

I next looked for the largest number of different words, with the restriction that words only read from top to bottom or left to right, and be at least two letters long. The champion so far is at the left:

	Y Z W L A X E N		T Y P I F I N K
	V K Z Y D M N W		Q H U Z O L E H
	A X U L O B O F		X S L G J C J M
	J I B C H G V M		G R A V I N G D
	C T G H K P A P		R W H K B K X M
	F I J I F S L U		S F A B O J A F
	S D G D Q J Q B		B Q D U D Y L W
	H E R E R C T K		E T C P C V E Z

If words embedded in other words are not counted, and if preference is given for counting long words, there are still at least 20 words in this square: LAX, AXE, AX, LOB, OF, JIB, PAP, FIJI, IF, HERE, ER horizontally, and XI, IT, TIDE, CHIDE, ADO, OH, NOVA, OVAL, PUB verti-cally. If all words, embedded or not, are counted, there are at least 37 with two or more letters:

LA AX LAX AXE OF LOB JIB PAP IF FIJI HE RE HER ERE HERE ER XI

IT TI ID IDE TIDE HI CHI HID CHID HIDE CHIDE AD DO OH ADO NO OVA

OVAL PUB

which along with A, I, and O make an even 40. Another useful figure of merit is how many letters in the square are used in some word. In this case, 39 of the 64 (61 per cent) are used.

The square at the right above is a final example of a fairly rich square, containing a seven-letter word, GRAVING, plus 14 additional non-embedded words: PI, IF, FINK, EH, FAB, DUD, BE, LA, AHA, HAD, UP, JIB, BOD, ALE.

 

A New Logophilian Lingo: Knight's English

Instead of looking at the characteristics of individual squares, we can ask: which English words can be made to appear in some knight's tour letter square? This is a different question for each nxn board, so for brevity just consider the 8x8 case, and only allow words that read top to bottom or left to right. The complete collection of words which can be constructed forms a constrained vocabulary that we might call Knight's English (in contrast to the King's English). Is Knight's English, I wondered, rich enough to permit the writing of stories or poems?

First, note an important property of knight's tours: if the tour is numbered 1 through 64, the white squares on the chessboard will always contain numbers of the same parity (even or odd), and similarly for the black squares. This, in combination with the fact that there are an even number of letters in the alphabet, means that an orthogonally-placed word will always have letter values that alternate between even and odd values. In addition, we know that at most three of the letters A-L and at most two of the letters M-Z can appear. The English words with these properties (call them alternating words) are the only ones that have to be examined to determine which ones are also in Knight's English.

The table below shows the percentage of English words in the dictionary I used which are alternating words. This is the largest number of words we can ever hope for in Knight's English.

Number of letters   1    2   3   4   5   6   7   8

Percent of words   100  70  37  24  14  8.6 4.9 3.9

As an aside, note that these numbers are significantly higher than what one might expect. The probability that a random string of length 2,3,4... is alternating is 1/2, 1/4, 1/8... since each of the letters after the first has one chance in two of being the right parity. This predicts 1.6 per cent seven-words instead of the above 4.9 per cent, and the others are similarly "off". The explanation for this is the remarkable fact that all vowels have odd values (A=1, E=5, I=9, O=15, U=21, Y=25). Since vowels and consonants tend to alternate, the fact that all the vowels are the same parity significantly increases the chance of a word being alternating. Nonetheless, the above numbers tell us that Knight's English will be at best a fairly constrained dialect, especially in regard to longer words. Because the vowels are all odd, there no alternating words that begin with the letters M or Q, both being odd letters.

Just how many of the alternating words can be captured in a Knight's tour? Might it be possible, with sufficient perseverance, to construct any such word? The answer is no--the shortest examples of impossible words in a knight's tour square are POP and TUT. In the word POP, assume one of the P's is from the first alphabet group (A-Z) in the tour. It is impossible to get to an adjacent square in one knight's move so the O must be from the second alphabet group. That means that the other P can't be from the second group, since it's also adjacent to the O. But there is no third group to get a P from, so the word is impossible. Similarly, there are about a dozen impossible four-letter words: NONE, POPE, POPS, STAT, STET, TOTS, TUTU and a few less common ones.

Here are the number of words that we have been able to actually construct, expressed as a percentage of the alternating words.

Number of letters   1    2   3   4   5   6   7   8

Number of words     3   36  230 632 652 266  21  4

Percent of words   100  100  99  98  85  33  3  0.7

We can fully explain these results up to four letters, using the argument given above. For five or more letters, we do not know if all the missing alternating words are actually impossible, or whether we just haven't found them yet. In particular, we only have a very small number of seven-letter and eight-letter words. Are there many more to be discovered, or is the number of constructable long words really this small? This remains an open question.

The end of this article lists all the Knight's English words of five or more letters that we have discovered. It seems likely that any alternating word with fewer than five letters that is not impossible by the counting argument above, is in Knight's English, so these are not listed to save space. Also, if a word's plural or past tense is included, that word is not also listed.

Here is a rewrite of the first stanza of "The Raven" in which every word is a verifiable member of Knight's English (I have a knight's tour that contains it):

Ah, upon an eve in July, as I pored--oh, very lonely!--
Over five sad novels of an era lived afore;
As I bided, barely dozing, up on porch I noted raving,
As if she did stop, did tap, did perorate or jangle, or
Bodily did stop, did tap, did cry for fate or for favor--
Verily, it's she afore!

There are many questions still to be explored, including other rectangular boards, allowing words in all eight word-search directions, and the even more restricted version of the problem in which the knight's tour is required to be re-entrant (which means that the last square is a knight's move away from the first square, so that the tour forms a closed loop).

 

Table: Knight's-English words of five or more letters

abate abele abets abide abode above adits adobe adore adyta afire afore alarm alate alexin alibi aline alining alive alone along angle Anglo angry anile ankhs ankle apery aping Arabs archer archival arena arete armful atone Avalon avens avers axing axons

babel babul baled baler bangle bared barely barer baring baron batch bated bating batons bebop bedel befit behave belch bench beret beryl betel betide bevel bezel bided bidets biding bifid binary binate biped birch bitch biter boded bodily bolide boned boner borax bored borer botch boxed boxer bunch bungle buret burgh burins butyl byline Byron

chafe chafer chalets chalk chape chapel chaps charm chars chary chats chefs chela cherub chevy chided china chine chink chino chins chips chiral chital chiton chits chive chivy choler choli chops choral chore chunk chute chyle clads clang clank clans claps claret clarify clary clave clench clerk cling clink clips clods cloned clots clove cloven clover clubs clung clunk clutch crabs craned crank crape craps cratch crated crave craved crazed crazy credit crepe cretin cribs crone crony crops crude czars

dangle dared daring darkly dated dater dating davit dazed dazing debars debits debunk debut defat deluxe depot deter devil devote dilated dinar dined diner dingle direly ditch divans divers diving divots dolina doper doted dozed dozen dozer duper duping during duvets

ebony edify elate elide elite elude elute engrave enure enwrap eparch epidural erode etalons etched etude evade every evils exarch exiled exits exons exude

faded fader fading farad fared faring fatal fated favor fazed feline feral ferula ferule fetal fetch feted fetid feting fetor fever fiber fibers fibula fifed fifers fifing filched filed filer filets filing final finch fined finely finer fired firer firing fitch fivers fixate fixed fixers fixing foxed foxily furor

ghats glade glans glared glary glazed glazer glazy glebe glens glide gliders gliding glitch global globed glory glove glover gluts gnats grabens grabs grade grader gradin grape grated grater grave gravel graven graver gravid graving gravy grazed grebe gride grids grins gripe grips grove grovy grubs

habit haded hading hafiz halal haled haler halide haling halite hared haring harsh hatch hated hater hating haven haver hazed hazel hazing hejira heled heling helix helot helots heritor heron hexad hexane hider hiders hired hirer hiring hived holed honed honer horal horst hotel hovels hover hunch hutch hyrax

idola idols idyls inane inches ingle inured inwrap irade irate irony italy itched itchs itchy ivory

jabot jaded jading jalap jalopy jangle Japan japed japer Javan jehads jibed jibing jihads jingled juleps jungle jural jurat khans klaxon knaps knars knave knife knits knobs knops knots krona krone

label labors laden ladify lading ladyfy lapels larch latch lately latens later latex Latin latine lavers laxity lazed lazily lazuli leper levels levers Levite levity libels libers libido lifers lined linen liner lining lipid litany liters lived liver livery livid living lobar lobate lobed lobular lobule lonely loner loral loran loved lovely lover lunar lunch lupin lupine lupins lurch lured lurid luring luted lynched

nabob nadir natal naval navel navels nidify niter nitid nodal nopal noted novels nubile

obeli obits obols olefin olive opals opera opine orals orate orchid orchil oribi otary ovals ovary ovate ovens ovine ovoli ovule

paladin palatal palate paled palely paler paling panel papal paper papery parang parch pared parer paring parity parol patch patchy paten patina patine pavan paved paver paving pedal penal penile perch peril perorate petal peter petit pilch piled pilers piling pilots pilule pinch pined pinery pineta pining pinkly pipal piped piper pipit pitch pixel podunk polar poled porch pored puled punch purer purify pylong pylori

rabid radix radon rajah ranch rankly raped raper rapids rapine ratch rated ratels rater ratify raved ravel raven raver ravins raving razor rebate rebel rebids rebut redan redox refits rehung relate relax reline renal repave repel repin repine repot retch revel revet revile rider riding ripely ripen rivals rivel riven river rivet robed robins robing robot roper rotal rotate rotch roved rover rubify ruder ruled ruler rural

shade shadily shads shady shahs shale shaly shank shape share shark shave shaven shaver sherif sheva shined shins shiny ships shire shone shoran shove shyly slabs slang slaps slate slaty slaved slaver sleds slide sling slink slips slobs slope slops slubs slung slunk slyly slype snafu snaps snare snark snibs snipe snips snivel snore snubs spade spadix spahi spang spank spans spark spate spavin spile spiling spinal spined spinel spiny spiry spivs spore spuds spunk sputa staled stalk stanch stank starch stared stark stave stela stele sting stink stipe stola stole stony stork stove study stupa style styli

tabors talons taped taper tapir tarot taxed taxing taxon tench tenet tenor tepid tetchy tidal tided tiled tilers tinct tined tinily tirade tired tiring titer toned toner topaz torch total toxin tuber tubing tulip tuner typed

unarm unary uncle unify uniped unite units unity unshaven unshed unship unwrap urate urinal urine uteri utile

valet valeta valid valor vaned vapid vapor varix velar venal verify verily verst vetch vexed vilely vinery vinyl viper viral virile vital vivax vivid vixens vizor volar volets votary voted voter votive

whaled whaler whare whelk where whets while whined whins whiny white whity whole whore wrangle wraps wrench wretch wring write wrote wrung wryly zarape zener zibets zonal zoned zoril

---

Back to Word Ways articles
Back to Word Ways home