Dobble

Dobble is a card game of fifty-five cards, each bearing eight pictorial symbols drawn from a pool of fifty-seven. It is marketed under the trade names Dobble in Europe and Spot It! in North America, and sold as a speed-matching game: players race to identify a symbol common to two cards. The design guarantees that this common symbol always exists and is always unique — any two cards in the deck share exactly one symbol. The combinatorial feat that makes the game playable conceals a piece of classical finite geometry: a full Dobble deck is a projective plane of order seven (projective planes exist for every prime-power order).

The deck’s parameters are not arbitrary. A projective plane of order $n$ has $n^2 + n + 1$ points and the same number of lines; each line passes through $n + 1$ points, each point lies on $n + 1$ lines, and any two distinct lines intersect in exactly one point. Setting $n = 7$ gives $57$ symbols, $57$ cards, $8$ symbols per card, and the Dobble guarantee. (Commercial decks trim the full $57$ cards to $55$ for printing reasons; the mathematics works for any subset.) The existence of a plane of order $n$ is guaranteed when $n$ is a prime power, in which case the finite-field construction below applies. For $n = 6$ (not a prime power) no plane exists, by the Bruck–Ryser theorem; for $n = 10$ the nonexistence is a celebrated result of Lam, Thiel, and Swiercz ($1989$).

The Fano plane: $n = 2$

The smallest projective plane is the Fano plane, $\mathrm{PG}(2, 2)$: $7$ points, $7$ lines, $3$ points per line. Figure 10.1 shows the standard picture: a triangle, its three medians, and an inscribed circle. The three sides, three medians, and one circle together make seven lines; the three vertices, three edge midpoints, and one centroid make seven points; and any two lines meet in exactly one point.

A “mini-Dobble” with the Fano plane’s parameters has seven cards, each with three symbols; any two share exactly one symbol. The seven cards are the seven lines of Figure 10.1: the three sides $(A, D, B)$, $(A, F, C)$, $(B, E, C)$, each carrying its edge midpoint; the three medians $(A, G, E)$, $(B, G, F)$, $(C, G, D)$, each through the centre $G$; and the inscribed circle $(D, E, F)$ through the three midpoints.

The programming model

Constructing a projective plane of a given order by pure search is an exact-cover-flavoured problem with a beautifully simple encoding.

Variables

For each card $i \in \{0, \ldots, N - 1\}$ and each symbol $j \in \{0, \ldots, N - 1\}$ (where $N = n^2 + n + 1$), introduce a Boolean variable $x_{i, j}$: one if card $i$ contains symbol $j$, zero otherwise.

Card size

Each card has exactly $n + 1$ symbols: $$\sum_{j = 0}^{N - 1} x_{i, j} \;=\; n + 1, \quad i \in \{0, \ldots, N - 1\}.$$

Symbol multiplicity

Each symbol appears on exactly $n + 1$ cards: $$\sum_{i = 0}^{N - 1} x_{i, j} \;=\; n + 1, \quad j \in \{0, \ldots, N - 1\}.$$

Pairwise intersection

For every pair of distinct cards $i \neq k$, exactly one symbol is shared. Since $x_{i, j} x_{k, j}$ is the indicator that symbol $j$ lies on both cards, the constraint is $$\sum_{j = 0}^{N - 1} x_{i, j} \; x_{k, j} \;=\; 1, \quad 0 \leq i < k \leq N - 1.$$ In CP-SAT the product is linearised by introducing an auxiliary Boolean $y_{i, k, j} = x_{i, j} \wedge x_{k, j}$ and requiring $\sum_j y_{i, k, j} = 1$.

Symmetry breaking

The full automorphism group of a projective plane is enormous, so without symmetry breaking the enumerator will revisit many equivalent decks. A common break fixes the contents of card $0$: card $0 = \{0, 1, \ldots, n\}$. This pins the first card’s symbols and halves or more the search tree.

A solver in forty lines

from ortools.sat.python import cp_model

def dobble(n):
    N = n * n + n + 1
    m = cp_model.CpModel()
    x = [[m.NewBoolVar("")
          for _ in range(N)] for _ in range(N)]
    # Each card has n+1 symbols
    for i in range(N):
        m.Add(sum(x[i][j]
                  for j in range(N)) == n + 1)
    # Each symbol on n+1 cards
    for j in range(N):
        m.Add(sum(x[i][j]
                  for i in range(N)) == n + 1)
    # Any two cards share exactly one symbol
    for i in range(N):
        for k in range(i + 1, N):
            y = [m.NewBoolVar("") for _ in range(N)]
            for j in range(N):
                m.AddBoolAnd(
                    [x[i][j], x[k][j]]
                ).OnlyEnforceIf(y[j])
                m.AddBoolOr(
                    [x[i][j].Not(), x[k][j].Not()]
                ).OnlyEnforceIf(y[j].Not())
            m.Add(sum(y) == 1)
    # Symmetry break: card 0 = {0, 1, ..., n}
    for j in range(N):
        m.Add(x[0][j] == (1 if j <= n else 0))
    s = cp_model.CpSolver()
    s.parameters.max_time_in_seconds = 120
    s.Solve(m)
    return [[j for j in range(N) if s.Value(x[i][j])]
            for i in range(N)]

Timings (on a standard laptop, with the symmetry break above): $$n = 2 \text{ (Fano)}: 18 \text{ ms}; \quad n = 3: 60 \text{ ms}; \quad n = 4: 0.4 \text{ s};$$ $$\quad n = 5: 1.6 \text{ s}; \quad n = 7 \text{ (commercial Dobble)}: \approx 30 \text{ s}.$$ No projective plane of order $6$ exists, by the Bruck–Ryser theorem, and the solver confirms this by eventually returning infeasible; note though that proving nonexistence is a genuine exhaustive search, far slower than finding a plane that does exist, so the time it takes is not the fraction of a second the feasible cases enjoy. For $n = 10$ the model is beyond naive CP-SAT; the nonexistence result is Lam–Thiel–Swiercz’s $1989$ theorem, obtained by a much larger specialised search.

The algebraic construction

For $n$ a prime power $q$, the projective plane $\mathrm{PG}(2, q)$ is built directly. Points are equivalence classes of $(a, b, c) \in \mathbb{F}_q^3 \setminus \{\mathbf{0}\}$ under scaling; lines are the same, with the duality that point $(a, b, c)$ lies on line $(u, v, w)$ if and only if $au + bv + cw = 0$ in the finite field $\mathbb{F}_q$. When $q$ is prime this is ordinary arithmetic modulo $q$; when $q$ is a proper prime power the field $\mathbb{F}_q$ is needed, since the ring $\mathbb{Z}/q\mathbb{Z}$ then has zero divisors and is not a field. For $q = 7$ this assembles a full Dobble deck in microseconds, yielding the same $57 \times 57$ incidence matrix that CP-SAT recovers by search (up to permutation of rows and columns).

Sources. Projective planes entered finite geometry in the late nineteenth century through the work of Karl von Staudt and Theodor Reye; the Fano plane is named after Gino Fano ($1892$). The classical existence theorem for planes of prime power order is due to Veblen and Wedderburn ($1907$). The Bruck–Ryser nonexistence theorem ($1949$) rules out orders $n \equiv 1, 2 \pmod{4}$ unless $n$ is a sum of two squares. The nonexistence for $n = 10$ is due to Lam, Thiel, and Swiercz (Canadian Journal of Mathematics, $1989$), a major computational result that occupied several Cray years. The Bruck–Ryser theorem also rules out orders $21$ and $22$ (neither is a sum of two squares, and both are $\equiv 1, 2 \pmod 4$), so the smallest orders whose existence is currently open are $n = 12, 15, 18, 20, 24, \ldots$. The mapping of finite projective planes to a physical game of cards has a longer history than the commercial product suggests: in $1976$ the French enthusiast Jacques Cottereau devised an unpublished set of $31$ insect cards with the shared-symbol property, and in $2008$ the game designer Denis Blanchot reworked the idea into Dobble, published in $2009$.