Word Ladder

Abstraction is a key skill in programming - knowing which are the key features of the problem that we're trying to solve. Sometimes things that look different on the surface have deeper similarities and can employ similar solutions. I got the idea for this page when watching my son doing a word ladder puzzle in a newspaper. I realised that you could use recursive backtracking, and essentially the same method that I used for the Sudoku solver. See below for an explanation of how this page works.

Create a Ladder

Create a ladder

Enter the two words and click Go! to generate a word ladder.

NB. This page uses a list of the most common British English words. Using a longer list, e.g. legal Scrabble words, might generate a shorter ladder but it will take longer and is more likely to contain words that you don't recognise.

How Does It Work?

The solution is really like a cross between prime factorisation and Sudoku - the former in the way that it generates a first step to a solution and then repeats the process to get closer to the answer, and the latter because it uses recursive backtracking to avoid dead-ends.

The steps are essentially what you'd do if you were creating a word ladder yourself. Starting with the first word:

  1. generate a list of possible next words by swapping out each letter of the word for the other letters of the alphabet - for example, if you started with cat, then possible next words would be aat, bat, cat, dat, and so on, but also cat, cbt, cct, etc., and caa, cab, cac, etc.
  2. check the list of possibilities against the dictionary (i.e. this list) to skip any words that aren't real words or that have been used in the ladder already
  3. repeat steps 1. and 2. with each possible new word until:
    • we reach a dead end - i.e. you can't make another valid word by swapping any of the letters, or the ladder has got too long (more than ten words)
    • one of the possible words is the target word, in which case we display the ladder

In lessons we often talk about the efficiency of our algorithms, but the commands and types of data structures used can also have a big impact on performance. This is a brute force method and the number of combinations of possible words can get very large. The first version of the program checked the generated words against a list of real words stored in an array. For longer words, or where a longer ladder was required, this could take a long time - up to several minutes. Using a set rather than a list led to a very dramatic improvement in speed, with solutions taking seconds rathen than minutes.

If you're familiar with Python, then you might like to view a commented version of the Python prototype for this page (which also uses sets for improved performance). You can try tweaking the code and using different word lists - just be careful with the case!