# SET 卡牌的第三張怎麼算：mod 3 補全與 1,080 組 SET 的由來

> SET 任兩張不同的牌都能用 mod 3 補出唯一的第三張，整副 81 張牌共有 1,080 組 SET，每對牌恰在一組。桌面 12 張牌用補全法搜尋，最多查表 66 次。

原文：https://sheng.page/posts/set-card-game-third-card-and-set-counting/ · 發布：2026-10-27 · 作者：Sheng

SET 的三張牌，每個特徵都要全部相同或全部不同。把各特徵的值編成 0、1、2，這條規則就等於三個值相加後除以 3，餘數為 0，所以任取兩張不同的牌 a、b，第三張只能是逐特徵計算的 `c = −(a+b) mod 3`。

整副 81 張牌共有 1,080 組 SET，每張牌參與 40 組，每對牌恰在一組裡。三張列舉和兩張補全都能算出 1,080；桌面只有 12 張時，補全法最多查表 66 次就能判斷有沒有 SET，隨機抽出 12 張卻沒有 SET 的機率約 3%。

## 規則與編碼

SET 有 81 張牌，每張牌有顏色、形狀、數量、底紋四個特徵。判斷時各特徵分開看，顏色可以全同，數量可以全異，只要各自符合規則即可。

四個特徵各有三種值，整副牌包含所有組合，所以牌數是 `81 = 3^4`。把各特徵的值編成 0、1、2，一張牌就能用四個數字組成的 tuple 表示，也就是 `(Z₃)⁴` 的一個點。

先只看一個特徵，把三張牌對應的值記為 x、y、z，可能情況如下：

| 三個值的關係 | 相加後會怎樣 |
|---|---|
| 全部相同 | 和為 0、3 或 6，都能被 3 整除 |
| 全部不同 | 一定各有一個 0、1、2，和為 3 |
| 兩個相同、一個不同 | 設重複的值為 x，另一個為 y，`2x+y ≡ y−x (mod 3)`；x、y 不同，餘數就不會是 0 |

因此，全同或全異與 `x+y+z ≡ 0 (mod 3)` 等價，四個特徵都符合這個條件，三張牌就構成 SET。程式只要逐欄相加取餘數，不必另外寫全同與全異的分支。

## 第三張唯一

已知 a、b 兩張牌，將 `a+b+c ≡ 0 (mod 3)` 移項，就得到 `c ≡ −(a+b) (mod 3)`，每個特徵各算一次，第三張牌便確定了。

這張 c 也不會與 a 或 b 重複。假設 c 等於 a，原式就成了 `2a+b ≡ 0 (mod 3)`，也就是 `b ≡ a (mod 3)`，與起初選兩張不同的牌矛盾；c 等於 b 時同理。

整副牌共有 `C(81,2) = 81×80/2 = 3,240` 對，一組 SET 含三對牌，同一組會算到三次，所以總數是 `3,240/3 = 1,080`。固定其中一張牌，它能和其餘 80 張各配一對，每組包含這張牌的 SET 會貢獻兩對，於是每張牌參與 `80/2 = 40` 組。

每張牌參與 40 組、每對牌恰在一組，總數也可寫成 `81×80/3! = 1,080`。

## 列舉三張與補全兩張

整副牌只有 85,320 種三張組合，直接逐組檢查，就能和兩張補全的結果對照。`set_count.py` 用前面推導的餘數條件判斷 SET：

```python
# 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))
```

```text
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
```

`by_triples` 走訪全部 85,320 個三元組，逐一呼叫 `is_set`；這個函式檢查四個特徵，有任何一個不符合就回傳 `False`。`by_pairs` 則只走訪 3,240 對，每對算出第三張，用 `frozenset` 表示不分順序的一組牌，外層 `set` 再把重複的組合去掉。

兩種寫法都得到 1,080，最後的 `is_set` 檢查也全部通過，列舉版可以留下來做回歸測試。輸出的每牌組數由總數算平均，每張牌都參與同樣多組則由前面的配對證明保證。

三張列舉耗時 28 ms，兩張補全耗時 3 ms，後者包含建立 `pairs` 與去重集合的時間。這是 Mac 上的單次量測，不能當成固定的效能比例。

## 用兩張補全搜尋桌面的 SET

桌面只有 n 張牌時，第三張仍然唯一，只是可能不在桌面上。先把桌面牌放進 Python 的 `set`，每對牌算出第三張後查一次，平均一次查詢是 `O(1)`。

| 桌面張數 | 三張列舉的候選數 | 兩張補全的查表上限 |
|---|---:|---:|
| 12 | `C(12,3) = 220` | `C(12,2) = 66` |
| 15 | `C(15,3) = 455` | `C(15,2) = 105` |

只要判斷有沒有 SET，找到第一組就能停止，無 SET 時才需要查完每一對。`no_set_probability.py` 對 12 張與 15 張桌面各抽樣 200,000 次，seed 固定為 42，以 `1.96 × sqrt(p×(1−p)/T)` 計算近似 95% 信賴區間的半寬：

```python
# 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)}")
```

```text
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
```

`random.sample` 每次從完整 81 張牌抽出不重複的 n 張，因此這些機率適用於獨立重新發牌。`has_set` 裡的 `any` 會提早停止，輸出的 66 與 105 都是查表上限。

12 張桌面約有 3.17% 找不到 SET，誤差範圍約正負 0.08 個百分點；15 張降到 0.04%，約正負 0.01 個百分點。

這個估計也接近 [Norvig 的模擬](https://www.norvig.com/SET.html)。[^set-sampling]

[^set-sampling]: Norvig 每種桌面抽樣 100,000 次，12 張有 3,299 次無 SET，也就是 3.299%；15 張有 38 次，為 0.038%。他的 12 張結果誤差範圍約正負 0.11 個百分點；這次 200,000 次抽樣得到 3.17%，兩者相差約 0.13 個百分點，區間有重疊。

## 小桌面值不值得最佳化

先做出可用的工具，12 張牌直接列舉 220 個三元組就夠。搜尋成為瓶頸時，再量補全法把候選數從 220 降到 66 能省多少時間；前面的計時涵蓋整副 81 張牌，12 張桌面要另外測，包含建立查表集合的成本。

做練習題生成器，可以直接把抽樣程式裡的桌面送進 `has_set`，沒有 SET 就重抽，通過才交給玩家，並記錄淘汰比例與每題耗時。改用補全法時，保留列舉版核對篩選結果，再用整段生成流程的耗時決定值不值得換。提示功能需要實際的牌，搜尋找到第一組時就回傳這一對和第三張；遊戲途中要加牌，則保留桌面剩牌，從未發出的牌堆補。

## 補充筆記

- 實作判定時，把四個特徵各編成 0、1、2，逐欄檢查相加後模 3 是否為 0。
- 用每對牌恰在一組 SET 檢查重複計數，整副牌應有 1,080 組，每張牌參與 40 組。
- 改搜尋法時，保留列舉 85,320 個三元組的版本做回歸基準，補全 3,240 對也應得到 1,080 組。
- 生成有解的練習題時，12 張桌面約會淘汰 3.17%，15 張約 0.04%（每種桌面各抽樣 200,000 次）。
- 搜尋 12 張桌面時，找到 SET 就停止，66 次是查完所有牌對的上限。

## 延伸閱讀

- [PlayMonster：SET](https://www.playmonster.com/product/set/)：發行商的產品頁，列出牌數與四個特徵，說明全同或全異的規則。
- Peter Norvig〈[The Odds of Finding a SET in The Card Game SET](https://www.norvig.com/SET.html)〉：SET 數量的推導與無 SET 機率的模擬，附 Python 程式。

> 想法與技術判斷出自 Sheng，和 Claude 一起起草 · 範例在 Mac 上以 Python 3.15.0 實測。