Dobble Deck Generation

Dobble is a card game that uses a special deck of cards that has an interesting mathematical property. There are 55 cards, each with 8 distinct symbols on them, and for any to cards you pick from the deck there will be one and only one symbol matching. Part of what makes the game so fun is how well designed these symbols are to trip you up whether you try matching on colour, shape or name, but that's not as mathematically interesting! How to generate a deck of cards with that property is.

I'll also add to that property to keep things interesting - the case where all cards share the same symbol is trivial and boring, both mathematically and as a game. So we'll ignore it.

What follows is an explanation of a deck generation algorithm for a Dobble-like deck of cards. It may well not be the only way to do it, but it does provably work for Dobble itself and for any deck with N + 1 symbols per card, where N is prime. (I don't have the patience to find a second algorithm for N not prime, if it exists.)

Grouping The Deck

The first question to consider is how many cards can you create if you have N + 1 symbols. (The reason I'm using N + 1 will be obvious soon, I promise.) Assume that you already have such a deck. Also assume that you have an even distribution of symbols. I'm not saying that every possible deck has this property, but the one we're generating does, and the real Dobble deck does with the exception it's got a couple of cards missing.

Pick a card, any card. It's got N + 1 symbols on it. Sort the rest of the deck into N + 1 groups, where each group contains cards that match one of the original symbols. For an evenly distributed deck, you'll have N cards in each group, each with one (and only one) of the symbols from the original cards, and then N new distinct symbols. Consider one of the groups - each card has 1 matching symbol, and then N other symbols, all distinct. These other symbols are then reused across the other groups. So there are N * N other symbols, plus the original N + 1 symbols, which actually simplifies to N(N + 1) + 1 as well. For a practical example, let's take N = 2, i.e. there are 3 symbols on every card. We'll use letters for symbols for now, that will have to change later as things get more complicated!

First card: {A, B, C}
Group A: {A, D, E}, {A, F, G}
Group B: {B, D, F}, {B, E, G}
Group C: {C, D, G}, {C, E, F}

Now, remove the symbol that the group's named after, and you have N + 1 groups of N cards with N symbols on each card.

Group A: {D, E}, {F, G}
Group B: {D, F}, {E, G}
Group C: {D, G}, {E, F}

The properties these groups have:

1. Each group's cards are completely distinct from each other, there are no matching symbols at all
2. If you pick one card each from any two groups, they will match one and only one symbol

So why are we doing this? Because if we can generate these groups then we can generate a deck by adding an extra N + 1 symbols. And often the only way to attack a problem is to break it down into a different problem that you can actually solve.

Generating The Groups

Before we start, I'm going to do a sleight of hand. I'll switch the example to N = 3, and also change notation on you. It's mean to do half way through, but the clearest way to show what's going on. So I'm going to name the groups with greek letters, and the generation will give each symbol a letter and a number.

Take one of the groups, and we'll call it the "seed group", because we'll use it to generate the others. I'll name each card after a letter of the alphabet (lower case), and then each symbol on that card will be determined by the card name and its order, like so:

Card a b c
Group/Position 0 1 2 0 1 2 0 1 2
seed A0 A1 A2 B0 B1 B2 C0 C1 C2

Now we need N more groups. The first one is simple enough - take one symbol from each seed card and we're sorted:

Card a b c
Group/Position 0 1 2 0 1 2 0 1 2
seed A0 A1 A2 B0 B1 B2 C0 C1 C2
α A0 B0 C0 A1 B1 C1 A2 B2 C2

Now we need a way to generate the other groups. For each group, give it a numerical "offset", which is the difference between the numbers on consecutive symbols, where those numbers are modulo N. I.e. if your offset is 2 and N = 3, then you start with 0, then go to 2, then go to 4 which is 1 mod 3. That gives us:

Card a b c
Group/Position 0 1 2 0 1 2 0 1 2
seed A0 A1 A2 B0 B1 B2 C0 C1 C2
α (offset = 0) A0 B0 C0 A1 B1 C1 A2 B2 C2
β (offset = 1) A0 B1 C2 A1 B2 C0 A2 B0 C1
γ (offset = 2) A0 B2 C1 A1 B0 C2 A2 B1 C0

If we give the seed group a greek letter too, let's say φ because it looks like a seed, then the full deck that you'd generate from these groups can be described as:

First card: {α, β, γ, φ}
Group φ: {φ, A0, A1, A2}, {φ, B0, B1, B2}, {φ, C0, C1, C2}
Group α: {α, A0, B0, C0}, {α, A1, B1, C1}, {α, A2, B2, C2}
Group β: {β, A0, B1, C2}, {β, A1, B2, C0}, {β, A2, B0, C1}
Group γ: {γ, A0, B2, C1}, {γ, A1, B0, C2}, {γ, A2, B1, C0}

By inspection (fancy way of saying "by looking at it carefully"), that algorithm works for N = 3. If you try it for N = 4, you'll see it fails - the rows with offset 0 and 2 start getting some cards where there are too many symbols overlapping. So how do we know whether this algorithm is any good?

The Maths

Warning: this contains modular arithmetic. I can never remember how modular arithmetic works, but the wikipedia page is a neat crib sheet. Simple version is that you use ≡ to mean that two things are equal modulo something, and you can do regular additions, subtraction and multiplication around it (but not division) as long as you're dealing with integers. To save me typing, assume every ≡ below is modulo N.

So let's define our groups, cards and position in the card numerically. Letters convert to 0-based numbers, e.g. A and α are 0, B and β are 1 etc. I didn't start with this because it's seriously confusing. Then each symbol's name becomes a kind of two dimensional co-ordinate referring to the seed row. B2 becomes 1-2, the symbol that's in position two on the card 1 in the seed row.

Card 0 1 2
Group/Position 0 1 2 0 1 2 0 1 2
seed 0-0 0-1 0-2 1-0 1-1 1-2 2-0 2-1 2-2
group 0 0-0 1-0 2-0 0-1 1-1 2-1 0-2 1-2 2-2
group 1 0-0 1-1 2-2 0-1 1-2 2-0 0-2 1-0 2-1
group 2 0-0 1-2 2-1 0-1 1-0 2-2 0-2 1-1 2-0

Each card's symbol then is defined as $m$-$n$ for some $m$ and $n$ that are integers between 0 and N - 1. We can come up with a formula for $m,n$ based on the card's group, the card number and the symbol's position in the card if we define them as $i,j,k$ respectively: $$m = k$$
$$n ≡ ik + j \;\; (mod N)$$

From earlier, the properties we need the groups to have in order to use them to build a Dobble-like deck are:

1. Each group's cards are completely distinct from each other, there are no matching symbols at all
2. If you pick one card each from any two groups, they will match one and only one symbol

NB: I'm only looking at the non-seed groups from here on. The seed group clearly satisfies both properties with all other groups by construction.

Picking two cards is simply picking two $i,j$, so let's call those $i_0,j_0$ and $i_1,j_1$ and we'll look at each $k$ on the card, leading to $m_0,n_0$ and $m_1,n_1$. So our properties can expressed as:

1. Where $i_0 = i_1$, $m_0,n_0 ≡ m_1,n_1$ iff $j_0=j_1$ for any value of $k_0,k_1$
2. Where $i_0 ≠ i_1$, for any given $j_0,j_1$ there exists one and only one pair of $k_0,k_1$ such that $m_0,n_0 ≡ m_1,n_1$

$m_0 = m_1$
$⇒ \; k_0 = k_1$

and

$n_0 = n_1$
$⇒ \; i_0 k_0 + j_0 ≡ i_1 k_1 + j_1$
$⇒ \; j_1 - j_0 ≡ k(i_0 - i_1)$

In the case of the first property, if $i_0 = i_1$, then so must $j_0 = j_1$, so it holds.

In the case of the second property, $i_0,i_1,j_0,j_1$ are fixed and $k$ is still a variable - while the $k$ must be the same for the symbols to match, the property means that we fail if there are two or more such $k$s, e.g. if the first and second positions match on the same pair of cards. So we can reduce that last equivalence to $r ≡ kq$ for $q,r$ as integers in the range 0 to N - 1, and state that the second property holds iff there is only one $k$ that satisfies the equation for a given $q,r$. Assume that isn't true for the moment, and there are two such $k$s, then $k_a q ≡ r ≡ k_b q$ ⇒ $q(k_a - k_b) ≡ 0$. $k_a = k_b$ is the one and only one case we're allowing, and we've already ruled out the possibility of $q$ being 0 as $i_0 ≠ i_1$. There is another possibility though (since this is modular arithmetic) - that $q$ and $k_a - k_b$ are factors of N. The factors of N itself and 1 don't count - neither of those can be N by definition, they are N - 1 at their maximum. So we're left with the fact that if N is prime then there can only be one possible value of $k$ and the property holds. Otherwise, the property fails.

Hence the algorithm generates viable groups iff N is prime.

Some Code

If my attempt at a wordy description of the algorithm is confusing, some code might be helpful. Here you go, it's a Java implementation I wrote that generates and then checks a Dobble-like deck. I've only run it up to a point because I'm lazy and can't be bothered to make the checker efficient or look at whether a number is prime, but as reference code it serves its purpose.