The Third SET Card: Mod 3 Pair Completion and the 1,080 SETs

Any two distinct SET cards determine exactly one third card. The rule requires each feature across the three cards to be either identical or different on all three. Encode the values as 0, 1 and 2, and the rule becomes a sum of zero modulo 3. The missing card is therefore c = −(a+b) mod 3, calculated separately for each feature.

That gives 1,080 SETs in the full deck of 81 cards, with 40 containing any given card and exactly one containing any given pair. On a table of 12 cards, pair completion needs at most 66 lookups to decide whether a SET exists; roughly 3% of randomly drawn 12-card layouts have none.

Rules and encoding

SET has 81 cards, each with four features: colour, shape, number and shading. The rule applies to each feature separately, so a valid SET can have identical colours and different numbers.

Each of the four features has three possible values, and the deck contains every combination, giving 81 = 3^4 cards. Label each feature’s values 0, 1 and 2, and each card becomes a tuple of four digits, or a point in (Z₃)⁴.

For one feature, let the values on the three cards be x, y and z. The possible cases account for the whole rule:

Relationship between the values	What happens to the sum
All identical	The sum is 0, 3 or 6, each divisible by 3
All different	The values must be 0, 1 and 2, so the sum is 3
Two identical, one different	If x is repeated and y differs, `2x+y ≡ y−x (mod 3)`, which cannot be zero

So a feature passes exactly when x+y+z ≡ 0 (mod 3). Apply that test to all four positions in the tuples and there is no need for separate branches for identical and different values.

The third card is unique

Rearranging a+b+c ≡ 0 (mod 3) gives c ≡ −(a+b) (mod 3). Each coordinate has a unique answer, which fixes the whole card.

The completed card cannot duplicate either input. If c equalled a, the equation would read 2a+b ≡ 0 (mod 3), forcing b ≡ a (mod 3). That contradicts the choice of distinct cards. The same argument rules out c equalling b.

There are C(81,2) = 81×80/2 = 3,240 pairs in the deck. Each SET contains three pairs, so counting pairs counts each SET three times: 3,240/3 = 1,080. Fix a single card and it has 80 possible partners. Each SET containing that card accounts for two of those partners, giving 80/2 = 40 SETs per card.

The same count can be written as 81×80/3! = 1,080.

Counting triples and completing pairs

There are only 85,320 triples in the deck. The complete set_count.py script tests each one using the modulo condition derived above, then compares the count with pair completion:

# SET: 81 cards = every point of (Z_3)^4 (four features, three values each).
# Three cards form a SET iff for every feature the values are all equal or all different,
# which is the same as summing to 0 mod 3. Hence for any two cards the third is unique:
# c = -(a + b) mod 3, feature by feature.
# Count all SETs two ways and time them.
from itertools import product, combinations
import time

cards = list(product(range(3), repeat=4))

def is_set(a, b, c):
    return all((x + y + z) % 3 == 0 for x, y, z in zip(a, b, c))

def third(a, b):
    return tuple((-x - y) % 3 for x, y in zip(a, b))

t0 = time.perf_counter()
by_triples = sum(is_set(*tri) for tri in combinations(cards, 3))
t_triples = time.perf_counter() - t0

t0 = time.perf_counter()
pairs = list(combinations(cards, 2))
by_pairs = {frozenset((a, b, third(a, b))) for a, b in pairs}
t_pairs = time.perf_counter() - t0

print(f"cards={len(cards)}  triples C(81,3)={len(list(combinations(cards, 3)))}  pairs C(81,2)={len(pairs)}")
print(f"SETs by enumerating triples: {by_triples}  ({t_triples * 1000:.0f} ms)")
print(f"SETs by completing pairs:    {len(by_pairs)}  ({t_pairs * 1000:.0f} ms)")
print(f"check: 81*80/6 = {81 * 80 // 6};  each card in {len(by_pairs) * 3 // 81} SETs;  pairs / 3 = {len(pairs) / 3:.0f}")
print("every completed triple really is a SET:", all(is_set(*s) for s in by_pairs))

cards=81  triples C(81,3)=85320  pairs C(81,2)=3240
SETs by enumerating triples: 1080  (28 ms)
SETs by completing pairs:    1080  (3 ms)
check: 81*80/6 = 1080;  each card in 40 SETs;  pairs / 3 = 1080
every completed triple really is a SET: True

The triple method visits all 85,320 candidates and calls is_set on each. That function tests the four features, stopping as soon as one fails. The pair method visits 3,240 pairs and calculates their third cards. A frozenset represents each completed group without an ordering, and the outer set removes repeated groups.

Both methods find 1,080 SETs, and every completed group passes is_set. Keep the exhaustive version as a regression check when changing the pair search. The per-card figure printed above is an average calculated from the total; the pairing proof establishes that it holds for every card.

The triple search took 28 ms and pair completion took 3 ms, including the time to build the pair list and the collection of distinct groups. These come from one run on a Mac, so the ratio may not hold elsewhere.

Finding a SET by completing pairs

For a table of n cards, completing a pair still produces exactly one candidate. It may simply be absent from the table. Put the layout in a Python set, then test membership for each completed card; a lookup takes O(1) time on average.

Cards on the table	Candidate triples	Maximum pair lookups
12	`C(12,3) = 220`	`C(12,2) = 66`
15	`C(15,3) = 455`	`C(15,2) = 105`

The search stops at the first SET and checks every pair only when none exists. no_set_probability.py samples 200,000 layouts of each size with seed 42, using 1.96 × sqrt(p×(1−p)/T) as the half-width of an approximate 95% confidence interval:

# Probability that a random layout of 12 (or 15) cards contains no SET, by Monte Carlo (seed 42).
# Finding a SET in a layout of n cards costs C(n,2) lookups with the "third card" trick
# instead of C(n,3) triple checks.
from itertools import product, combinations
import random, math

random.seed(42)
cards = list(product(range(3), repeat=4))

def third(a, b):
    return tuple((-x - y) % 3 for x, y in zip(a, b))

def has_set(layout):
    s = set(layout)
    return any(third(a, b) in s for a, b in combinations(layout, 2))

T = 200_000
for n in (12, 15):
    none = sum(not has_set(random.sample(cards, n)) for _ in range(T))
    p = none / T
    ci = 1.96 * math.sqrt(p * (1 - p) / T)
    print(f"{n} cards: P(no SET) = {p:.4f} +/- {ci:.4f}   lookups per layout: C({n},2)={math.comb(n, 2)} vs C({n},3)={math.comb(n, 3)}")

12 cards: P(no SET) = 0.0317 +/- 0.0008   lookups per layout: C(12,2)=66 vs C(12,3)=220
15 cards: P(no SET) = 0.0004 +/- 0.0001   lookups per layout: C(15,2)=105 vs C(15,3)=455

Each call to random.sample draws n distinct cards from the full deck of 81, so the probabilities apply to independent fresh deals. The early return in has_set comes from any; 66 and 105 are the maximum lookup counts.

About 3.17% of the 12-card layouts have no SET, with a margin of about 0.08 percentage points. For 15 cards that falls to 0.04%, with a margin of about 0.01 percentage points.

The estimate is also close to Norvig’s simulation.¹

Is it worth optimising a 12-card table

Testing 220 triples on a table of 12 cards is straightforward enough for a first implementation. If search becomes a bottleneck, measure what reducing the candidate count to 66 saves, including the cost of building the lookup set. The timings above cover the full 81-card deck; a 12-card table needs its own measurement.

A practice generator can reuse the sampling loop: pass each draw to has_set, discard it if there is no SET, and deal an accepted layout to the player. Track the rejection rate and time per accepted puzzle. When changing the search method, check its decisions against the exhaustive version and measure the whole generation loop before choosing between them. For hints, return the matching pair and its completed card. During a game, retain the cards still on the table and add cards from the undealt deck.

Notes

Encode each feature as 0, 1 or 2 and test for a sum of zero modulo 3 in each coordinate.
Use the unique completion of each pair to check for double counting: expect 1,080 SETs across the deck and 40 containing each card.
Keep the exhaustive search as a regression check: enumerating 85,320 triples and completing 3,240 pairs should both give 1,080 SETs.
A generator that requires a SET would reject about 3.17% of 12-card draws and 0.04% of 15-card draws in this sample of 200,000 layouts per size.
Stop at the first match when checking whether a SET exists; 66 lookups is the upper bound for a 12-card table.