# CSCI-1200 Homework 6 — Inverse Word Search Recursion

\$30.00

Category:

## Description

5/5 - (2 votes)

In this homework we will build an inverse word search program using the techniques of recursion. The goal
is to construct a grid of letters that one can search to find specific words. Understanding the non-linear word
search program from Lectures 13 & 14 will be helpful in thinking about how you will solve this problem.
We strongly urge you to study and play with that program, including tracing through its behavior using a
debugger or cout statements or both. Please read the entire handout before beginning your implementation.
For this assignment, you will be given the dimensions (width and height) of a word search puzzle, a set of
words that should appear in the grid (forwards, backwards, up, down, or along any diagonal), and optionally
a set of words that should not appear anywhere in the grid. Each grid cell will be assigned one of the 26
lowercase letters. Note that unlike the non-linear word search problem we discussed in class, we will only
allow words that appear in a straight line (including diagonals). Your task is to output all unique word
search grids that satisfy the requirements. Rotations and mirroring of the board will be considered unique
solutions.
Your program should expect three command line arguments, the name of the input file, the name of the
output file, and a string:
inverse_word_search.exe puzzle2.txt out2.txt one_solution
inverse_word_search.exe puzzle2.txt out2.txt all_solutions
The third argument indicates whether the program should find all solutions, or just one solution. Here’s an
example of the input file format:
4 4
+ arts
+ arid
+ east
+ rest
– ear
– at
– sit
t
e
s
t
a
r
i
d
a
r
r
s
e
a
s
t
a
r
t
s
r
e
s
t
e
a
s
t
a
r
i
d
The first line specifies the width and height of the grid. Then each line that follows contains a character
and a word. If the character is ’+’, then the word must appear in the grid. If the character is ’-’, then the
word must not appear in the grid. For this first example we show an incorrect solution on the left. Though
it contains the 4 required words, it also contains two of the forbidden words. The solution on the right is a
fully correct solution. This particular problem has 8 solutions including rotations and reflections.
Below is a second example that specifies only positive (required) words. This puzzle has 4 solutions including
rotations and reflections.
5 3
+ echo
+ baker
+ apt
+ toe
+ ore
+ eat
+ cap
e
b
a
o
r
e
h
k
t
c
a
p
o
e
o
When asked to find all solutions, your program should first output the number of solutions and then an
ASCII representation for each solution. See the example output on the course webpage. You should follow
this output closely, however your solutions may be listed in a different order. When asked to find just one
solution, your program should just output the first legal solution it finds (it does not need to count the
number of solutions). If the puzzle is impossible your program should output “No solutions found”.
To implement this assignment, you must use recursion in your search. First you should tackle the problem
of finding and outputting one legal solution to the puzzle (if one exists). Nearly full credit will be given for
submissions that do this correctly. Full credit will be given to programs that find all of the solutions.
Algorithm Analysis
For larger, more complex examples, this is a really hard problem. Your program should be able to handle the
small puzzles we have created in a reasonable about of time. You should make up your own test cases as well to
understand this complexity. Include these test cases with your submission (they will be graded). Summarize
the results of your testing, which test cases completed successfully and the approximate “wall clock time”
for completion of each test. The UNIX/cygwin time command can be prepended to your command line to
estimate the running time:
time inverse_word_search.exe puzzle1.txt out1.txt
Once you have finished your implementation and testing, analyze the performance of your algorithm using
order notation. What important variables control the complexity of a particular problem? The width &
height of the grid (w and h), the number of required words (r), the number of forbidden words (f), the
number of letters in each word (l), the number of solutions (s)? In your plain text README.txt file, write
time paint_by_pairs.out puzzle1.txt find_all_solutions > out_puzzle1_all.txt
• You may want to use a C++ code profiler to measure the efficiency of your program and identify the
portions of your code that consume most of the running time. A profiler can confirm your suspicions
about what is slow, uncover unexpected problems, and focus your optimization efforts on the most
inefficient portions of the code.
• We will be testing with and without the optional command line argument find all solutions and
will highlight the most correct and the fastest programs.
• You may submit up to two interesting new test cases for possible inclusion in the contest. Name these
tests smithj 1.txt and smithj 2.txt (where smithj is your RCS username). Extra credit will be
awarded for interesting test cases that are used in the contest. Caution: Dont make the test cases so
difficult that your program cannot solve them in a reasonable amount of time!
• In your README contest.txt file, describe the optimizations you implemented for the contest, describe
your new test cases, and summarize the performance of your program on all test cases.
• Extra credit will be awarded based on overall performance in the contest
3