Boggle game Implementation is not able to get all the words

Question

I read the board into a vector of char vector B is the 4x4 board Read the 'sorted' dictionary into a vector of strings I scan through the 4x4 board, call fillGoodWoods function for every individual cell.

    int main(int argc, char *argv[])
    {
    if ( argc < 3 )
    {
        std::cout << "\n usage : ./boggle boardfile dictionaryfile ";
        return 1;
    }
    // B is the 4x4 board
    boggle::board B;
    // this function reads the board fine
    boggle::read_board(argv[1], B);
    // read the 'sorted' dictionary into a vector
    std::vector<std::string> dict;
    boggle::read_dictionary(argv[2], dict);
    int bsize = B.size();

    std::map<std::string, unsigned int> goodwords;

    for ( unsigned int i = 0; i < bsize; ++i )
    {
        for ( unsigned int j = 0 ; j < bsize ; ++j)
        {
            std::vector<std::vector<bool> > marked;
            for (unsigned int z = 0; z < bsize; z++)
            {
                marked.push_back(std::vector<bool>(bsize, false));
            }
            std::string pathStr ;
            pathStr += B[i][j];
            marked[i][j] = true; // mark visited
            fillGoodwords(i, j, goodwords, marked, pathStr, dict, B);
        }
    }
    std::map<std::string, unsigned int>::iterator itr;


    for ( itr = goodwords.begin(); itr != goodwords.end(); ++itr)
    {
        //std::cout << itr->first << "\n";
    }
    return 0;
}

The fillGoodWords is the DFS : It has to go through every neighbouring cell that has not already been visited in the path. With a board that contains 193 words Im only able to extract 80 words

void fillGoodwords(int startrow , int startcol ,
                   std::map<std::string, unsigned int> &goodwords,
                   std::vector<std::vector<bool> > marked,
                   std::string currentStr,
                   const std::vector<std::string> &dict,
                   const boggle::board &B)
{
    if(currentStr.find("unt") == 0) {
        cout<<currentStr<<" -- ";
    }

    if (currentStr.length() >= 3)
    {
        if ( std::binary_search(dict.begin(), dict.end(), currentStr))
        {
            goodwords.insert(std::pair<std::string, unsigned int>(currentStr, 1));
        }
    }
    int boardsize = B.size();
    for ( int x = -1; x <= 1 ; ++x)
    {
        for ( int y = -1; y <= 1 ; ++y)
        {
            // checking if out of bounds
            if (  (startrow + x) < 0 || (startcol + y) < 0 || (startrow + x) >= boardsize || (startcol + y) >= boardsize )
            {
                continue;
            }
            else if (marked[startrow + x][startcol + y] == false)
            {
                marked[startrow + x][startcol + y] = true; // mark visited
                fillGoodwords(startrow + x , startcol + y, goodwords, marked, currentStr + B[startrow + x][startcol + y], dict, B);
            }
        }
    }
}

What words is it not finding? Long words? Short words? Could it be an issue with part of one word being a complete word itself? (i.e. "Train" and "Trainer" will it recognise both if both are available?) — Nic Robertson, Jan 27 '14 at 00:12
Also, http://stackoverflow.com/questions/746082 might help you out — Nic Robertson, Jan 27 '14 at 00:30
Thanks Nic. I could not classify the problem as subwords and words, like train trainer. It was a mix of words, and M Oehm found the problem. — Kim Kardashian, Jan 31 '14 at 15:52

score 3 · Accepted Answer · answered Jan 27 '14 at 08:34

You mark a cell as visited before recusing down so that it can't be used twice in the same word. But you must clear the cell for "sibling" paths after recursion has returned:

marked[startrow + x][startcol + y] = true; // mark as visited
fillGoodwords(startrow + x , startcol + y, goodwords, marked, currentStr + B[startrow + x][startcol + y], dict, B);
marked[startrow + x][startcol + y] = false; // clear again for other paths

To illustrate:

S O C K
T P X Y
A H Z E
O W N T

If you start at the S and go east to the O you eventually find SOCK. Recursion returns to the S and you explore the cell to the south. You cannot find STOCK or STOP, because the O is still marked as visible.

Boggle game Implementation is not able to get all the words

1 Answers1