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

Question

我正在研究一个涉及棋盘游戏 Quarto 的组合数学问题的程序化解决方案。在四开本中有 16 件作品，每件作品都具有四个二进制属性。这意味着我们可以将每个片段表示为一个元组 (i, j, k, l)，其中每个元素要么为零，要么为一。为了解决我的问题，我需要遍历每种独特的方式来在 4x4 棋盘上排列 all 棋子。我可以做类似

的事情

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

一个棋盘是'isomorphic' 16 棋盘应用倒置，最多8 板应用旋转和镜像。即一组同构板最多为16*8=128。至少有 15!/8 (1.6 * 10^11) 板配置。

使用反转可以将每个板 'transformed' 变成左上角为 0 的板。固定一个角覆盖了所有对称性，除了通过左上角（和右下角）在对角线上进行镜像。可以通过在该对称性上选择两个 'opposite' 字段（如 (1,2) 和 (2,1)）来覆盖该对称性，并在其中一个字段中要求较小的值（例如 B[1,2] < B [2,1])。这意味着如果 B[1,2] > B[2,1] 比执行对角线镜像。以上述方式变换的棋盘可以用15位十六进制数字串编码（左上角字段始终为0）。称此编码归一化为左上角。

同理，一块板可以被其他角归一化。一块板有 4 个角归一化，并让这些归一化的板 ID 最小。该 ID 对一组等轴测板进行唯一编码。

现在是好的部分 :-)，不需要在配置生成过程中存储生成的 ID。以一个角归一化形式（e.f。左上角）的字典顺序生成板就足够了，计算其他三个规范化，如果其他三个规范化中的任何一个低于生成的，我们已经通过该配置。这是因为配置是按字典顺序生成的。

注意：可以通过检查创建板过程中的规范化值来优化代码，而不是创建整个板并执行上层检查。比如，如果第二个角的归一化必须小于左上角的归一化（仅检查前缀两个字段）比没有必要进一步生成。对于该编码，必须将有序字段作为前两位数字。扩展是接下来填充第三个角字段，执行检查，而不是第四个角字段并执行检查。

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

Python iterator for unique arrangements of Quarto game board

python

iteration

generator

combinatorics