Please read the remarks about programming problems for this course.
A word search puzzle consists of words hidden in a rectangular block of random characters. You will complete a C++ program that reads in a list of words to find and a word search puzzle. Your program then will print the solution to the puzzle.
In class we considered two possible strategies for finding hidden words within a word search puzzle. In this assignment you will select and implement a strategy to solve a word search puzzle.
The word search program you are to complete consists of five C++ files, found here:
main
function and a function that
reads the list of words from a text file and inserts
them into a C++ std::vector
. The code
in this file loads the words, loads the puzzle from a file,
calls your solve
function,
and finally prints the puzzle's solution.
You should not modify this file.
LetterMatrix
, which represents a
two-dimensional vector of characters.
A word search puzzle and its key will be a
LetterMatrix
.
Additionally, this file provides the declaration of
several overloaded operators that work with
LetterMatrix
objects.
This type is provided as a convenience to simplify the code
you need to write.
You should not modify this file.
solve
function you are to
implement in wordsearch.cpp. The
solve
function builds the solution to a
given puzzle.
You should not modify this file.
solve
function
declared in wordsearch.h. Your task is to
implement the solve
function.
You are strongly encouraged to add helper functions to assist
solve
. Declare these helper functions
static
to limit their scope to this
wordsearch.cpp file.
These files constitute a C++ project that will build and run. You modify only the wordsearch.cpp file. Do not modify any of the other files; your code must compile and run successfully within the context of the other existing files.
You should study all the code provided, especially the code that reads data from a text file and the overloaded operator functions. You may need to write similar code yourself in the future.
The program within wspuzzle.cpp reads the list of words from a text file named wordlist.txt. The file should contain ten words, each on its own line. No word will contain more than 15 letters. The program then reads from puzzle1.puz a 20 x 20 word search puzzle with the words from the word list hidden inside.
Your program's behavior is undefined if the puzzle has no solution; this means you need not worry about this possibility.
The program produces the following output, in the following order:
Here is the output of a sample run.
It is possible that for some puzzles your program generates a correct key that is different from the correct key that someone else's program generates for that same puzzle. This especially is true if the hidden words are short. This is because a word in the list may be coincidentally duplicated in other locations within the puzzle. A proper puzzle would have only one solution. Since your program has no control over the puzzle, as long as your program produces a correct solution, your program is considered correct. You need not worry about handling multiple answers in ambiguous puzzles.
You have only one required function to write, but there is a lot of other code involved that you need to understand. You have one and one-half weeks to complete the assignment, but most students will want to set aside a few hours over several days to complete the assignment. The following represents a reasonable time schedule for this assignment:
solve
function ensure that you
can compile
and run the code provided. (0.5 hour)
Submit your completed wordsearch.cpp C++ source file to http://eclass.e.southern.edu. Be sure your name appears within a comment as the first line in each source file you submit.