Recursive word search algorithm
-
14-02-2021 - |
Domanda
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)
Soluzione
What I would do is build a Tree structure. Where a Node is defined like so
public class Node {
private String data;
private int row,col;
private Node parent;
public Node(Node parent,int row,int col) {
this.parent = parent;
this.col = col;
this.row = row;
}
public boolean hasParent(int row, int col) {
Node current = this;
while((current=current.parent)!=null) {
if(current.row == row && current.col==col)
return true;
}
return false;
}
public String toString() {
Node current = this;
StringBuffer sb = new StringBuffer();
do {
sb.append(current.data);
}while((current = current.parent)!=null);
return sb.reverse().toString();
}
}
Each time you have a new starting place you want to create a new root node for the tree
for (int r = 0; r < ROWS; r++)
for (int c = 0; r < COLS; c++)
4WaySearch(new Node(null,r,c); //it is the root and has no parent
end for;
end for;
And then you want to build the tree as you go
private void FourWaySearch(Node c) {
if (c.row < 0 || c.row > ROWS - 1 || c.col < 0 || c.col > COLS - 1 || c.hasParent(c.row,c.col))
return;
else {
c.data = grid[c.row][c.col]; //get the string value from the word search grid
if(dictionary.contains(c.toString()))
foundWords.add(c.toString());
FourWaySearch(new Node(c,c.row-1,c.col));
FourWaySearch(new Node(c,c.row,c.col-1));
FourWaySearch(new Node(c,c.row+1,c.col));
FourWaySearch(new Node(c,c.row,c.col+1));
}
}
This might not be the best way to do it but to me it seems simple and easy to follow.
Altri suggerimenti
So what you need to do is first establish the grid. In this instance you have elected for 3x3 . What you need is a way to keep track of all the valid points on the grid, might I recommend an object called Point
that takes two int
s as its constructor. The next thing you need is a class that is composed of a Point
and a char
, this will enable us to see what letter is available at each Point
.
Now that we have our data structure in place we need to keep track of valid moves for the game. For instance if I am at position 3,3 (the bottom right corner, or 2,2 if you are zero based) I would need to realize that the only valid moves I have are up or left. The way to determine this is to keep a Set
of Point
s that tell me all the places I have visited, this will enable the recursive algorithm to terminate.
Some pseudocode for the recursion that may help
if(!validMovesRemaining)
return
else
removeValidPosition(pointToRemove);
captureLetter(composedObject);
recurse(pointsRemaining);
I think a tree is the way to go, but not in the way other answers seem to be using it.
What I would do would be to build a parse tree of the words you're looking for (from the dictionary) -- each letter is a node, with 26 possible children, one for each letter of the alphabet (check for null
children before recursing), and a flag saying whether it's a complete word. Check each direction, see if you can move in that direction, and move accordingly.
I was going to say that the hard part would be building the tree and it shouldn't be done recursively, but I just had another thought. The best way to build the tree is also recursive.
This is obviously just an overview, but hopefully enough to give you a start. If you get stuck again, comment and I'll see if I can push you more in the right direction.