计数井字棋唯一状态的有效算法

        数学 诀窍是使用Polyas枚举定理： http://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem 忽略重复项，存在3个状态（x，o和-）的9个正方形，因此有3 ^ 9 = 19683个配置。您需要定义在板上提供操作的组。对于您的问题，Dehedral Group D4似乎可以并列使用。但是并置是很容易的，因为只要不在一块满不在乎的电路板上，它就有2个（所有-初始配置）。 计算方式 虽然数学可以让我们计算配置，但并不能帮助您识别它们。也许最简单的解决方案是将板定义为元组：{p1，p2，p3，...，p9}，其中每个pn为{0,1,2}。每平方需要2位，其中有9位共18位。因此，一块板可用32位或更少的整数表示。 通过哈希表可以很容易地将索引添加到板中。只有19000种配置，因此它不会杀死我们。 最好在上面9个元组的基数为3的情况下完成所有电路板配置：{0,0,9，...，0}，{0,0,0，...，1}，{0 ，0,0，...，1,0}，依此类推。随身携带而已。这将生成所有板。注意组动作和并置将如何转换这样的数字。可能性是有限的（将x从x移到o，反之亦然，其他的则根据D4组在板上的位置移动。有8种这样的转换。）您可以使用Polya来确保算法将它们全部。 如建议的那样，从集合中选择最小的人是对操作进行模配置的唯一代表。     

        我不知道正确的数学方法，但是我会这样做。设计一种将任何状态转换为一个数字的方法。例如，将空字段分配为零，将O片分配为1，将X片分配为2，并在base-3系统中将9位数字视为数字。现在，将状态转换为所有其余7个镜像状态。也计算他们的数字。从这8个数字中选择最小的一个。而已。     

        如果您只关心最佳移动： 参见此最佳井字移动的系统地图（http://xkcd.com/832/）。您可以使用一些（行，行）索引来标识特定状态。 如果存在多个等效状态，则使用所有的\“ lowest \”索引（您必须定义\“ lowest \”的含义；例如，值（3 * col + row最低）的那对（col，row）对）等效的。     

结合其他答案中的一些想法... 不要将配置映射到数字。使用数字表示配置。如果确实需要通过x，y位置获取/设置，请编写对表示形式进行操作的方法。 然后选择一种可以有效操作以回答问题的表示形式。这是一个主意。 您有三个操作，因此让我们给它们命名： R =将板逆时针旋转90度 M =绕y轴的镜子 I =反转板（您称之为“并置”，但我认为“反转”更具描述性） 您想计算这些操作轨道下的等效板数量。每个等效类中最多包含16个元素。给定一个板，您可以通过按以下顺序应用操作来生成其他15个等效板： R，R，R，I，R，R，R，M，R，R，R，I，R，R，R （其他顺序也可以使用...） 因此，一个好主意是选择一个使R快速（我有点快速）并且不必太担心M的表示形式。 由于R不会改变中心，因此我会将其保持在其他位置，并使用2位数字序列表示其他8个正方形。我让第一个2位数字代表左下角，下一个2位数字代表其旁边的正方形，依此类推，在板上逆时针移动。我会让00代表\“ O \”，11代表\“ X \”，而01和10都代表\“ empty \”（因为这样我就可以简单地进行位翻转）。 然后，如果将这8个2位数字写为单个16位数字，则操作R只是对16位数字的循环操作，您的CPU可能可以在一条指令中执行。运算I只是与-1的XOR（但不要忘记也将中心平方反转）。 M运算是一堆复杂的位运算，但是由于您在15次中只执行了一次，谁在乎？ 这应该使您可以采用任何表示形式并快速生成其他15种等效形式。然后按照Dialecticus的建议，选择数值最小的表示形式作为您的等价类的规范成员，并对它们进行计数。     

        我认为图论对此有好处，对于您给出的示例，您将有一个具有9个顶点的图。唯一仍然可能是问题的是并置。     

        井字游戏与AI有关，特别是来自Game theory的minmax算法，甚至更适合于AB Pruning，以获得良好的效果。整个主题很大，但是很容易且程序化。它很容易掌握，您可以从以下页面开始： http://en.wikipedia.org/wiki/Game_theory http://www.cs.trincoll.edu/~ram/cpsc352/notes/minimax.html 比上面的链接更清晰，更容易的事情： http://www.cs.ucla.edu/~rosen/161/notes/alphabeta.html