Boggle - Player recursive backtracking need help.

[Brucesharky]

Hi.

I need some help with my recursive backtracking function for boggle. I don't know what the bug is. The board is 4X4 and i set a test case which is "thisboggleisnotw"

t h i s
b o o g
l e i s
n o t w

apparently for words like "LONE" my recursion finds until LO and stops. For "LEGIT" it goes to LEGI and stop.

I'm wondering what is the bug and why does it do that?

here's my code:

void playGame(Grid<char> &Board, Lexicon lex)
{
	 cout << "Okay, take all the time you need and find all the words you can" << endl
	 << "Signal that you've finished by entering an empty line" << endl;
	 Lexicon wordsFound;
	string userEntry = "start";
	while(userEntry!="")
	{
	 cout << "Enter a word: " << endl;
	 userEntry = ConvertToUpperCase(GetLine());
		if(lex.containsWord(userEntry) && userEntry.length()>= minWordLength && !wordsFound.containsWord(userEntry))//if is a valid english word and 4 chars or more and has not been guessed before
		{
			findPos(userEntry, Board, lex, wordsFound); // wrapper function
		}
		else if(wordsFound.containsWord(userEntry))//already chose that correct word
		{
			cout<< "You already found that word."<< endl;
		}
		else if(!lex.containsWord(userEntry)) //not english word
		{
			cout<< "That's not an english word." << endl;
		}
		else if(userEntry.length() < minWordLength) //<4 chars
		{
		cout<< "I'm sorry that word doesn't meet the requirement length." << endl;
		}
		else // if word not in boggle
		{
			cout<< "You can't make that word." << endl;

		}
	}
}

//Wrapper function
void findPos(string &userEntry, Grid<char> &Board, Lexicon lex, Lexicon &wordsFound)
{
	Grid<bool> KeepingTrack(dimension,dimension);
	string alreadyFound = userEntry.substr(0,1);
	for(int row=0; row<dimension; row++)
	{
		for(int col=0; col<dimension; col++)
		{
			if(Board[row][col] == alreadyFound[0]) //found the first char
			{
				//initialize a grid to keep track of letters used
		
				for(int r=0; r<dimension; r++)
				{	
					for(int c=0; c<dimension; c++)
					{
						KeepingTrack[r][c]= false;
					}
				}
				KeepingTrack[row][col] = true;

				if(isWordValid(alreadyFound, userEntry, Board, row, col, KeepingTrack))
				{
					wordsFound.add(userEntry);
					RecordWordForPlayer(userEntry, Human);
					break;
				}
			}
		}
	}
	/*foreach(string found in wordsFound)
	{
		cout<< found << " wordfoundsofar?"<< endl;
	}*/
	if(!wordsFound.containsWord(userEntry)) // after looping through all possible locations of first letter and can't build word
	{
		cout<< "You can't make that word!" << endl;
	}
}

	
bool isWordValid(string alreadyFound, string userEntry, Grid<char> &Board, int row, int col,Grid<bool> &KeepingTrack)
{	
	
	//Base case
	//found
	if(alreadyFound == userEntry)
	{
		return(true);
	}
	
	//Recurse
	for (int y= (col > 0 ? col-1: col); y <=(col == (Board.numCols()-1) ? col : col+1);y++)
	{
		for (int x=(row > 0 ? row-1: row); x<=(row == (Board.numRows()-1) ? row : row+1); x++)
		{
	
			if((Board[x][y] == userEntry[alreadyFound.length()]) && (KeepingTrack[x][y] == false))
			{
				col =y;//get location of currently found char
				row =x;
				KeepingTrack[x][y] = true; 
				alreadyFound = alreadyFound+userEntry[alreadyFound.length()];
				//cout<< alreadyFound << " alreadyFound" << endl;
				if(isWordValid(alreadyFound, userEntry, Board, row, col, KeepingTrack))//recursive backtracking
				{
					return true;
				}
				else
				{
					//undo moves
					alreadyFound = alreadyFound.substr(0, alreadyFound.length()-2);
					KeepingTrack[x][y] =false; 
				}
			}
		}
	}
	return false;
}