如何生成/迭代所有"Connect-Four“游戏？

Question

我需要迭代所有不同的"Connect-Four“游戏。

网格有42个单元格，其中有21个红色部分和21个黄色部分。

生成的每个游戏必须使用每个棋子，并且相同颜色的所有棋子是不可区分的(例如，如果您在一个解决方案中交换两个红色，则不能算作另一个解决方案)

从这点我可以得出结论

​

​

我正在考虑生成包含21个0和21个1的二进制字符串，但除了生成每个42个字符的二进制字符串并逐个测试它们之外，我不知道如何做到这一点。这将是42！(1.4050061e+51)字符串测试，所以这不是一个选项。

你将如何着手生成所有这些可能的游戏？

Answer 1

看起来你并不关心这些游戏中的一些会提前结束。要简单地生成所有可能的组合，您应该将棋盘视为一个矩阵，其中1表示黑色，0表示红色。现在，如果我们向量化整个棋盘的值矩阵，那么我们将得到如下内容

[0,1,1,0,...] 

其中确切的顺序取决于排列。现在，由于每种颜色都有21种颜色，这意味着您实际上是在请求向量的所有可能的排列

[ones(1,21),zeros(1,21)]

(使用Matlab和Python表示法)。在Matlab中，您可以使用下面的函数生成所有排列的列表

perms([ones(1,21),zeros(1,21)])

我不确定您在这里想要什么，因为在实践中枚举所有这些显然是不可行的。如果您只对如何做到这一点感兴趣，我建议您查看Matlab实现。它看起来像10行非常简单的代码。