Algorithms and Data Structures I
Project 3: WordSearch
Background
In this project, you will be completing a program that searches a 2D array of chars for a user-supplied word. Your solution will need to use recursive backtracking to accomplish this.
Word searches are a popular puzzle game where players try to find words by connecting lines in a puzzle. In this Project, the word search differs from traditional searches in a few ways:
● Words can be found along any path (not just a straight line). The next letter could be in any adjacent cell to the previous letter in any of the 8 directions: North, Northeast, East, Southeast, South, Southwest, West, and Northwest.
● The puzzle edges wrap around to the other side. Thus, a letter in the last column of the 2D array can connect to a letter in the first column in the 2D array. The same goes for rows.
Exercise
A few of the methods in WordSearchPuzzle.java are already implemented. Here is a list of those methods and their functions:
● Stack| findWord(String word): the entry point to solving a word search puzzle. | findWord loops through the 2D array and checks if the target word can be found starting at the current Cell. It does this by calling the solve method for each Cell. It is your job to implement the solve method.
● Boolean isValid(int row, int col): For the given cell, return if the Cell is within the bounds of the puzzle and it hasn’t been marked as ‘visited’ . The char in a visible cell is capitalized. Thus, unvisited cells contain lowercase letters only.
● int nextRow(int row, Direction direction): Returns the index of the next row in the given direction. The Direction type is an enum declared in WordSearchInterface.java. For example, nextRow(3, Direction .S) would return 4, as row 4 is the next row directly south of row 3.
● int nextCol(int col, Direction direction): Similar to nextRow, this method returns the next column in a given direction. nextCol(2, Direction .S) would return 2 since moving south does not put you in a different column. However, nextCol(2, Direction .W) would return 1 since moving west from column 2 would put you in column 1.
● boolean isPrefix(String check, String against): Returns whether or not the last character in check is equal to the character in against at the same index. Returns false if check is longer than against. For example, check(“ban”, “banana”) returns true because n is at index 2 of each String. This method assumes that isPrefix was called at every step of building check, so that it only needs to check the last character each time. Cation: misuse of this function can lead to bugs!
You’ll also notice three incomplete methods in WordSearchPuzzle.java: solve, initialize, and getPuzzle:
● void initialize(char [] [] puzzle, int n): Initializes a new puzzle based on the given array and n, where n is the dimension of the array (n == num rows == num columns).
● char [] [] getPuzzle(): Returns a deep copy of the puzzle in fully lowercase form. Each char in the array should be copied into the new array so modifications of the clone do not affect the original.
● boolean solve(int row, int col, StringBuilder current, String wordToFind, Stack| positions): Returns whether or not a path from row, col, can complete current so that it matches wordToFind. Ex: calling solve(0, 1, “”, “example”, []) on the following puzzle should return true because the word “example” can be found starting at Cell (0, 1): |
Additionally, solve(2, 2, “cor”, “correct”, [(2,0), (1,1), (2,2)]) should return true for the following puzzle, since starting at (3, 2), we can complete “cor” to become “correct” :
Note: The solve method takes in a StringBuilder to represent the current progress on finding the goal word. This is because appending to a StringBuilder is much more efficient than appending to a regular String.
Starter Code
The starter code for this project can be found here. The starter code folder includes the following:
● WordSearch Interface .java: Interface for the WordSearchPuzzle class that you will complete.
● WordSearch Puzzle .java: The class you must complete for this assignment.
● Project3 .java: The driver program that allows a user to load puzzles from a file and search for words.
● P3Out .txt: Example output from a user running Project3.java with a completed WordSearchPuzzle class.
● 445 .txt: An example puzzle you can use for testing. Some words in this puzzle are (but not limited to):
○ recurrence
○ recursion
○ queue
○ list
○ stack
○ bag
Deliverables
You are responsible for submitting a completed WordSearch Puzzle .java file. You should not have to modify any of the starter code.
Program Input
445.txt is supplied to you as sample input. This is not the same word search puzzle that the autograder will use. You can expect the autograder to use a square word search puzzle no larger than 80x80 and for no words longer than 20 characters long.