COMP 114



COMP 114, Spring 2003

Program 5: Jumble unscrambler using backtracking

Due April 25, 2003 Programs will be accepted until 4:30pm. Late programs will be accepted until 4:30 on Monday, April 28.

Objectives

• Use backtracking to solve a problem.

• Use pruning to make backtracking more efficient.

• Use your word list objects to solve a real problem.

Word Jumbles

Word Jumbles appear on the comics page of many newspapers. They consist of four scrambled words. You have to unscramble the words and then, using the letters in the unscrambled words, solve another puzzle (often a dumb play on words). For example, one day the jumbled words were NUGOY, UNORM, ENVEAL, and NURTAT. These unscrambled to YOUNG, MOURN, LEAVEN, and TRUANT. The second puzzle, which used the letters in the underlined positions of the unscrambled words, was "What the actor hoped the play about a marathon would have." The answer is LONG RUN. We will solve only the first part: unscrambling the words.

Program

Write a program that solves word jumbles using backtracking with pruning. Your program will first read in the dictionary and construct 676 (26x26) word lists using linked lists. Just as we did in program 4, each word list will contain only words of the appropriate length and that begin with the appropriate first letter. Then the program will accept strings from the user and for each, display all the valid words that can be formed by permuting the letters of that string. For some jumbled strings, there may be more than one valid word. For example entering “opst” should generate: “stop,” “post,” and “spot.” Some solutions won’t be found because the dictionary does not contain all inflected forms of words. For example, “pots” will not appear as a solution to “opst” because while “pot” is in the dictionary, its plural, “pots,” is not. Another example: the dictionary contains “hide” but neither “hides” nor “hiding.” Don’t worry about this; your program should generate only those solutions that are in the dictionary.

Input

Your program should read the full (25,000 word) dictionary file. Valid words (all letters, and length ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download