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

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

Document History

10/7/2009 Added an assumption about no duplicate words in puzzle.
9/24/2009 Available for Fall 2009