Interesting mathematical underpinnings of a favorite game. Mickey Blake Carl-Eric Menzel

Interesting mathematical underpinnings of a favorite game. Mickey Blake Carl-Eric Menzel 

Originally shared by Richard Green

The mathematics of Boggle logic puzzles

This picture shows a logic puzzle based on the popular word game Boggle. The object of the game is to place the fourteen letters shown at the bottom into the grid in such a way that the grid spells out each of the ten words in the list on the right. The words must be constructed from the letters of sequentially adjacent squares, where adjacent refers to squares that are horizontal, vertical or diagonal neighbours, and where squares may not be reused.

It turns out that Boggle logic puzzles have mathematically interesting aspects; for example, they are related to the subgraph isomorphism problem, which is an example of an NP-complete problem. The recent paper 10 Questions about Boggle Logic Puzzles by Jonathan Needleman (http://arxiv.org/abs/1506.04173) gives a survey of what is known and proposes a number (ten!) of related problems.

The paper starts with what seems like an easy challenge: construct a filling of a 3 by 3 Boggle grid that contains each of the words ACT, APE, ATE, COP, END and OLD. It is clear that the nine letters in the grid must be ACDELNOPT, but the puzzle is a lot harder than I thought it would be, and this is partly because there are only six words in the list.

If B is a Boggle grid that has been filled in with letters, Needleman defines the set W(B) to be the set of all words in the board B that are at least two letters long. Here, the term words refers to strings of letters that may or may not be valid English words. The paper also makes the simplifying assumption that each letter appearing in the grid should appear only once, like in the grid in the picture, although the paper also discusses how this second assumption may be removed.

Two boards B and B' are said to be equivalent if they produce the same list of words. It can be shown that if two boards are equivalent, it must be the case that they differ from each other only by mirror reflection or by rotation by a multiple of a right angle. [Precise statement for mathematicians: the group of automorphisms of the adjacency graph of the Boggle grid is dihedral of order 8.]

The formal definition of a Boggle logic puzzle is as a list of words P satisfying two conditions: (1) P is a subset of W(B) for some board B, and (2) if P is a subset of W(B') for some other board B', then B and B' are equivalent. For example, the assertion that “ACT, APE, ATE, COP, END, OLD” is a Boggle logic puzzle for n=3 is the claim that (1) there exists a 3x3 Boggle board that spells out all of these six words and (2) up to symmetry, there is no other Boggle board with this property. The puzzle in the picture has two letters already filled in. As well as making the puzzle easier, this also provides enough information to break the symmetry of the solution and give a unique answer.

Two of the main themes studied in the paper are minimal solutions and maximal non-solutions of Boggle logic puzzles. Theorem 3.1 says something about the minimal solutions of a 3x3 grid. What it proves is that a puzzle consisting only of three-letter words, on a board with no repeated letters, must contain at least six words. Recall the “ACT, APE, ATE, COP, END, OLD” puzzle from earlier, which contains six three-letter words and no repeated letters. The theorem then says that any list of only five three-letter words cannot possibly lead to a unique solution. One of the open questions in the paper concerns 3x3 grids with no repeated letters whose puzzles contain only two-letter words. It can be proved that one would need at least 11 two-letter words to achieve a unique solution, but it is not known if this bound is sharp, because the smallest known example of such a puzzle contains 12 two-letter words.

The maximal non-solutions arise from lists of words that lead to a puzzle that is as inefficiently long as possible. To see what this means, suppose that you have played a game of Boggle and produced a long list of words. Is it possible to reconstruct the board (up to symmetry) using only the words you have written down? How long does your list of words have to be before this is inevitable? Even on a 3x3 grid, the number turns out to be surprisingly large: one needs 137 distinct three-letter words (out of a possible total of 160) to guarantee that the puzzle can be reconstructed uniquely. For four-letter words, the number is 377 words (out of a possible total of 496).

Relevant links

The game Boggle was designed by Allan Turoff. It was originally manufactured by Parker Brothers, and is now manufactured by Hasbro. More information on the game is here: http://en.wikipedia.org/wiki/Boggle

Image source: http://www.aspenhouse21.com/gc/boggle_east.jpg

Details of the subgraph isomorphism problem: http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem

Boggle logic puzzles are reminiscent of the game Sudoku. In 2012, Gary McGuire, Bastian Tugemann and Gilles Civario proved that the smallest possible number of clues on a standard Sudoku board that can lead to a unique solution is 17. Richard Elwes has included this result in a recent blog post about his personal top 10 mathematical achievements of the last 5ish years. You can find this post at http://goo.gl/Nl7IwX. (I've abbreviated the URL because it is rather long.)

#mathematics #scienceeveryday #spnetwork arXiv:1506.04173