It's time for me to write your grandmother her first Java word search program. But instead of having her do all the work by looking for words within the letter grid, a recursive function 4WaySearch
does it for her!
The only problem is:
I am finding it hard to conceptualize a recursive algorithm that builds every possible letter combination when starting at once place in the grid.
Here's code I already have written that I deem a big step in the right direction:
/*
* This is the method that calls itself repeatedly to wander it's way
* through the grid using a 4 way pattern,
* creating every possibly letter combination and checking it against a
* dictionary. If the word is found in the dictionary, it gets added to a
* collection of found words.
*
* Here an example of a 3x3 grid with the valid words of RATZ and BRATZ, but
* the word CATZ isn't valid. (the C is not tangent to the A).
*
* CXY
* RAT
* BCZ
*
* @param row Current row position of cursor
* @param col Current column position of cursor
*/
private void 4WaySearch(int row, int col) {
// is cursor outside grid boundaries?
if (row < 0 || row > ROWS - 1 || col < 0 || col > COLS - 1)
return;
GridEntry<Character> entry = getGridEntry(row, col);
// has it been visited?
if (entry.hasBreadCrumb())
return;
// build current word
currentWord += entry.getElement(); // returns character
// if dictionay has the word add to found words list
if (dictionary.contains(currentWord))
foundWords.add(currentWord);
// add a mark to know we visited
entry.toggleCrumb();
// THIS CANT BE RIGHT
4WaySearch(row, col + 1); // check right
4WaySearch(row + 1, col); // check bottom
4WaySearch(row, col - 1); // check left
4WaySearch(row - 1, col); // check top
// unmark visited
entry.toggleCrumb();
// strip last character
if (currentWord.length() != 0)
currentWord = currentWord.substring(
0,
(currentWord.length() > 1) ?
currentWord.length() - 1 :
currentWord.length()
);
}
In my head, I visualize the search algorithm just like a recursive tree traveral algorithm, but each node (entry in this case) has 4 children (tangent entrys), and the leaf nodes are the boundaries of the grid.
Also, the location of the cursor upon initial entry into the function is determined by a simple for loop psuedocoded here:
for (int r = 0; r < ROWS; r++)
for (int c = 0; r < COLS; c++)
4WaySearch(r,c);
end for;
end for;
I have been thinking about this for a while now, and trying different approaches... but I still cant seem to wrap my mind around it and make it work. Can someone show me the light? (For the sake of me and your grandmother! :D)
What I would do is build a Tree structure. Where a Node is defined like so
Each time you have a new starting place you want to create a new root node for the tree
And then you want to build the tree as you go
This might not be the best way to do it but to me it seems simple and easy to follow.