Python迭代器Quarto游戏板的独特安排

Question

我正在研究涉及棋盘游戏Quarto的组合问题的编程解决方案。在Quarto中有十六件，每件都有四个二元属性。这意味着我们可以将每个元素表示为一个元组（i，j，k，l），其中每个元素为零或一个元素。为了解决我的问题，我需要重复每种独特的方式，以便在4x4的棋盘上安排全部棋子。我可以做类似

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）），而不是填充其它角的两个有序字段两个领域），而不需要进一步产生。对于该编码必须有有序的字段作为前两位数字。扩展是接下来填充第三个角落字段，执行检查，比第四个角落字段并执行检查。