Boggle - Implementing Recursion

Question

So, I'm trying to figure out how to implement the recursive calls for a simulation of Boggle. There are two players: human and computer. When the human goes, s/he finds a words on the board (which was randomly shuffled), and the recursive call is supposed to check the validity. Basically, I have to loop through adjacent letters starting from index 0 of the word input, and crawl that way, checking each time to make sure the word exists or not. The problem is I don't exactly know how to do this. Here's my code thus far, and I've provided some pseudocode to further explain my intentions. Can anyone help?

#include <iostream>
#include <cctype>
#include <cmath>
#include "strlib.h"
#include "gboggle.h"
#include "graphics.h"
#include "grid.h"
#include "lexicon.h"
#include "random.h"
#include "simpio.h"
#include "Board.h"

using namespace std;

/* Constants */
const int MIN_WORD_COUNT = 4;
const int boardSize = 16;

const int BOGGLE_WINDOW_WIDTH = 650;
const int BOGGLE_WINDOW_HEIGHT = 350;

const string STANDARD_CUBES[16]  = {
   "AAEEGN", "ABBJOO", "ACHOPS", "AFFKPS",
   "AOOTTW", "CIMOTU", "DEILRX", "DELRVY",
   "DISTTY", "EEGHNW", "EEINSU", "EHRTVW",
   "EIOSST", "ELRTTY", "HIMNQU", "HLNNRZ"
};

const string BIG_BOGGLE_CUBES[25]  = {
   "AAAFRS", "AAEEEE", "AAFIRS", "ADENNN", "AEEEEM",
   "AEEGMU", "AEGMNN", "AFIRSY", "BJKQXZ", "CCNSTW",
   "CEIILT", "CEILPT", "CEIPST", "DDLNOR", "DDHNOT",
   "DHHLOR", "DHLNOR", "EIIITT", "EMOTTT", "ENSSSU",
   "FIPRSY", "GORRVW", "HIPRRY", "NOOTUW", "OOOTTU"
};

/* Function prototypes */

void welcome();
void giveInstructions();

void checkBoard( Vector<string> );
void shakeCubes( int, int, Vector<string> &, Grid<char> & );
void checkBoardLetters( Grid<char> );
void checkHumanWords( Set<string> );
void findHumanWordsOnBoard( Set<string> &, Grid<char> );
bool boardContainsHumanWord( Grid<char>, string );

void toupper(string& word);
bool askQuestion(string question);
void customConfiguration(int boardSize);
void shuffleBoard(int boardSize, const string cubes[]);
void humanTurn(Grid<char>& cubeLetters, Set<string> &alreadyUsedWords, Lexicon &dictionary);

/* Main program */

int main() {

    initGraphics(BOGGLE_WINDOW_WIDTH, BOGGLE_WINDOW_HEIGHT);
    welcome();
    giveInstructions();

    int rows = 4;
    int cols = 4;
    int boardSize = rows*cols;
    Vector<string> vec;
    Set<string> humanWords;
    Grid<char> cubeLetters( rows, cols );
    Lexicon dictionary("EnglishWords.dat");

    // Task 1: Copy constant array into a vector vec
    for( int i = 0; i < rows * cols; i++ )
    {
        vec.add( STANDARD_CUBES[ i ] );
    }

    string instructions = "Do you need instructions?";
    if (askQuestion(instructions))
        giveInstructions();

    string customConfig = "Do you want a custom configuration?";
    drawBoard( rows, cols );
    if (askQuestion(customConfig)){
        customConfiguration(boardSize);
    }
    else {
        shakeCubes( rows, cols, vec, cubeLetters );
    }
    // Task 2
    humanTurn( cubeLetters, humanWords, dictionary );

    // debug
    //checkHumanWords( humanWords );

    // Task 3
    findHumanWordsOnBoard( humanWords, cubeLetters );

    // debug
    //checkHumanWords( humanWords );


   //else {
      // shuffleBoard(boardSize,STANDARD_CUBES);
   //}
   return 0;
}

/*
 * Function: shakeCubes
 * Usage: shakeCubes( int, int, Vector<string> & );
 * -----------------
 * Randomize cubes and their sides.
 */

void shakeCubes( int rows, int cols, Vector<string> &vec, Grid<char> &cubeLetters )
{
    // Shuffle cubes
    srand ( time(NULL) );
    random_shuffle( vec.begin(), vec.end() );

    char c;
    int i = 0, j = 0;

    // Shuffle cube sides
    foreach( string s in vec )
    {
        c = s[ rand() % 6 ];
        labelCube( i, j, c );
        cubeLetters[ i ][ j ] = c;

        if( j == 3 )
        {
            i++;
            j = 0;
        }
        else
            j++;
    }
}


void humanTurn(Grid<char>& cubeLetters, Set<string> &alreadyUsedWords, Lexicon &dictionary) {
    cout << endl << "Find all the words you can."
    << endl << "Signal that you're finished by entering an empty line." << endl << endl;
    do {
        cout << "Enter a word: ";
        string word = getLine();

        if(word.empty())
            break; // the only way out of the do-while loop

        toupper(word);

        if(word.length() < MIN_WORD_COUNT) // word < min word length
        {
            cout << "I'm sorry, but we have our standards." << endl
            << "That word doesn't meet the minimum word length." << endl;
        } 
        else if(alreadyUsedWords.contains(word)) // word has already been entered
        {
            cout << "You've already found that word!" << endl;
        } 
        else if( dictionary.contains( word ) ) // word not in lexicon
        {
            alreadyUsedWords.add(word);
            recordWordForPlayer( word, HUMAN );
        }
        else
        {
            cout << "You can't make that word!" << endl;
        }
    } while(true);
}


/*
 * Function: checkBoard
 * Usage: checkBoard( Vector<string> );
 * -----------------
 * Print out current state of Boggle board.
 */

void checkBoard( Vector<string> vec )
{
    cout << endl;

    foreach(string s in vec)
    {
        cout << s << endl;
    }
}

void checkBoardLetters( Grid<char> cubeLetters )
{
    cout << endl;
    for( int i = 0; i < 4; i ++ )
    {
        for( int j = 0; j < 4; j++ )
        {
            cout << cubeLetters[i][j] << endl;
        }
    }
}

void checkHumanWords( Set<string> humanWords )
{
    cout << endl;
    foreach( string s in humanWords )
    {
        cout << s << endl;
    }

    if( humanWords.isEmpty() )
        cout << "human word set is empty" << endl;
}

// Does board contain word? RECURSIVE
bool boardContainsWord( Grid<char> cubeLetters, string word )
{

    foreach( char c in cubeLetters )
    for( int i = 0; i < cubeLetters.numRows(); i++ )
    {
        for( int j = 0; j < cubeLetters.numCols(); j++ )
        {
            if( cubeLetters[i][j] == word[0] )
            {
                if( word.length() == 1 )
                    return true;
                else
                    return boardContainsWord( cubeLetters, word.substr(1) );
            }
        }
    }

    return false;
}
/*
bool boardContainsLetter( Grid<char> cubeLetters, char letter )
{
    return false;
}

// Task 3: Reduce set of HumanWords to those that exist on board
void findHumanWordsOnBoard( Set<string> &humanWords, Grid<char> cubeLetters )
{
    foreach( string word in humanWords )
    {
        if( !boardContainsWord( cubeLetters, word ) )
           humanWords.remove( word );
    }
}
*/

/* *** Brainstorming and Under Construction ***
I need to save (x,y) coordinates and store in a Set collection class to describe path.

I need a recursive, boolean function that takes in string word, Grid board, and Set path to check valid words.
This recursion will check each adjacent letter (and can start from top left [row-1][col-1], and move around the chosen letter);
It also has to check whether it's inBounds before proceeding.


/*
 * Function: welcome
 * Usage: welcome();
 * -----------------
 * Print out a cheery welcome message.
 */

void welcome() {
   cout << "Welcome!  You're about to play an intense game ";
   cout << "of mind-numbing Boggle.  The good news is that ";
   cout << "you might improve your vocabulary a bit.  The ";
   cout << "bad news is that you're probably going to lose ";
   cout << "miserably to this little dictionary-toting hunk ";
   cout << "of silicon.  If only YOU had a gig of RAM..." << endl << endl;
}

/*
 * Function: giveInstructions
 * Usage: giveInstructions();
 * --------------------------
 * Print out the instructions for the user.
 */

void giveInstructions() {
   cout << endl;
   cout << endl << "The boggle board is a grid onto which I will randomly distribute" << endl
        << "dice.  These 6-sided dice have letters rather than numbers on the faces, " << endl
        << "creating a grid of letters on which you try to form words.  You go first, " << endl
        << "entering the words you find that are formed by tracing adjoining " << endl
        << "letters.  Two letters adjoin if they are next to each other horizontally, " << endl
        << "vertically, or diagonally. A letter can only be used once in the word. Words" << endl
        << "must be at least 4 letters long and can only be counted once.  You score points" << endl
        << "based on word length, a 4-letter word is worth one, 5-letters two, etc.  After your " << endl
        << "tiny brain is exhausted, I, the brilliant computer, will find all the remaining " << endl
        << "words in the puzzle and double or triple your paltry score." << endl << endl;
   cout << "Hit return when you're ready...";
   getLine();
}

//Function call to capitalize every letter in a string
void toupper(string& word) {
    for(int i = 0; i < word.size(); i++) {
       word[i] = toupper(word[i]);
    }
}

// A do-while loop to keep asking for a YES/NO answer to a given question
bool askQuestion(string question) {
    do {
        cout << question << " ";
        string answer = getLine();
        if(toupper(answer[0]) == 'N') return false;
        else if(toupper(answer[0]) == 'Y') return true;
    } while (cout << "Please answer yes or no." << endl);

    return 1;
}


// Requests user for a board configuration input for the given size board
// and labels the cubes with the corresponding input string
void customConfiguration(int boardSize) {
    cout << endl << "Enter a " << boardSize
         << "-character string to identify which letters you want on the cubes."
         << endl << "The first " << sqrt(double(boardSize))
         << " letters are the cubes on the top row from left to right "
         << endl << "next " << sqrt(double(boardSize))
         << " letters are the second row, etc."
         << endl << "Enter the string: ";
    string answer;
    do {
        answer = getLine();
        if(answer.size() >= double(boardSize)) break;
    } while (cout << "String must include " << boardSize
        << " characters! Try again: ");
    toupper(answer);
    int strIndex = 0;
    for (int row = 0; row < sqrt(double(boardSize)); row++){
        for (int col = 0; col < sqrt(double(boardSize)); col++){
            char answerSubStr = answer[strIndex];
            labelCube(row, col, answerSubStr);
            strIndex++;
        }
    }
}

Answer 1

Unless you need to (e.g., for homework) don't use recursion for this.

Instead, pre-process your word list into equivalents with the letters sorted. Build a multimap from sorted letters to the words you can represent with a group of letters.

When the player picks out a proposed word, sort the letters in that word, look that up in your map, and see if one of the results matches what they entered. That'll essentially always be such a small number of entries that you can do a simple string comparison for each.

Another possibility would be to build your word list into a trie. This will definitely be more work. It will almost certainly save memory, and probably make lookups minutely faster as well -- but unless you're going to run a boggle web site so the computer is going to play against thousands of people at once, that's unlikely to matter.