When I visit my family at Christmas boggle is always a popular choice of game, but a year ago the physical boggle board was often abandoned for wordament. Many of my family members were quite good at the game (myself not among them), but there were always a few players that seemed to find an impossible number of words. We collectively speculated that they were cheating to save our egos, so I wrote a simple solver to find every word on a Boggle board contained in a dictionary. Source code for the project can be found here.

The short answer is, either they are not not cheating, or if they are they are doing a very bad job of it. At least as of last Christmas. I haven’t looked at any scores since then.

Implementation

The approach I used is to build a trie of words in a dictionary file, and then do an exhaustive depth first search of the board to find every valid word on the board.

The trie is structured so every node has a flag saying if it is a valid word, and a list of children.

WordTree(children: Map[Char, WordTree], val isWord: Boolean)

With this representation, simultaneous recursion over the board and the trie will find every word. The board is small enough that overflowing the stack during the search will not be an issue.

def findAllWords(prevPath: Seq[Location], subDict: WordTree): Seq[String] = {
  val subwords = pathStep(prevPath).flatMap {
    step =>
      subDict.subTree(board.pieces(step)) match {
        case Some(subSubDict) => findAllWords(prevPath :+ step, subSubDict)
        case None => Nil
      }
  }

  val thisLetter = board.pieces(prevPath.last)
  val fixedSubwords = subwords.map(word => thisLetter + word)

  if(subDict.isWord)
    thisLetter +: fixedSubwords
  else
    fixedSubwords
}

Here pathStep is a function that returns all possible next steps in a valid path, and subTree recurses down the dictionary trie. Everything at the end of the function rebuilds words from the recursive calls to findAllWords.

Performance

Solving a 5x5 board with a list of over 100 000 words took less than a second on my laptop. Assuming this list could be fed directly to the game, there is no reason an automated solver should ever miss any word. Apparently there are some people who are just mind-bogglingly good at wordament.