Background

• I learned about Spot-It from a friend. Fun to play alone.
• Card matching game, where we can find exactly one match per card.
• My first instinct after reading the packet that stated 55 cards and 57 symbols was, there’s no way that’s optimal. Hence the fun 🐰 rabbit-hole and this post.
• Lots of variations of the game, will focus on single player Spot-It.
• This is my attempt to rev. eng. the math behind spot-it without looking at previous work for the sake of fun!
• Note: Combinatorial designs and algaebric geometry are both outside of my typical wheelhouse, I tried to present this as best as I can with my intuition, but there are many posts by mathematicians that you should check out! I will leave a couple at the end.

Math-ification

• Let’s try to define the problem such that we can find good reductions.
• A game where there are $c$ cards, $s$ symbols and exactly 1 matching symbol per pair of cards.

Difference Sets

• This is what’s known as a $(v, k, \lambda)$ combinatorial design or difference set. Where $\lambda=1$ is the number of . $v$ is the number of cards. $k$ is the number of cards containing each symbol.
  • A (v, k, A)-configuration is an arrangement of v elements $x_1, x_2, \cdots$ into v sets $S_1, S_2, \cdots$ such that every set contains exactly $\lambda$ elements in common.
  • Singer type difference set https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=522ead886d7ce8af1c34a58881548d7e5e58c639

Use spot_it_combinatorial_design.py for galois example of construction on GF.

Projective Planes

Perfect difference set: $D\subset \mathbb{Z}/m\mathbb{Z}$ if every nonzero $a \ in \mathbb{Z}/m\mathbb{Z}$ can be written unique as $a = d_i - d_j$ for $d_i, d_j \in D$.

These are large Siden set. <- important for number theory if $a+b = c+d$ for $a, b, c, d \in D$ then ${a, b} = {c, d}$.

For D to possible exist need m=n^2+n+1 and #D=n+1. n is the order of $D$.

Any PDS gives rise to a finite projective plane. $D -> $

• Take set of points by taking p = Z / (n^2+n+1)Z.
• and the lines to be the set of translates.

When do they exist? Singer -> pds of all prime power orders exist

Take $q$ prime power -> $\zeta$ generator of $\mathbb{F}_{q^3}$. $D=\{k: \zeta^k =1+a\zeta\}\mod q^2+q+1$ for $a\in \mathbb{F}_q \cup \{0\}$ is a PDS.

Cool things

• P.P. are each others duals. The symmetry of cards and symbol exists.
  • Namely: for every pair of symbols there is a unique card and for every 2 card, one symbol.
  • This can be noticed from the P.P. <-> Cyclic Difference Set symmetry
• We conjecture that these designs exist for prime powers only, but we don’t have proof. For example, https://arxiv.org/pdf/2003.04929 shows an asymptotic proof of the prime power conjecture for PDS, but even for order 12, we don’t know if there is a PDS/P.P.

SAT Solving

SAT problems

SAT, short for satisfiability, describes a set of problems that can be reduced to a boolean expression consisting of ORs and ANDs. For example, every SAT problem can be written as:

\begin{array}{cc} (a_{00} \cup \overline{a_{01}} \cup \cdots) \cap (a_{10} \cup \cdots) \cap \cdots \end{array}

Where $a_{ij}$ is a variable that takes on a boolean value (True or False), where $a_{ij}$ could be defined to be the same as $a_{nm}$. The solution to a SAT problem is to find whether a parameterization exists such that the expression evaluates to true.

Example

$E = (x \cup \overline{y}) \cap (y \cup z)$

The evaluation {x = True, y = False, z = True}

evaluates $E$ to True therefore $E$ is satisfiable.

These types of problems are $\rm{NP}$-complete when the expression is of length $N$ with clauses of length $O(1)$.

More generally, people are interested in finding (or enumerating) the parameterization(s) that results in a truthy expression.

The Z3 Theorem Prover - z3

The Z3 Theorem Prover

Other Generalizations

• If every card has the same number of symbols and every symbol appears on the same number of cards, this would be considered a “Steiner system with parameters v,k,3” or a “3-(v,k,1)-design”