Word Ladder Solver

It's likely that the first word ladder puzzles were created by none other than Lewis Carroll (Charles Lutwidge Dodgson), the talented British mathematician, and author of the Alice's adventures. According to Carroll, he invented them on Christmas Day in 1877.

A word ladder puzzle consists of two end-cap words, and the goal is to derive a series of chain words that change one word to the other. At each stage, adjacent words on the ladder differ by the substitution of just one letter. Each chain word (or rung of the word ladder), also needs to be a valid word. Below is an example of turning TABLE into CROWN (this time, in nine steps):

TABLE → CABLE → CARLE → CARLS → CARPS → CORPS → COOPS → CROPS → CROWS → CROWN

In another example, it take four steps to turn WARM into COLD.

WARM → WARD → CARD → CORD → COLD

(As each letter of the two words in the last example is different, this is the minimum possible number of moves; each move changes one of the letters).

Word ladders are also sometimes referred to as doublets, word-links, paragrams, laddergrams or word golf.

Longest

Obviously, it's possible to make infinitely long chains if words are allowed to be re-used (turning them into cycles), and so we can define a valid ladder as one that uses distinct steps. Further, we'll define an optimal ladder as the one that is the shortest possible way to transition from one word to another (if multiple paths are possible).

~~The longest known English word ladder is a monster 22 steps long, and is the chain that converts CHARGE to COMEDO.~~ (See Update).

CHARGE → CHANGE → CHANGS → CHANTS → CHINTS → CHINES → CHINED → COINED → COINER → CONNER → CONGER → CONGES → CONIES → CONINS → CONING → COMING → HOMING → HOMINY → HOMILY → HOMELY → COMELY → COMEDY → COMEDO

UPDATE - When I published this article, I blindly copied the above 'longest' solution from research done in 2012 but, of course, solutions are based on the dictionary used. The dictionary I am using contains 172,806 English words. This is a dictionary I have collated and merged over the years and so contains not just 'official' words but also a few colloquialisms, chemical, and medical terms. I'm sure the database used in the earlier research was not a 'loose' as mine.

It was not a surprise, therefore, that I was contacted by one of my readers, Matt Hutson, who was able to find a longer ladder. What was a surprise, was how quickly he found it! He emailed me within hours of my tool going live, with his solution for converting ORANGE to PURPLE in 25 steps.

I realised I needed to rectify this, so wrote a query to finding the longest chain using my dictionary. The winner is this 52 ladder for converting between the two seven letter words ATLASES and CABARET.

ATLASES → ANLASES → ANLACES → UNLACES → UNLACED → UNLADED → UNFADED → UNFAKED → UNCAKED → UNCAKES → UNCASES → UNEASES → UREASES → CREASES → CRESSES → CROSSES → CROSSER → CRASSER → CRASHER → BRASHER → BRASIER → BRAKIER → BEAKIER → PEAKIER → PECKIER → PICKIER → DICKIER → DICKIES → HICKIES → HACKIES → HACKLES → HECKLES → DECKLES → DECILES → DEFILES → DEFILED → DEVILED → DEVELED → REVELED → RAVELED → RAVENED → HAVENED → HAVERED → WAVERED → WATERED → CATERED → CAPERED → TAPERED → TABERED → TABORED → TABORET → TABARET → CABARET

You can find out more details on this, and other solutions, in this Follow-up article.

Try it out

Below is an applet that generates the shortest possible ladder between two words.

Longer words have more letters to change, and often it is not possible to find any solution as each intermediate step needs to be a valid dictionary word.

If a solution is possible, the first minimum length solution found is displayed. If not solution is possible, this is also explained. Below the results are statistics for the search. The number of words used in the calculation is displayed. By definition, as no letters cannot be added or removed, every step of the solution is the same length. The number of words in the dictionary of this length thus provides an upper bound for the words to be searched. The number of words examined is also displayed. This describes the number of words from the above set that were passed through in looking for a solution (or failing to find one). This number represents the size of the graph from the start word. Finally, the radius of the graph is displayed. For a puzzle with the solution, this is the number of steps. For a puzzle with no solution, this is the number of letter changes that were made before the heap petered out and no further progress is possible.