1. 简介

神奇形色牌（Set）是一种卡片游戏，共有81张牌，其中有四个特征会不同：数量（1,2,3）、图案（菱形、椭圆形及波浪形）、纹路（实心、条纹及空心）及颜色（红色、绿色及紫色）。在一副牌中，四个特征的组合（例如三个绿色实心的菱形）都只会出现一次，不会重复。[1]

全部的牌如下图所示：

神奇形色牌的核心是组成 Set 的条件，只要桌面任意三张牌符合以下所有的条件，即为一个 Set：

三张牌的数字相同，或是三张牌的数字完全不同。
三张牌的图案相同，或是三张牌的图案完全不同。
三张牌的纹路相同，或是三张牌的纹路完全不同。
三张牌的颜色相同，或是三张牌的颜色完全不同。

若有两张牌的特征相同，但另一张牌和另外两张不同，这三张牌不能组成 Set。

例如，以下的三张牌可以组成 Set：

一个红色实心菱形
二个红色条纹菱形
三个红色空心菱形

在标准的神奇形色牌游戏中，发牌者将十二张牌放在桌上，若任一游戏者找到一组 Set，即可喊 Set，并将三张牌拿走，发牌者将桌上的牌补足 ,到 12 张（若游戏者喊了 Set，但没办法很快的将三张牌拿走，会被处罚）。有可能十二张中都没有三张牌可以组成 Set，发牌者可以再发牌到 15 张，使让游戏者继续找 Set，若有需要可以再发牌到 18 张……。游戏一直进行到所有的牌都发完，桌上没有牌可以组成 Set 为止，此时拿到最多 Set 的游戏者获胜。

2. Set 中的数学问题

在神奇形色牌中，需要从随机的 12 张或者更多的牌中寻找 Set ，那么需要多少张牌才能保证一定能从中找到 Set ？或者等价地说，最多能够有多少张牌而仍然不出现 Set ？

利用计算机进行蒙特卡洛模拟的方法，我们可以得出无法找到 Set 的概率。当有 12 张牌时，概率约为 33：1 ，当有 15 张牌时，概率约为 2500：1 [2]。但在进行真正的游戏时，情况则变得不同，因为并不会将找到的 Set 放回牌堆打乱后重新抽取，而是补充 3 张牌。在 12 张牌中找不到 SET 的平均概率增加了一倍，在 15 张牌中找不到 SET 的平均概率增加了 20 倍 [3]。更详细的分析指出了在游戏进行时随着剩余牌的数量减少概率的变化 [4]。

12 张牌

15 张牌

3. 问题的形式化定义 [5]

令 $\mathbb{F}_3$ 表示含有三个元素的域，考虑向量空间 $\mathbb{F}_3^4$ 。空间中的一个点是一个形如 $(x_1,x_2,x_3,x_4)$ 的四元组，Set 中的每一张牌可以对应于空间中的一个点。例如：

利用这种转换，三张牌构成一个 Set 当且仅当对应的三个点在 $\mathbb{F}_3^4$ 中是共线的。注意到 $\alpha,\beta,\gamma$ 是 $\mathbb{F}_3$ 中的三个元素，那么 $\alpha+\beta+\gamma=0$ 当且仅当 $\alpha=\beta=\gamma$ 或者 ${\alpha,\beta,\gamma}={0,1,2}$ 时成立，这意味着它们要么全部相同，要么各不相同。因此寻找 Set 实际上是在 $\mathbb{F}_3^4$ 的子集中寻找共线点。

我们定义 $d-cap$ 为 $\mathbb{F}_3^d$ 的一个不包含任何共线点的子集，那么等价的问题是： $\mathbb{F}_3^4$ 中一个 $4-cap$ 的大小最大可能是多少？这个问题最早在 1971 年被 Giuseppe Pellegrino 解答 [6] ，有趣的是这在 Set 游戏被发明的三年前。尽管 Set 游戏中 $d=4$ ，但我们仍然可以进一步考虑当 $d$ 为其他值时问题的答案和 $d$ 的关系，但这个问题尚未有通解。将答案记做 $a_d$ ，现在已经知道的结果如下：

4. 计算机视角

4.1 问题的复杂度分析 [7]

在上面的分析中，我们只考虑了 $d$ 即特征个数的变化，但每个特征下有几个分类也可以改变。我们将问题重新定义如下：牌堆为 $D={1,\ldots,v}^{p}$ ，当 $p=4,v=3$ 时就是一般的 Set 游戏。我们将 $p,v$ 同时改变的问题称为 $Set$ ， $v$ 固定的问题称为 $k-VALUE -SET$ ， $p$ 固定的问题称为 $k-PROPERTY-SET$ 。

可以证明，当 $k\geq3$ 时 $k-PROPERTY-SET$ 是 $NP-complete$ 的，于是 $Set$ 作为 $k-PROPERTY-SET$ 的推广也是 $NP-complete$ 的。在最早发现的 $NP-complete$ 问题中有一个非常类似的问题是 $k-DIMENSIONAL-MATCHING$ ，在 k 维的情况下寻找完美匹配，这是二分图完美匹配的推广。而它可以在多项式时间内规约到 $k-PROPERTY-SET$ 。

4.2 形式化验证

仅考虑 81 张牌可能的排列组合已有 $\binom{81}{12}=\frac{81!}{12!69!}=70724320184700\approx7.07\times10^{13}$ 种，因此用程序暴力计算几乎不可能。但可以将这个问题转化为 SAT(SMT) 问题，利用现有的搜索库进行求解。

用 $x[i][j]$ 表示第 $i$ 张牌的第 $j$ 个属性， $1\leq i\leq n,1\leq j\leq p$ ， $n$ 为牌组的数量。现在我们想要在特定的 $n$ 下找到一组 $x[i][j]$ ，使得它们之中没有 Set ，如果能够找到，就说明 $n$ 张牌不一定有 Set ，构建四个约束如下：

每个 $x[i][j]$ 的取值在 $0 \sim 2$ 之间，即每个属性只有 2 个取值

$$
\bigwedge_{i,j} 0 \leq x[i][j] \leq2
$$

任意两张牌不完全相同
$$
\bigwedge_{i,k,i\ne k} \bigvee_{j} x[i][j] \ne x[k][j]
$$
在 n 张牌中不存在 3 张，它们的每个属性要么完全相同，要么全不相同

$$
\bigwedge_{i,j,k,i\ne j\ne k \ne i} \neg \bigwedge_{l} (x[i][l] = x[j][l]\wedge x[j][l] = x[k][l])\vee(x[i][l] \ne x[j][l]\wedge x[i][l] \ne x[k][l] \wedge x[j][l] \ne x[k][l])
$$

利用德摩根率，等价地有
$$
\bigwedge_{i,j,k,i\ne j\ne k \ne i} \bigvee_{l} \neg( (x[i][l] = x[j][l]\wedge x[j][l] = x[k][l])\vee(x[i][l] \ne x[j][l]\wedge x[i][l] \ne x[k][l] \wedge x[j][l] \ne x[k][l]))
$$
利用 z-3 库，构建 SMT 问题

def check(n, p=4):
    # x[i][j]表示第i张牌的第j个属性
    card = [[Int("x_%s_%s" % (i, j)) for j in range(p)] for i in range(n)]
    # 每个x[i][j]的取值在0-2之间
    constraints = [And(card[i][j] >= 0, card[i][j] <= 2)
                   for i in range(n) for j in range(p)]
    # 任意两张牌不完全相同
    constraints += [Or([card[i][j] != card[k][j] for j in range(p)]) for i in range(n) for k in range(i + 1, n)]
    # 在n张牌中不存在3张，它们的每个属性要么完全相同，要么全不相同
    constraints += [Or([Not(Or(And(card[i][l] == card[j][l], card[j][l] == card[k][l]),
                           And(card[i][l] != card[j][l], card[j][l] != card[k][l], card[i][l] != card[k][l]))) for l in range(p)]) for i in range(n) for j in range(i + 1, n) for k in range(j + 1, n)]
    solver = Solver()
    solver.add(constraints)
    if solver.check() == sat:
        model = solver.model()
        # for i in range(n):
        #     print([model[card[i][j]] for j in range(p)])
        print("pass test %s" % n)
        # 存在反例
        return True
    else:
        # 不存在反例
        return False

类似地，也可以构建 SAT 问题，它的求解速度比 SMT 版本稍快

def check_sat(n, p=4):
    # x[i][j][k]表示第i张牌的第j个属性是否为k
    card = [[[Bool("x_%s_%s_%s" % (i, j, k)) for k in range(3)] for j in range(p)] for i in range(n)]
    # k在0-2之间，有且只有一个x[i][j][k]为真
    constraints  = [Or(And(card[i][j][0],Not(card[i][j][1]),Not(card[i][j][2])),
                        And(Not(card[i][j][0]),card[i][j][1],Not(card[i][j][2])),
                        And(Not(card[i][j][0]),Not(card[i][j][1]),card[i][j][2])) for i in range(n) for j in range(p)]
    # 任意两张牌不完全相同
    constraints += [Or([Or([card[i][j][l] != card[k][j][l] for l in range(3)]) for j in range(p)]) for i in range(n) for k in range(i + 1, n)]
    # 在n张牌中不存在3张，它们的每个属性要么完全相同，要么全不相同
    constraints += [Or([Not(Or(And([card[i][l][m] == card[j][l][m] for m in range(3)] + [card[j][l][m] == card[k][l][m] for m in range(3)]),
                        And(Or([card[i][l][m] != card[j][l][m] for m in range(3)]), Or([card[j][l][m] != card[k][l][m] for m in range(3)]), Or([card[i][l][m] != card[k][l][m] for m in range(3)])))) for l in range(p)]) for i in range(n) for j in range(i + 1, n) for k in range(j + 1, n)]
    solver = Solver()
    solver.add(constraints)
    if solver.check() == sat:
        model = solver.model()
        # for i in range(n):
        #     print([model[card[i][j][k]] for j in range(p) for k in range(3)])
        print("pass test %s" % n)
        # 存在反例
        return True
    else:
        # 不存在反例
        return False

初始时设置 $n=1$ ，逐渐增大 $n$ 直到不可满足为止，即可找出问题的解。

n = 1
while True:
    if check_sat(n,4):
        n += 1
    else:
        break

print("final n = %s" % (n - 1))

对于 $p=4$ 的情况，在 2 分钟内可以求出 $1 \sim 20$ 的解。

参考资料

“How to Play the Daily SET Puzzle”. America’s Favorite Card Games®. 2015-08-11. Archived from the original on 2022-01-13. Retrieved 2022-02-07.
Cannei, LLC (1991). [“SET Instructions”](https://www.setgame.com/sites/default/files/instructions/SET INSTRUCTIONS - ENGLISH.pdf) (PDF). Retrieved 17 January 2023.
“The Odds of Finding a SET in The Card Game SET®”
“SET Probabilities Revisited”. 30 September 2011. Archived from the original on 10 December 2011. Retrieved 4 October 2011.
Benjamin Lent Davis and Diane Maclagan. “The Card Game Set” (PDF). Archived from the original (PDF) on June 5, 2013.
G. Pellegrino. Sul massimo ordine delle calotte in S4,3. Matematiche (Catania), 25:149–157 (1971), 1970.
Chaudhuri, Kamalika; Godfrey, Brighten; Ratajczak, David; Wee, Hoeteck (2003). On the Complexity of the Game of Set (PDF) (Technical report). Archived (PDF) from the original on 2022-01-09.