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 (can you see why?). It also contains the word syzygy.
For consistency, consider only words that are four or more letters long, and use the following input format: from standard input, read the integer N, then N lines of N characters each, containing the character array, then the dictionary, with words separated so that successive calls to scanf("\%s"...) read successive words. For example, if you have a file mysquare with an 8-by-8 puzzle, then the command (echo "8"; cat mysquare; cat /usr/dict/words) | a.out should print out the words in the dictionary that are in the puzzle.
We have covered 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 then explain and defend your design in the writeup. A good writeup is particularly important for this assignment, because we expect to see a variety of solution strategies. You need to explain clearly 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 N and on the dictionary size, and stick to a running time constraint of 15 seconds or so. As usual, your goal is to find a decent method that 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.
Hints. You can write and debug the scaffolding that you will need to read and write the character array, read and write the dictionary, and so forth without even thinking about the problem.
Due: 11:59PM Thursday, March 23.