Solving Jumble Puzzles Using a Recursive Algorithm

• Download demo - 6.46 KB
• Download source - 5.13 KB

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