Boggle Solver

During Summer 2017 I tried to learn clojure, as I had been curious about Lisps and it seemed like a good place to start. Additionally, Kyle Kingsbury (Aphyr), the author of the Jepsen series of blog posts (and now testing software) writes a lot of clojure, as does Tim Pope (author of many Vim plugins), so I was somewhat inspired by their examples.

My family love to play Boggle, which is a game where you try to make up as many words as possible from a 4x4 grid of letter-dice in about 2-3 minutes. I was curious as to how many words there actually were in each board, given that on a good round I normally can come up with circa 25. My friend Adam had built a boggle solver two years earlier in python, so I thought I would try my hand at it.

I had never programmed in a Lisp before, so despite having leanings towards a functional programming style in my day-to-day work, I was very unused to it (the last time I think I really used something purely functional was back at university when we had to learn ML). The resulting algorithm is, therefore, quite naïve, and could do with some optimisation.

The basic method is to cycle over the dictionary, and to try to construct each word in the board according to the boggle rules. To do this, the algorithm converts a board into a list of characters, and then proceeds to find the first character of the word to be constructed. If that character is found, it then searches its adjacent “tiles” for the next letter in the word for which we are looking. This continues until it finds the complete word, or has exhausted its options. The completed words are added to a list, along with the paths through the board used to construct them