Word Search Puzzle Solver
CSc 103 Programming Project
The goal of this project is to write a Java program to solve "word
search" puzzles as described on page 2 of Weiss.
Objectives
The objectives of this assignment are
- to review and apply programming concepts from CSc 102:
two-dimensional arrays, generics, for-each loops, and enumerated types.
- to review and practice software development skills: reading API
javadocs, implementing a class specification, applications with
multiple components, unit testing, and JAR files.
Overview
Word Search Puzzles are popular pencil-and-paper word puzzles.
Read page 2 of Weiss for a description.
Here are some example Word
Search Puzzles online.
The input to the program is a single text data file containing the
puzzle and the words to be found. Here is an example data file. The output is
the list of words and where they were found in the puzzle. Our
solution will use a "brute-force" approach, exhaustively trying all
possibilities. Weiss proposes two different strategies; you may
use either, or invent one of your own. You may not
use the web or other resources to find a solution; you must write your
own solution.
Software Design
The instructor has written the "front end" of the application.
You are provided the working .class file for PuzzleUI
that reads the data file, calls the solver, and outputs the
results. Your assignment is to write the solver component.
Your component does no input or output to the user.
Here are the Javadoc for the instructor supplied components.
PuzzleUI
PuzzleWord
PuzzleWord.Directions
Natural
Here is the javadoc for the module you must implement. Your
public interface must match the class specification exactly.
WordSearchSolver
Here are the .class files for the instructor components, (not
the source code), in a
JAR formatted file: WordSearch.jar
Compiling your module on CSL Unix server (unix1.csc.calpoly.edu)
Download the WordSearch.jar file into your working directory.
wget
http://www.csc.calpoly.edu/~jdalbey/103/Projects/WordSearch/WordSearch.jar
Compile your module
javac -classpath .:WordSearch.jar WordSearchSolver.java
Execute the application
java -classpath .:WordSearch.jar PuzzleUI
puzzletestdata1.txt
Compiling your module with BlueJ
Create a directory in your BlueJ project folder named +libs
and place WordSearch.jar
in that new directory. Now you can create
your own class and compile it as normal. For complete directions
about importing external JAR files, see sections 9.10 and 9.11 in the BlueJ Reference
Manual (pdf). You do not need to unzip the jar file.
You do not need the individual .class files. If you find yourself
unarchiving WordSearch.jar, you are doing it wrong. If you've read
sections 9.10 and 9.11 and still don't understand, see the instructor.
To execute the application, select Tools -> Use Library Class.
Type "PuzzleUI" in the Class field and press enter. The
constructor and main method will appear in the list. Double-click
the main method. The argument list dialog appears. Type the data
file name in quotes inside the braces. Press enter and the
application will execute.
For more info, see the BlueJ Reference
section 9.12.
Input Requirements
The program will assume:
The puzzle will always be a square. The first line of the data
file gives the dimensions of the puzzle (a positive integer).
The maximum size puzzle is 80 x 80.
The puzzle letters will be uppercase.
The word list may be lower or mixed case.
The words may contain leading or trailing blanks.
The words will be comprised of alphabetic characters.
The words will be at least two characters long.
The word list will not contain blank lines.
All the words in the list must be in the puzzle.
The word list will not contain duplicate words (or redundant phrases).
(E.g. it won't contain both BAG and RUTABAGA)
Each word will appear only once in the puzzle.
Output Requirements
The list of puzzlewords returned by WordSearchSolver must be in the
same order as the words provided to the constructor. The words must be
uppercase.
Design Constraints
There must be no redundant code in your solution.
That is, no statement may appear more than once. Specifically, it's not
acceptable to write eight
separate blocks of code that check the eight directions,
because the code in each block will be nearly identical to the code in
the seven other blocks.
Sample Execution
Here is an example execution on Unix of the instructor's solution of
this sample puzzle.
>java
-classpath WordSearch.jar:. PuzzleUI
wordsearchdata5.txt
LIST
4 5,8 left
SET
3 3,5 down
GRAPH
5 7,4 up
STACK
5 5,6 left
QUEUE
5 4,9 left
TREE
4 5,5 downright
>java
-classpath WordSearch.jar:. PuzzleUI
wordsearchdata5.txt -timing
Elapsed time (secs): 0.047
LIST
4 5,8 left
SET
3 3,5 down
GRAPH
5 7,4 up
STACK
5 5,6 left
QUEUE
5 4,9 left
TREE
4 5,5 downright
Testing
Your WordSearchSolver class will be tested with instructor reference
tests. The reference tests are JUnit tests of your class.
PuzzleUI is not used in testing.
Here is a sample JUnit test:
public void testOneHorizontal()
{
ArrayList<String> wordlist = new
ArrayList<String>();
char [][] board = { {' ',
' ',' ',' '},
{' ', 'C','A','T'},
{' ', 'X','Y','Z'},
{' ', 'J','K','L'}};
wordlist.add("CAT");
WordSearchSolver ws = new
WordSearchSolver(3, board, wordlist);
ArrayList<PuzzleWord>
results = ws.findwords();
assertEquals("wrong number
of results",1,results.size());
}
On this project the
grader will penalize for non-conformance to the class coding standard,
and it will run your own unit tests. Your unit tests
must demonstrate "statement" coverage (they cause every
statement in your program to be executed.)
Handing in Your Source
Electronically
- Submit your source code and unit tests to Web-CAT.
- You might be curious to know the number of lines of code in your
file. On unix1, enter this command:
~graderjd/bin/countloc WordSearchSolver.java
- The instructor's solution is 37 LOC.
Document History
10/7/2009 Added an assumption about no duplicate words in puzzle.
9/24/2009 Available for Fall 2009