The Wordsnake Puzzle

A Wordsnake puzzle is a list of words which must be arrange in an overlapping fashion. The entire list is called a "wordsnake", and is scored by squaring the overlaps of each consecutive pair, and adding. We allow the wordsnake to "wrap around", so there's one extra score for overlap from the last word to the first.

A wordsnake is actually a form of the traveling salesman problem, and hence, theoretically, it can be very hard to determine the maximum possible score.

The words in Dennis Shasha's challenge are:

alas	ally	blemish	blend
certain	dense	denude	eloped
emerge	essential	eternal	geriatric
gerund	icer	incredible	ingrate
invent	lasting	later	lending
merger	mishapen	pediatric	penultimate
rates	sea	seem	stinger
sudden	tense	terrestrial	terrible
tessilate	trials	trice	tricky
underdevelop	yes	yet	_

Two of the words are misspelled, but we'll work with them as they are.

Reference 1:

Dennis Shasha,
Wordsnakes,
Dr Dobb's Journal,
July, 2000, pages 143-144.

Dr Dobb's Journal web site.

I give up, show me the solution.

Back to the puzzle page.