Jumble algorithm

Each clue in a Jumble word puzzle is a word that has been “jumbled” by permuting the letters of each word to make an anagram. A dictionary of such anagrams may be used to solve puzzles or verify that a jumbled word is unique when creating puzzles.

Computerized solution

Algorithms have been designed to solve Jumbles, using a dictionary. Common algorithms work by printing all words that can be formed from a set of letters. The solver[1] then chooses the right word.

First algorithm:

  1. Begin
  2. Input: J, all the jumbled letters that form an unknown W word(s)
  3. Sort the letters of J in alphabetical order, preserving duplicates
  4. Look up sorted letters in a hash table, initialised with a dictionary, that maps a sorted set of letters to unscrambled words
  5. Print the set of words, which is W
  6. End

Second algorithm:

  1. Begin
  2. Input: J, all the jumbled letters that form an unknown W word(s)
  3. Frame a word list Y with all permutations of J
  4. For each word in Y check if the word is existing in the dictionary
  5. If a match is found then collect it in word list W
  6. Print the words in W
  7. End

Algorithm to find the permutations of J:

  1. Begin
  2. Initialize a string with first character of J denoted by J(1)
  3. Add the second character of J denoted by J(2) on either side of J(1) to get two strings

J(1)J(2)


J(2)J(1)

  1. Add the third character of J denoted by J(3) on either side and in between the above 2 strings to get 6 strings

J(1)J(2)J(3)


J(1)J(3)J(2)


J(3)J(1)J(2)


J(2)J(1)J(3)


J(2)J(3)J(1)


J(3)J(2)J(1)

  1. In the same way add J(4) to each of the above strings in either sides and between two characters to get 24 strings
  2. Continue this until all the characters are completed

Though the algorithm looks complex it is easy to program.

Douglas Hofstadter developed a program called Jumbo that tries to solve Jumble problems as a human mind would. The program doesn't rely on a dictionary and doesn't try to find real English words, but rather words that could be English, exploiting a database of plausibilities for various combinations of letters. Letters are combined non-deterministically, following a strategy inspired by chemical reactions and free associations.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.