The Game of Dobble
We recently went out for lunch and the next generation of our relatives unpacked the game Dobble. At first I was just impressed by the speed of the little kids, but then I started thinking about the math behind the game. For those who do not know it, here is a short summary of the rules: The game consists of a deck of cards, which each display $8$ symbols. When you compare any two cards of the deck, they share exactly one symbol. During the game, two cards are revealed and whoever identifies the the duplicate symbol gets to keep the two cards.
This raises some questions, like how many symbols are in the deck or is there a limit to the possible number of cards? After fiddling around a bit, I realized that I am far from the only one interested in that. There are more detailed and mathematical explanations like this blog post, but mine focuses more on the visualization of the process.
Constructing the deck
So let's start by constructing a deck and in the process find out the limitations of the game. Our initial choice is the number of symbols per card and for the following example we pick $k=4$ (when using $8$ symbols as in the game, things quickly get cluttered). We represent the deck with a grid, where each column stands for a card and the rows represent the symbols on the card (here illustrated by number and color). The start is easy, we can simply choose the numbers $1$ to $k$ to fill the first card.
For all the following cards, we need to make sure that they share exactly one symbol with each of the existing cards. For the next block of cards, we assume that they share the $1$ with the first card. Because only one symbols is allowed to match between two cards, we have to fill the missing symbols with new unique values.
Suppose we add more than $(k-1)$ cards to this block. Once we want to add another card without $1$, it needs to contain a symbol from each of the existing cards. After we assigned a value from the first card, it only has $(k-1)$ spots left, so we can not link it to more than $(k-1)$ cards from the previous block. This limits the number of symbols to the ones from the first card plus the ones from the first block which is a square with width $(k-1)$ or in total
$$ N_\text{symbols} = k+(k-1)^2 $$
We can then repeat this step for the symbols $2$ to $k$ from the first card, leading to $k$ such blocks in total.
With $(k-1)$ cards in each block, we end up with a deck that contains
$$ N_\text{cards} = 1 + k \cdot (k-1) $$
possible cards. This number is identical to the number of symbols $N_\text{symbols}$.
Now filling the thus far empty cards with symbols and thereby connecting them to the existing cards is where things get complicated. The procedure goes as follows: starting with the second card, we select the unique values and rotate the column by $90^{\circ}$ to use it as the second row in the remaining blocks. In the case of the second block, we can do the same for the third card and so on. However, if we apply this from the third block onwards, we end up with multiple matching symbols. To avoid this, we have to shift the values. By how much depends on the source card and the destination block (see also the source code below).
This is lacking a prove why the cards in block $2$ to $k$ all overlap with exactly one symbol. Also it only works if $k-1$ is a prime number.
Code it in Python
Executing this process by hand quickly becomes annoying, but it is pretty simple to realize it in Python.
We heavily rely on the numpy package to handle the data structure, so keep in mind that the indexing in the code starts with 0.
import numpy as np
k = 8 # number of symbols per card
N = k**2-(k-1) # number of total symbols/cards in deck
print(f'{k} symbols on each card results in {N} cards')
# create an empty array where deck[:,0] represents the first card
deck = np.nan*np.zeros((k,N))
# we assign 0,...,k-1 to the first card
deck[:,0] = np.arange(0,k)
# assign values from first card to the first row in all blocks
for i in range(k):
deck[0,1+i*(k-1):1+(i+1)*(k-1)] = i
# we fill the cards 1 to k with the next (k-1)**2 numbers
deck[1:k,1:k] = np.arange(k,k+(k-1)**2).reshape((k-1,k-1),order='F')
# we fill the remaining cells by assigning the column to the rows in each block
for column in range(1,k):
for block in range(1,k):
deck[column,1+block*(k-1):1+(block+1)*(k-1)] = np.roll(deck[1:,column],(column-1)*(block-1))
We can check the result to make sure each card overlaps with every other card with exactly one symbol
from itertools import combinations
for (i,j) in combinations(range(N),2):
match = np.intersect1d(deck[:,i],deck[:,j])
if len(match)<1:
print(f'No match between card {i} and {j}')
elif len(match)>1:
print(f'{len(match)} matches between card {i} and {j}')
In order to visualize it we use matplotlib
import matplotlib.pyplot as plt
fig,ax=plt.subplots(figsize=(16.8,4))
ax.imshow(deck,vmin=0,vmax=N-1,cmap='rainbow',extent=[0,N,k,0])
# draw the grid
for i in range(k):
ax.plot([0,N],[i,i],color='white')
for i in range(N):
ax.plot([i,i],[0,k],color='white')
# write out the symbol
for (j,i),label in np.ndenumerate(deck):
ax.text(i+0.5,j+0.5,int(label+1),ha='center',va='center',fontsize=20,color='white')
ax.axis('off')
plt.show()
Applying this process to $k=8$ yields the following deck
Play the game
Congratulations, you made it to the end. As a reward, you can now play the game as long as you want. Once you found the duplicate, click on the picture and a new pair will show up.
