In today’s article, I want to share an interesting word puzzle, and then show how to solve it in Prolog.

Here is the puzzle:

You are given two words of the same length. You have to transform the first word into the second word, by changing only one letter at a time. The additional constraint is that each intermediate step must be a valid word!

For example, here is one way to transform “cold” to “warm”:

1) cold -> cord

2) cord -> card

3) card -> ward

4) ward -> warm

A problem such as this one can be solved in any programming language. However, usually my first choice when it comes to puzzles is Prolog. Being a declarative language with built-in support for unification and backtracking, it is ideally suited for solving such problems. You may want to read my earlier article on Prolog.

Let us get started. We need a dictionary to check whether a sequence of characters is indeed a valid English word. For the sake of this toy problem, let us limit ourselves to a few 4 letter words:

We need a predicate to check if two valid words are neighbors (they differ by exactly one letter).

Here is the main predicate print_word_chain:

We need a helper to perform breadth-first search to trace the solution path:

When you run the program, here is the output:

The program works as expected. The above program was tested in Sicstus Prolog ver 4.8 on Windows 10. You can download the code here.

Have a nice week!