COS 226 Programming Assignment #5
Due: Tuesday, March 29, 2005

Word Searching

Write a program to solve word searching puzzles, where words from a dictionary are to be found in a two-dimensional array of letters. For example, you might be given the following array:
                     m v j l i x a p e
                     j h b x e e n p p
                     h k t t h b s w y
                     r w a i n u y z h
                     p p f x r d z k q
                     t p n l q o y j y
                     a n h a p f g b g
                     h x m s h w y l y
                     u j f j h r s o a
Your program is to find words from the dictionary that can be spelled out in the puzzle by starting at any character, then moving in a straight line up, down, left, right, or on any of the four diagonals. For example, the above array contains the word algorithm because it can be spelled out by starting in the lower right corner and moving up and to the left; and it contains the word syzygy because it can be spelled out by starting at the s on the third row and moving down.

The purpose of this assignment is to give you more experience working with strings and to give you an opportunity to put to work the algorithm-design skills that you are learning.

Input format. From standard input, read the integer N, then N lines of N characters each (with each characters separated by one space), followed by the word list (one per line). You may assume that the list of dictionary words is in lexicographic order. You may also assume that both the puzzle and the dictionary consist of only lowercase letters. Finally, you may assume that all of the words in the dictionary are at least four letters long.

Output format. Print out every dictionary word (one per line) that is contained somewhere in the puzzle.

Approach. We have covered a number of different algorithms that can be used effectively to solve this problem. Your task is to study the problem; come up with a strategy for solving it using some of the algorithms and data structures that you have learned; implement and test your solution; and then explain and defend your design in the program report. A good report is particularly important for this assignment, because we expect to see a variety of solution strategies. You need to clearly explain not just what you did, but also why you did it, backed up with estimates of resource costs. Also, you should clearly explain whatever limitations you need to place on the puzzle size N and the dictionary size M. As usual, your goal is to find a decent method which works within reasonable bounds. You need not waste effort squeezing time and space out of a bad algorithm or implementing complex or highly tuned code. This problem can be solved efficiently with 200 or so lines of code (including comments and basic error checking).

Comparison of methods. We will compare all submitted programs by racing them off against each other on large (nondegenerate) puzzles.  The fastest programs will be announced in class.  Note that, although you are encouraged to write a fast program using the best design you can come up with, your grade will not depend on how well you do relative to your classmates in this friendly competition; this comparison of approaches is only meant to be a fun, communal experiment in algorithm design.

Challenge for the bored. Search for words according to the rules of Boggle, instead of just vertically, horizontally, and diagonally.

This assignment was developed by Bob Sedgewick.
Copyright © 2004.