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:
Our Dictionary
We need a predicate to check if two valid words are neighbors (they differ by exactly one letter).
Check for Neighboring Words
Here is the main predicate print_word_chain:
Checking Valid Transformation
We need a helper to perform breadth-first search to trace the solution path:
Breadth First Search
When you run the program, here is the output:
Program 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!
Recent Comments