CSC 427: Data Structures and Algorithm Analysis
Fall 2004

HW6: Hash Sets and Backtracking

Boggle (® Hasbro) is a game in which a 4x4 grid of letters is randomly chosen, and then the players try to identify as many words in that grid as possible. Words can be formed by any sequence of adjacent letters in the grid. For example, consider the following grid.

c k s z x o t h d g r n z n a m

The word "sock" is formed starting at the letter "s" in the top row, moving down diagonally to the "o", moving up diagonally to the "c", and finally moving right to the "k". Note that letters can be connected horizontally, vertically, and diagonally. The same occurrence letter may not be used more than once in the same word, however. Thus, "tot" is not a valid word in the above grid. A player earns points for each word found in the grid, with an n-letter word earning n points. For example, "so" is worth 2 points while "strand" is worth 6 points.

Your program should have the following features:

An online dictionary of words is provided for you in the file dict.txt. Since this file contains over 58,000 words, efficient storage and access is imperative. You should use a hash_set to store and search for words as needed.

Sample execution:

Welcome to Dave's online Boggle game. I will show you a 4x4 grid of letters, and you are to find as many words as you can by connecting letters in the grid (you can connect letters horizontally, vertically, or diagonally). The longer the word, the more points you earn. Let's play: l s q t r v k b v u m w k k a w Enter your words (terminate with '*'): ma CORRECT! 2 points. maw CORRECT! 3 points. skum THERE IS NO SUCH WORD. -1 point. rum CORRECT! 3 points. maw YOU ALREADY GOT THAT WORD. mum THAT WORD IS NOT ON THE BOARD. -1 point. * TOTAL SCORE = 6 Do you want to see the words you missed? (y/n) y a am auk mu

Hint 1: Think OOP. For example, instead of just representing the grid of letters as a 2-dimensional array or vector, define a class (e.g., BoggleBoard) that combines the grid with its basic operations. Such modularity will help to manage the complexity of the program.

Hint 2: Since you will have to display all of the valid words in the grid at the end (at least those not entered by the user), it probably makes sense to find all of the valid words up front and store them in a hash_set. The grid can be searched via recursive backtracking, using the functions below.

bool BoggleBoard::contains(string word) { for (int r = 1; r <= BOARD_SIZE; r++) { for (int c = 1; c <= BOARD_SIZE; c++) { if (contains(word, r, c)) { return true; } } } return false; } bool BoggleBoard::contains(string word, int r, int c) { if (word == "") { return true; } else if (board[r][c] != word[0]) { return false; } else { char safe = board[r][c]; board[r][c] = '*'; string rest = word.substr(1, word.length()-1); bool result = (contains(rest, r-1, c-1) || contains(rest, r-1, c) || contains(rest, r-1, c+1) || contains(rest, r, c-1) || contains(rest, r, c+1) || contains(rest, r+1, c-1) || contains(rest, r+1, c) || contains(rest, r+1, c+1)); board[r][c] = safe; return result; } }