Have you ever wondered if Bananagrams is NP-complete? No? Well I think it is, and I’ll prove it!
In this post we’ll dive in to an abstract version of the game Bananagrams, prove it is NP-complete, and discuss some future extensions.
The Bananagrams Decision Problem
We will be interested in a simplified, abstract version of Bananagrams. Assume we are given tiles, where each tile can be any “letter” from an alphabet of unique letters . We can represent these tiles with a multiset , so . Consider a dictionary of ordered sequences of letters (“words”), where each letter is also from . We define a Bananagram decision problem to be the following: is it possible to make a two dimensional crossword-style grid that uses all tiles from exactly once, such that each contiguous group of letters in the grid going left to right or top to bottom is in ?
When you play Bananagrams with your family or friends, you probably sensibly set to be the Oxford English Dictionary or the Scrabble Dictionary or some common sense shared vocabulary that you definitely won’t argue over, for sure. The (English version) of the game comes with only the tiles of the English alphabet, so . During play, you frequently end up with some multiset of tiles that you need to turn into a crossword-style grid, and because the word distribution is pretty friendly the decision problem will probably evaluate to “yes”. Let’s run through a couple of quick examples here to show this clearly.
Say we have and is the Scrabble Dictionary. Then . For example, we can lay out the tiles like so:
On the other hand, if we set to be the words in the Scrabble Dictionary that contain the letter , then .
One important note: according to the official Bananagrams rules, “Any available dictionary may be used”. Therefore, we do not require any restrictions on , , or beyond what we have already stated.
What’s NP, NP-Hard, and NP-Complete?
NP, NP-Hard, and NP-Complete are complexity classes, which is a fancy way to say
they are groupings of decision problems that share a certain trait.
NP problems are decision problems that can be verified in polynomial time. That is, we can
write an algorithm that takes a potential solution to the problem and determines whether it is valid or not in time on the order of some polynomial, like or .
NP-Hard problems are problems that are “as hard” as any other problem in NP. Formally,
if a problem is NP-Hard, then we can reduce any problem in NP to
in polynomial time. A “reduction” from decision problem to means
that we are creating an instance of that has the same yes/no answer as .
Finally, an NP-Complete problem is a problem that is in both NP and is NP-Hard.
One way to prove that a problem is NP-Complete is to to prove that it is in NP
and that some other NP-Hard problem can be reduced to it in polynomial time.
This method implies the problem is in NP-Hard because we then know that we can reduce any
problem in NP to the first NP-Hard problem in polynomial time and then
that instance to our goal problem also in polynomial time. This combination of
polynomial time reductions is itself a polynomial time reduction.
Exact cover by 3-sets is an NP-Complete problem [1] with the following definition (taken verbatim from [1]):
Given a set , with (so, the size of is a multiple of ), and a collection of -element subsets of . Can we find a subset of where every element of occurs in exactly one member of ? (So, is an “exact cover” of ).
Here is an example. Consider
and
Then the answer to this decision problem is , because if we pick the only set with
then we can’t pick the only sets with and . On the other hand, if
then the answer to the decision problem is , with . We will reduce X3C to in our proof below.
Proof that is NP-complete
We will now prove that the Bananagrams decision problem is NP-Complete.
Formalizing
We will first formalize . WLOG, impose an arbitrary indexing scheme on , so . A potential solution of is a placement of each tile
in on an infinite integer grid, which we formalize by specifying unique
integer tuples , 𝕫. Let , and in a slight abuse of notation let . Then is valid iff
The grid is connected. That is, if we consider the grid as a graph , where each tile is a node and there is an edge between and if , then is connected.
Every horizontal and vertical word is in .
For every , we define a tuple as the “horizontal word” containing tile and a tuple as the “vertical word” containing tile . Formally, to define , let be the smallest integer such that for all and let be the largest integer such that for all . Then is the following tuple:
Similarly, to define , let be the smallest integer such that for all and let be the largest integer such that for all . Then is the following tuple:
Recall that , where each is a tuple of elements of . We then require if , and we require if , for all .
If a valid solution exists, then the answer to is ; otherwise it is .
The following image displays an examples of these concepts. The grid is connected,
and the highlighted horizontal (green) and vertical (red) words are all in .
is in NP
First, we show that is in NP. Consider some possible assignment , with defined the same way as above. Algorithm that can verify in polynomial time is as follows:
Verify that no tile is isolated by building a graph as described above and checking if it is connected. Such a graph can at worst be built in by looping through every two tiles and checking if they are adjacent, and if so adding an edge between them. Checking if a graph is connected is a standard operation that we can do in time .
Verify that all words are valid. We can use the following pesudocode, which
runs in polynomial time. The proof is left as an exercise to the reader (no for real it’s not too bad!).
These algorithms are thus polynomial in the sizes of and , so is in NP.
is NP-Hard
We will prove this by reducing X3C to .
Reduction definition
Recall that in the X3C decision problem we are given a set , with , and a collection of -element subsets of . The first step of our reduction is to let
Now, let and denote
Then we define as follows:
In other words (pun intended), these are the words in our dictionary :
is yes -> is yes
Assume there is some valid cover . Then we claim the following is a valid solution of the reduced Bananagrams problem:
We will make most of our analysis informally from the image here, but we could formalize it (verbosely) in terms of if necessary. The solution clearly satisfies property 1, since the tiles are part of one structure and thus form a connected graph. Moreover, property 2 is satisfied because every vertical and horizontal word is valid by our construction of above: every horizontal and vertical word is one of , , and , all of which in . Finally, this construction uses every tile in exactly once: we use each element in exactly once because is a set cover and every set in corresponds to a single word in the solution, we use copies of around the elements of , and we use copies of between words. Note that this analysis works too if is empty: the grid will contain just a single tile.
is no -> is no
First, we note that we do not need to consider the case when is the empty set, since is always yes in this case, making the left side of the if statement false. Thus we only consider cases when . In these cases, by the definition of , must contain at least tiles.
We now define a -word: a -word is a horizontal or vertical word that contains a with length greater than that is in . These are all of the form
Each of the at least tiles must be connected to the rest of the tiles in the grid in a horizontal or vertical word, which by definition is a -word. Thus, there is at least one -word in .
Next, we prove a few lemmas.
Lemma 1: In any valid solution , every tile is in a -word or adjacent to a tile in a -word. To see this, we proceed by contradiction. Say a tile is not in a -word and is not adjacent to a tile in a -word. Consider a path through the connected tile graph from to a -word. WLOG, we can assume that this path does not traverse through a -word (if it does, we can just choose that shorter path). Let be a tile along this path of distance from a -word and let be the adjacent tile to with distance from a -word. Neither nor can be adjacent to a , since then they
would be in a word. Thus, WLOG the following two possibilities are the only ones that could be valid (with other tiles in possibly other places represented by the “?” blocks):
However, must then form some part of a vertical word. However, the only words that have two letters followed by a letter from are -words, so and must in a -word, which is a contradiction. Thus our assumption is incorrect and every tile in must be in a -word or adjacent to a -word.
Lemma 2: In any valid solution , every is adjacent to a tile from (some ). There is no word in that contains both a and a , so a cannot be in a -word. Thus, by Lemma , it must be adjacent to a tile in a -word. Again, a cannot be adjacent to a tile, so it must be adjacent to an tile (the only other type of tile in -words).
Lemma 3 In any valid solution , every is in a -word. By Lemma , every is either in a -word or adjacent to a -word, so we just need to show that cannot be adjacent to a -word. By contradiction, if was not in a -word, it would need to be in a word of the form . However, this would then mean that would need to be in a -word in order for Lemma to be satisfied, but since there are no words in with both and in them this is a contradiction and every is in a -word.
Lemma 4 Every is in just one-word. Assume by contradiction that this is not the case, and some is in two -words. Since every is in a -word (Lemma ), at least two tiles next to every are not a (since s are not in -words). Since is in two -words (one horizontal and one vertical), all adjacent tiles to will not be . This leaves at most possible places for next to s. By Lemma , s can only go in these positions. Since there are tiles by the definition of , but only places to put them, this is a contradiction and the assumption must be false, and thus every is in just one-word.
Finally, we are ready to prove that is no -> is no. Assume by contradiction this was not the case, and there was some such that was no and was yes; in other words, we had a valid . We can then take the set of all -words on the board , where we let , and consider
We know that every element in occurs in at least one element of because is valid and uses all of the tiles of , and by Lemma all of the tiles in are in some -word. Furthermore, we know that no element of occurs in two sets in by Lemma . Thus, this is a valid cover for , which is a contradiction, and is no -> is no.