13,090,678 members (42,239 online)
alternative version

Stats

38K views
21 bookmarked
Posted 28 Jun 2009

Solving Jumble Puzzles Using a Recursive Algorithm

, 8 Jul 2009
 Rate this:
Find all words that can be derived from a character string using recursion, LINQ, and COM

Introduction

In a recent article, Permutations in C# Using Recursion, I demonstrated the use of a recursive algorithm to calculate all permutations of a given set of items. The algorithm was one of three algorithms introduced in Alexander Bogomolny’s article, Counting and Listing All Permutations. The article can be found on the Interactive Mathematics Miscellany and Puzzles website. In this article and accompanying application, I will use the recursive algorithm to create a word descrambler. Based on a twist to the classic Jumble puzzle, the user inputs a string of 2 to 7 randomly ordered characters. The application will attempt to ‘unscramble’ the string by deriving all permutations of the input string and then searching for them in an English-language dictionary.

Note, you can choose to input any type of characters – letters, numbers, or symbols. All unique permutations will be returned. However, only character-only strings will be correctly identified as known words by the application.

Background

We've all seen the Jumble word scramble game in the newspaper. An example of this classic puzzle game can also be found online at UCLICKgames.com. The letters that make up a word are displayed in a random order. The goal is to rearrange the letters and discover the hidden word. Jumble puzzles normally have only one right answer. Jumble puzzles usually range from simple four-letter words to harder-to-solve six-letter words. While four letters have only 120 possible permutations, six letters have six times as many possible permutations (720), making them much harder to solve.

The application uses the recursive algorithm to solve the puzzle very similar to how we might solve it. We usually start visualizing or jotting down combinations of letters in the puzzle until we chance upon a recognizable word. Sometimes, we just ‘see’ the word right off; other times we struggle incessantly for the answer. Of course, sometimes the answer eludes us because of the limits of our vocabulary. We chance upon a word, but since we are unfamiliar with it, we discount it and continue permuting. Unlike us, the application can quickly search an entire dictionary for all possible matches.

Using the Code

To demonstrate the use of recursive algorithm to descramble a string of characters, I have created a simple Windows Forms Application. The application is built in C# 3.0, using Visual Studio 2008, on the .NET Framework 3.5. It consists of a single Windows form and a separate, small class file containing the methods, fields, and properties that define the game’s logic. As discussed earlier, the application uses Bogomolny’s original methods, which have been converted to C# from Java. The original methods, fields, and properties are renamed to create more readable, easy-to-understand C# code.

Below is the Permutations.cs class file, which contains the game’s logic. The actual source code has full commenting for each method.

```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows.Forms;

[assembly: CLSCompliant(true)]
namespace Unscramble
{
class Permutations
{
private int itemLevel = -1;
private int numOfItems;
private int permCount;
private int[] permutation = new int[0];
private char[] inputCharSet;
private List<string> permList = new List<string>();
object missing = System.Reflection.Missing.Value;

// Called directly w/o using directive to prevent ambiguity
// with System.Windows.Forms.Application object
Microsoft.Office.Interop.Word.Application wordApp =
new Microsoft.Office.Interop.Word.Application();

ProgressBar pgProgress = (ProgressBar)Form1
.ActiveForm.Controls["pbProgress"];

public void MakeCharArray(string inputString)
{
inputCharSet = inputString.ToCharArray();
numOfItems = inputCharSet.Length;
Array.Resize(ref permutation, numOfItems);
}

public void Recursion(int position)
{
itemLevel++;
permutation.SetValue(itemLevel, position);
if(itemLevel == numOfItems)
{
}
else
{
for(int currentPosition = 0; currentPosition < numOfItems;
currentPosition++)
{
if(permutation[currentPosition] == 0)
{
Recursion(currentPosition);
}
}
}
itemLevel--;
permutation.SetValue(0, position);
}

{
string tempPermString = "";
foreach(int item in currentPermutation)
{
// Build string permutation from position permutation
tempPermString += inputCharSet.GetValue(item - 1);
}
permCount++;
}

private bool CheckTheSpelling(string theWord)
{
pgProgress.Increment(1);
bool result = false;
try
{
if(wordApp.CheckSpelling(theWord, ref missing,
ref missing, ref missing, ref missing,
ref missing, ref missing, ref missing,
ref missing, ref missing, ref missing,
ref missing, ref missing) == true)
{
result = true;
}
else
{
result = false;
}
}
catch(Exception)
{
wordApp.Quit(ref missing, ref missing, ref missing);
}
return result;
}

public string OutputPermutations()
{
//Count all
int allPermCount = permList.Count();
var permListTrue = permList.Distinct();
//Count distinct
int uniquePermCount = permListTrue.Count();
pgProgress.Maximum = uniquePermCount;

permListTrue = permListTrue
.Where(perm => CheckTheSpelling(perm) == true)
.OrderBy(perm => perm);
var permListFalse = permList
.Distinct()
.Except(permListTrue)
.OrderBy(perm => perm);

StringBuilder tempDisplay = new StringBuilder();

try
{
foreach(string permutation in permListTrue)
{
tempDisplay.AppendLine(permutation + " (true)");
}
tempDisplay.AppendLine("-------------------");
foreach(string permutation in permListFalse)
{
tempDisplay.AppendLine(permutation + " (false)");
}
tempDisplay.AppendLine("-------------------");
tempDisplay.AppendLine("Total Permutations: " +
allPermCount.ToString());
tempDisplay.AppendLine("Unique Permutations: " +
uniquePermCount.ToString());
}
catch(Exception ex)
{
return ex.ToString();
}
finally
{
wordApp.Quit(ref missing, ref missing, ref missing);
}
return tempDisplay.ToString();
}
}
}```

Microsoft Word 11.0 Object Library

The application uses the spell checking capabilities of Microsoft Office Word 2003 to determine if each permutation is a recognized word. I did so adding a COM reference to the Microsoft Word 11.0 Object Library assembly to the project. If you own Microsoft Office Word 2007, you will need to add the Microsoft Word 12.0 Object Library assembly to your project. Using COM or Microsoft Word are not necessarily the best, or the only solutions. There are other applications and utilities, including freeware, which could be interfaced with the application. An alternate approach would be a web service. Each permutation or a list of permutations could be sent to a remote web service, which would provide spell checking.

To minimize memory usage, the application creates a single instance of the Word Application interface (`wordApp`) to call the `CheckSpelling(string theWord)` method for each individual permutation. When complete or when an exception occurs, the `wordApp` object is destroyed by calling the `Quit()` method. When `wordApp` is processing permutations, you will note an instance of WINWORD.EXE running in Task Manager’s Processes tab.

The Descrambler Process

1. Construct a character array from the string input by the user (ex. `cdeo` -> `{c, d, e, o}`).
2. Use the recursive algorithm to calculate each permutation of the characters based on the character’s position (example: `{1, 4, 2, 3}`).
3. Create the character permutation, by matching the numeric position-based permutation to the corresponding characters in the character array (ex. `{1, 4, 2, 3}` -> `{c, o, d, e}`).
4. Store the character permutation as a `string` in a `List<string>` object (ex. `{code}`).
5. Remove any duplicate permutations from the `List<string>`. See explanation below.
6. Use LINQ’s `Where()`extension to send each permutation in the `List<string>` to the `CheckSpelling(string theWord)` method, which in turn calls Microsoft Word.
7. Store only those permutations that have a return Boolean value from the `CheckSpelling(string theWord)` method of `true`, indicating the permutation was found in Word’s dictionary, in a second `List<string>` object.
8. Return a sorted list of all permutations to the user, with correct answer(s) listed first. Also included at the end is a summary of the results.

The recursive algorithm’s methods are very fast, while passing the results to the Word object for spell checking can be time consuming. A progress bar at the bottom of the UI is updated as each permutation is spell-checked by Word. It is important not to change windows while the application is running.

Handling Duplicate Permutations

Unlike the Console Application in the previous article, this Windows Application removes duplicate permutations using LINQ’s `Distinct()` extension. Duplicates are produced when identical characters exist in the input string, producing duplicate permutations. For example, the word ‘tester’ has two letter t’s and two e’s, which would generate 540 duplicate permutations out a total of 720 possible permutations. Permutations in the existing `List<string>` are copied to a second `List<string>` object using LINQ’s `Distinct()` extension, eliminating duplicates. See the example below, which has been foreshortened for display purposes.

Installing the Source Code

To use the source code, create a Windows Forms Application in Microsoft Visual Studio 2008 entitled ‘Unscramble’. Replace the default Form1.cs files with the source code’s Form1.cs files. Add in the Permutations.cs class file. Lastly, add a COM reference to the Microsoft Word 11.0 Object Library assembly (`Microsoft.Office.Interop.Word`). In doing so, two other assemblies, `Microsoft.Vbe.Interop` and `Interop.Microsoft.Office.Core`, will be automatically added to your project’s reference folder. If you implement an alternate spell checking method other than Word, you will need to modify the `CheckTheSpelling(string)` method.

History

• June 28, 2009 - version 1.0
• Initial version
• July 6, 2009 - version 1.1
• Rewrote the `OutputPermutations()` method to list correct answers first, and provide a better results summary
• Changed maximum input `string` length from 6 characters (720 possible permutations) to 7 characters (5,040 possible permutations)
• Updated article and article’s code references

Share

 Software Developer (Senior) Paychex United States
I am a senior software developer, architect, and project manager, specializing in .NET, JavaScript, Java, and database development, and build automation. I am currently a Lead Developer (.NET) / Developer IV for Paychex Enterprise Business Solutions. Paychex (PAYX) provides payroll, human resources, and benefits outsourcing and web-based solutions to business.

Prior to Paychex, I served as Lead Software Engineer, Operations Manager, and Technical Product Manager at Bio-Optronics. Bio-Optronics develops, deploys and operates information technology solutions to help healthcare professionals manage and optimize workflow to enhance quality, productivity, and patient and staff satisfaction and safety. Previously, I held positions of President, COO, Chief Technology Officer (CTO), and SVP of Technology for Lazer Incorporated. Lazer is a successful, digital imaging and Internet-based content management services provider.

You may also be interested in...

 Pro

 First Prev Next
 plzzzz help الياقوت الملكي17-Jul-13 13:47 الياقوت الملكي 17-Jul-13 13:47
 About Jumble to use more then 7 charater ajit chaudhary15-Jan-12 5:55 ajit chaudhary 15-Jan-12 5:55
 Very nice! alejandro29A14-Jul-09 2:25 alejandro29A 14-Jul-09 2:25
 Re: Very nice! Gary Stafford14-Jul-09 16:39 Gary Stafford 14-Jul-09 16:39
 A different approach ... Rich Leyshon29-Jun-09 23:19 Rich Leyshon 29-Jun-09 23:19
 Re: A different approach ... Gary Stafford30-Jun-09 5:02 Gary Stafford 30-Jun-09 5:02
 Re: A different approach ... supercat98-Jul-09 5:19 supercat9 8-Jul-09 5:19
 Once upon a time, I wrote a program that could take a dictionary and determine whether there existed any combination of words in the dictionary which would use each letter precisely once. The approach was similar, though I used 26 bits of a 32-bit 'long' variable to encode each word. I had 26 lists of words, based upon the most-significant set bit. I implemented a simple recursive search: check each word in the current list to make sure it doesn't have any 'disqualifying' letters; if it doesn't, mask out that word's letters from the set of letters remaining and search to see if the remaining set is solvable. Using the default usr/dict/words, there was no trouble finding workable sets, since that list includes things like the symbols of elements (C, Hg, etc.), but I didn't find those results particularly rewarding. I don't remember exactly what I came up with as results, but they tended to include "seq", "dr", and "tv". Searching for sets with a small number of extra letters would probably yield more interesting results, but would probably require a more complicated algorithm. If I still had my code, it might be interesting to hack it to ignore certain letters (e.g. produce lists of words that contain every letter but 'e' multiple times, and see which list has the fewest 'e's, then try the same thing with other vowels).
 Last Visit: 31-Dec-99 18:00     Last Update: 19-Aug-17 22:26 Refresh 1

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Web04 | 2.8.170813.1 | Last Updated 8 Jul 2009
Article Copyright 2009 by Gary Stafford