Python迭代器在Quarto游戏板上的独特排列

Question

我正在研究一个组合数学问题的程序解决方案，这个问题涉及到棋盘游戏Quarto。在四重奏中有十六首曲子，每首曲子有四个二进制性质。这意味着我们可以将每个片段表示为一个元组（i，j，k，l），其中每个元素不是0就是1。为了解决我的问题，我需要迭代每一种独特的方式来排列所有的棋子。我可以这样做

from itertools import permutations
for board_orientation in permutations(pieces, 16):
    do_stuff(board_orientation) #takes 1 or 2 full seconds

但这意味着16岁！（超过20万亿次）迭代。为了避免这种情况，我试图创建一个生成器，只产生唯一的板方向-即在一个或多个属性的旋转、反射和反转下唯一的方向（前两个属性由二面体组D4描述）。我为Tic-Tac-Toe发现了一个类似的问题，但我正在努力研究如何将其扩展到这个更复杂的迭代问题。你知道吗

我认为解决方案包括通过哈希树将每个电路板的方向映射为一个数值，然后查看在各种对称操作下数字的变化，但很难将其转换为代码。你知道吗

Answer 1

通过应用反转，一块电路板与16块电路板“同构”，通过应用旋转和镜像，最多与8块电路板“同构”。这是一组同构板最多16*8=128。至少有15个！/8（1.6*10^11）板配置。你知道吗

使用反转，每个板可以“转换”成左上角为0的板。固定一个角可以覆盖所有的对称性，除了通过左上角（和右下角）在对角线上镜像 通过选择对称性上的两个“相反”字段（如（1,2）和（2,1）），并要求其中一个字段的值较小（如B[1,2]<；B[2,1]），可以覆盖该对称性。这意味着如果B[1,2]>；B[2,1]比 执行对角线镜像。按上述方式转换的电路板可以用15位十六进制数字串编码（左上角字段始终为0）。按左上角调用此编码规范化。你知道吗

以同样的方式，一块板可以被其他角正火。一个板有4个角规格化，并让呼叫板ID这些规格化的最小值。该ID唯一地对一组等轴测板进行编码。你知道吗

好的一点是：-），在配置生成过程中不需要存储生成的ID。它足以以一角规范化形式（如左上角）的字典顺序生成电路板， 计算其他三个规格化，如果其他三个规格化中的任何一个低于生成的值，则我们已经传递了该配置。这是因为配置是按字典顺序生成的。你知道吗

注意：可以通过在创建板过程中检查规范化值来优化代码，而不是创建整个板并执行上层检查。例如，填充两个有序字段（（1,2），（2,1））而不是用它的两个有序字段填充另一个角点，如果第二个角点的规格化必须小于左上角点的规格化（只检查两个字段的前缀），则无需进一步生成。为此，编码必须将有序字段作为前两位数字。扩展是下一步填充第三个角点域，执行检查，然后再填充第四个角点域并执行检查。你知道吗