魔方

魔方是一个 的 立方体，其外部的 26 个小立方体以内部铰接的方式连接，使得在任何立方体平面内都可以旋转（四分之一圈、半圈，双向皆可）。六个面各自涂有不同的颜色，谜题的目标是通过反复旋转将其打乱后，将魔方恢复到每个面都是单一颜色的状态。这个 谜题 是由匈牙利人厄尔诺·鲁比克在 1970 年代发明的，并在接下来的十年中在全球销售了数百万个。

魔方可能的排列组合数量是

(Turner and Gold 1985, Schönert)。 Hoey 使用 Cauchy-Frobenius 引理 证明，在整个魔方对称的共轭关系下，有 种排列组合。

魔方操作的 群 被称为 魔方群，该群的 凯莱图 被称为 魔方图。从任意初始位置解开魔方所需的最少步数等于 魔方图 的 图直径，有时也被称为 上帝之数。虽然存在从任意初始位置解开魔方的算法，但它们不一定是最佳的（即，不一定需要最少步数），并且 上帝之数 的计算非常困难。自 1995 年以来，人们已经知道最坏情况下解开魔方所需的步数下限为 20 步，直到 Rokicki 等人 (2010) 证明没有任何一种配置需要超过 20 步，才确定上帝之数为 20。

仅使用半步旋转即可达到的 魔方构型形成一个 瑙鲁图。 Wolfram (2022) 通过一个 多向图 分析了 魔方，其最初几步如上图所示。