在Python的OR-Tools中实现数独变体的行唯一集合约束：解决sorted()和min()函数的兼容问题

我完全理解你遇到的困境——OR-Tools的CP-SAT变量是决策变量，在求解器找到解之前它们的值是未知的，所以Python原生的sorted()、min()这类处理确定值的函数根本没法直接用在这些变量上，生成9!排列的方法不仅效率极低，还完全走错了方向。

其实我们根本不需要折腾什么排列签名，核心需求是让每行的数字集合唯一，而不是排列不同。我们可以用一个更聪明的方式：给每个行的集合生成一个唯一的“哈希标识”，这个标识只和集合里的元素有关，和顺序无关，然后约束所有行的标识必须不同。

解决方案思路 #

我们可以利用二进制位的唯一性：对于0-11中的每个数字x，如果行里包含x，就把二进制的第x位设为1，否则为0。这样每个集合对应的二进制数（也就是十进制的哈希值）是完全唯一的——不同的集合不可能有相同的二进制表示，反过来相同的集合哈希值一定相同。

举个例子：集合{1,2,...,9}对应的二进制是0b11111111100（第1到9位是1），而集合{0,1,...,8}对应的是0b0111111111（第0到8位是1），这两个哈希值完全不同，完美符合我们的需求。

具体实现步骤 #

下面是完整的代码实现，我会一步步解释：

1. 先确保每行的单元格都是唯一的（经典数独行约束，如果你已经加过可以跳过）

# 先添加每行的数字唯一约束（经典数独要求）
for i in range(self.Rows):
    self.Model.AddAllDifferent([self.Cells[i][j] for j in range(self.Cols)])

2. 创建布尔变量标记每行是否包含某个数字

我们需要为每个行i和数字x（0-11）创建一个布尔变量present[(i, x)]，用来表示行i中是否存在数字x：

from ortools.sat.python import cp_model

# 存储行i是否包含数字x的布尔变量
present = {}
for i in range(self.Rows):
    for x in range(12):  # 数字范围是0-11
        present[(i, x)] = self.Model.NewBoolVar(f"present_row_{i}_num_{x}")

3. 关联布尔变量和单元格变量

我们需要约束：当present[(i, x)]为True时，行i中至少有一个单元格等于x；当它为False时，行i中所有单元格都不等于x：

for i in range(self.Rows):
    for x in range(12):
        # 若present为True，则行中至少有一个单元格等于x
        self.Model.AddBoolOr([self.Cells[i][j] == x for j in range(self.Cols)]).OnlyEnforceIf(present[(i, x)])
        # 若present为False，则行中所有单元格都不等于x
        self.Model.AddBoolAnd([self.Cells[i][j] != x for j in range(self.Cols)]).OnlyEnforceIf(present[(i, x)].Not())

4. 约束每行恰好包含9个不同数字

因为题目要求每行有9个唯一数字，所以每行对应的布尔变量中恰好有9个为True：

for i in range(self.Rows):
    # 统计行i中为True的present变量数量，必须等于9
    self.Model.Add(sum(present[(i, x)] for x in range(12)) == 9)

5. 计算每行的唯一哈希值

用2的幂次计算哈希值，每个数字x对应2^x，把所有存在的数字对应的幂次相加，得到唯一的哈希值：

row_hashes = []
for i in range(self.Rows):
    # 构建哈希表达式：sum( present[(i,x)] * 2^x for x in 0..11 )
    hash_expr = sum(present[(i, x)] * (2 ** x) for x in range(12))
    # 创建哈希变量，范围是0到2^12-1（因为0-11共12个数字，最大哈希是2^0+2^1+...+2^11=4095）
    hash_var = self.Model.NewIntVar(0, 4095, f"row_hash_{i}")
    self.Model.Add(hash_var == hash_expr)
    row_hashes.append(hash_var)

6. 约束所有行的哈希值唯一

最后，只需要让所有行的哈希值都不同，就能保证每行的数字集合唯一：

# 确保所有行的哈希值（即数字集合）唯一
self.Model.AddAllDifferent(row_hashes)
print("Distinct row set constraints added successfully.")

扩展到列和子网格 #

如果需要对列或子网格也施加同样的“集合唯一”约束，只需要把上面的逻辑中的“行”换成“列”或“子网格”即可：

• 对于列：遍历每一列j，收集self.Cells[i][j]作为列的单元格，然后重复上述步骤
• 对于子网格：先定义每个子网格包含哪些单元格，比如3x3的子网格，然后收集这些单元格，重复上述步骤

为什么这个方法高效？ #

• 完全不需要生成任何排列，避免了9!的爆炸式计算量
• 所有约束都是OR-Tools CP-SAT原生支持的布尔约束和线性约束，求解器处理起来非常快
• 哈希值的计算完全无冲突，保证了集合和哈希值的一一对应

备注：内容来源于stack exchange，提问作者Arun