{"id":3573,"date":"2024-12-17T10:46:12","date_gmt":"2024-12-17T05:16:12","guid":{"rendered":"https:\/\/www.rangakrish.com\/?p=3573"},"modified":"2024-12-20T20:42:48","modified_gmt":"2024-12-20T15:12:48","slug":"using-prolog-to-solve-the-word-transformation-puzzle","status":"publish","type":"post","link":"https:\/\/www.rangakrish.com\/index.php\/2024\/12\/17\/using-prolog-to-solve-the-word-transformation-puzzle\/","title":{"rendered":"Using Prolog to Solve the Word Transformation Puzzle"},"content":{"rendered":"

In today\u2019s article, I want to share an interesting word puzzle, and then show how to solve it in Prolog<\/strong><\/em>.<\/p>\n

Here is the puzzle:<\/span><\/p>\n

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!<\/p>\n

For example, here is one way to transform \u201ccold\u201d<\/strong><\/em> to \u201cwarm\u201d<\/strong><\/em>:<\/p>\n

1) cold -> cord<\/p>\n

2) cord -> card<\/p>\n

3) card -> ward<\/p>\n

4) ward -> warm<\/p>\n

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<\/strong><\/em>. Being a declarative language with built-in support for unification<\/strong><\/em> and backtracking<\/strong><\/em>, it is ideally suited for solving such problems. You may want to read my earlier article on Prolog<\/strong><\/em><\/a>.<\/p>\n

Let us get started. We need a dictionary<\/strong><\/em> 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:<\/p>\n

\"Our<\/a>
Our Dictionary<\/strong><\/figcaption><\/figure>\n

We need a predicate to check if two valid words are neighbors (they differ by exactly one letter).<\/p>\n

\"Check<\/a>
Check for Neighboring Words<\/strong><\/figcaption><\/figure>\n

Here is the main predicate print_word_chain<\/strong><\/em>:<\/p>\n

\"Checking<\/a>
Checking Valid Transformation<\/strong><\/figcaption><\/figure>\n

We need a helper to perform breadth-first search<\/strong><\/em> to trace the solution path:<\/p>\n

\"Breadth<\/a>
Breadth First Search<\/strong><\/figcaption><\/figure>\n

When you run the program, here is the output:<\/p>\n

\"Program<\/a>
Program Output<\/strong><\/figcaption><\/figure>\n

The program works as expected. The above program was tested in Sicstus Prolog ver 4.8<\/strong><\/em> on Windows 10<\/strong><\/em>. You can download the code here<\/strong><\/em><\/a>.<\/p>\n

Have a nice week!<\/p>\n","protected":false},"excerpt":{"rendered":"

In today\u2019s 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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[17,147],"tags":[148,410],"class_list":["post-3573","post","type-post","status-publish","format-standard","hentry","category-programming","category-prolog","tag-prolog","tag-word-puzzle"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p9OLnF-VD","jetpack-related-posts":[{"id":3589,"url":"https:\/\/www.rangakrish.com\/index.php\/2025\/01\/04\/word-transformation-puzzle-part-2-implementation-in-common-lisp\/","url_meta":{"origin":3573,"position":0},"title":"Word Transformation Puzzle – Part 2: Implementation in Common Lisp","author":"admin","date":"January 4, 2025","format":false,"excerpt":"In the last article\u00a0I discussed an interesting word puzzle and showed how to solve it using Prolog. Here is the problem statement: \u201cYou 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.\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"Getting Word Neighbors","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2025\/01\/code1-300x127.jpg?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2025\/01\/code1-300x127.jpg?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2025\/01\/code1-300x127.jpg?resize=525%2C300&ssl=1 1.5x"},"classes":[]},{"id":2366,"url":"https:\/\/www.rangakrish.com\/index.php\/2021\/03\/28\/implementing-ilexicon-using-litedb\/","url_meta":{"origin":3573,"position":1},"title":"Implementing iLexicon using LiteDB","author":"admin","date":"March 28, 2021","format":false,"excerpt":"iLexicon is an \"intelligent\" dictionary that can be used to build Natural Language applications. I have two implementations, one in Lisp and another in Prolog. Both implementations are memory-based, in order to speed up performance. I have written several articles referencing it, for example see this. \u00a0 LiteDB is a\u2026","rel":"","context":"In "Natural Language Processing"","block_context":{"text":"Natural Language Processing","link":"https:\/\/www.rangakrish.com\/index.php\/category\/natural-language-processing\/"},"img":{"alt_text":"Sample Commands","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2021\/03\/Session1.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":1025,"url":"https:\/\/www.rangakrish.com\/index.php\/2018\/08\/19\/sicstus-prolog-building-a-windows-executable\/","url_meta":{"origin":3573,"position":2},"title":"Sicstus Prolog – Building a Windows Executable","author":"admin","date":"August 19, 2018","format":false,"excerpt":"In my previous post, I showed how to build a C-based Windows DLL to execute Prolog predicates in the Sicstus Prolog\u00a0engine. Today, I want to show how to build an executable (on Windows) from a C\/C++ program that uses Sicstus prolog engine. The process is quite simple. In order to\u2026","rel":"","context":"In "Natural Language Processing"","block_context":{"text":"Natural Language Processing","link":"https:\/\/www.rangakrish.com\/index.php\/category\/natural-language-processing\/"},"img":{"alt_text":"Creating WordNet Prolog Image","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2018\/08\/Creating-image.png?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2018\/08\/Creating-image.png?resize=350%2C200 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2018\/08\/Creating-image.png?resize=525%2C300 1.5x"},"classes":[]},{"id":2922,"url":"https:\/\/www.rangakrish.com\/index.php\/2022\/10\/06\/why-learn-prolog\/","url_meta":{"origin":3573,"position":3},"title":"Why Learn Prolog?","author":"admin","date":"October 6, 2022","format":false,"excerpt":"There are several programming languages in use today and a simple google search will throw up interesting recommendations of a subset of these languages to learn, usually based on popularity ranking. As is expected, the popularity of a programming language varies over time and hence a language that was in\u2026","rel":"","context":"In "Programming"","block_context":{"text":"Programming","link":"https:\/\/www.rangakrish.com\/index.php\/category\/programming\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":1727,"url":"https:\/\/www.rangakrish.com\/index.php\/2019\/09\/15\/exploring-word-patterns\/","url_meta":{"origin":3573,"position":4},"title":"Exploring Word Patterns","author":"admin","date":"September 15, 2019","format":false,"excerpt":"Working with word patterns can be an exciting (and challenging) creative activity. Such patterns come into picture while playing word games, solving word puzzles or even writing poetry. It is precisely to facilitate such tasks that I am building my \"iLexicon\" system.\u00a0 One popular word game goes like this: The\u2026","rel":"","context":"In "Natural Language Processing"","block_context":{"text":"Natural Language Processing","link":"https:\/\/www.rangakrish.com\/index.php\/category\/natural-language-processing\/"},"img":{"alt_text":"Prolog Predicates for Word Pair Generation","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2019\/09\/Code.jpg?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2019\/09\/Code.jpg?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2019\/09\/Code.jpg?resize=525%2C300&ssl=1 1.5x"},"classes":[]},{"id":534,"url":"https:\/\/www.rangakrish.com\/index.php\/2017\/05\/22\/definite-clause-grammars-dcg-in-lisp\/","url_meta":{"origin":3573,"position":5},"title":"Definite Clause Grammars (DCG) in Lisp","author":"admin","date":"May 22, 2017","format":false,"excerpt":"Definite Clause Grammars (DCG) are an elegant formalism for specifying context free grammars, and part of their popularity is due to their support in the Prolog language. Most books on Natural Language processing usually include a brief coverage of DCGs, even though Natural languages are not context-free. Because of the\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"DCG Grammar","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/05\/DCG-Grammar.png?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/05\/DCG-Grammar.png?resize=350%2C200 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/05\/DCG-Grammar.png?resize=525%2C300 1.5x"},"classes":[]}],"_links":{"self":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/3573","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/comments?post=3573"}],"version-history":[{"count":0,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/3573\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/media?parent=3573"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/categories?post=3573"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/tags?post=3573"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}