13,254,754 members (52,952 online)
Add your own
alternative version

Stats

39.3K views
1.3K downloads
21 bookmarked
Posted 28 Jun 2009

Solving Jumble Puzzles Using a Recursive Algorithm

, 8 Jul 2009
 Rate this:
Please Sign up or sign in to vote.
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)
{
AddPermutation(permutation);
}
else
{
for(int currentPosition = 0; currentPosition < numOfItems;
currentPosition++)
{
if(permutation[currentPosition] == 0)
{
Recursion(currentPosition);
}
}
}
itemLevel--;
permutation.SetValue(0, position);
}

private void AddPermutation(int[] currentPermutation)
{
string tempPermString = "";
foreach(int item in currentPermutation)
{
// Build string permutation from position permutation
tempPermString += inputCharSet.GetValue(item - 1);
}
permList.Add(tempPermString);
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);

//Count answers
int answersFound = permListTrue.Count();

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());
tempDisplay.AppendLine("Words Found: " + answersFound);
}
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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

 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 Pro

Comments and Discussions

 View All Threads First Prev Next
 Very nice! alejandro29A14-Jul-09 3:25 alejandro29A 14-Jul-09 3:25
 Re: Very nice! Gary Stafford14-Jul-09 17:39 Gary Stafford 14-Jul-09 17:39
 Last Visit: 31-Dec-99 19:00     Last Update: 21-Nov-17 23:37 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

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

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.171114.1 | Last Updated 8 Jul 2009
Article Copyright 2009 by Gary Stafford
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid