如何在代码中表示魔方（Rubik's Cube）？

Question

如何在代码中表示魔方（Rubik's Cube）？

data-structuresrubiks-cube

70

如果您要开发用于解决魔方的软件，您会如何表示魔方？

- Mendokusai

4

取决于您需要对数据执行哪些操作。 - stefanB

Python，我想。 - erip

13个回答

17

简而言之，这取决于您将如何解决魔方。如果您的求解器将使用人类方法（如逐层法或Fridrich法），则底层数据结构不会有太大的影响。即使在最慢的编程语言中，计算机也可以在可忽略的时间（不到一秒钟）内使用人类方法解决魔方。但是，如果您要使用更加计算密集的方法来解决魔方，例如Thistlethwaite的52步算法、Reid的29步算法或Korf的20步算法，则数据结构和编程语言至关重要。

我编写了一个魔方程序，它使用OpenGL渲染魔方，并内置了两种不同类型的求解器（Thistlethwaite和Korf）。求解器必须生成数十亿个移动并比较每个魔方状态数十亿次，因此底层数据结构必须快速。我尝试了以下几种结构：

一个三维字符数组，6x3x3。其中一个面的颜色按cube [SIDE] [ROW] [COL]索引。这很直观，但很慢。
一个54个字符的单一数组。这比（1）更快，并且行和步幅是手动计算的（微不足道）。
6个64位整数。这种方法本质上是一个位板，比方法（1）和（2）快得多。扭转可以使用位操作完成，面部比较可以使用掩码和64位整数比较完成。
一个角块数组和一个单独的边块数组。每个数组的元素都包含一个立方体索引（对于边缘为0-11；对于角落为0-7）和定位（对于边缘为0或1；对于角落为0,1或2）。当您的求解器涉及模式数据库时，这是理想的选择。

在上述方法（3）的基础上，魔方的每个面由9个贴纸组成，但中心是固定的，因此只需要存储8个贴纸。有6种颜色，因此每种颜色都适合一个字节。给定这些颜色定义：

enum class COLOR : uchar {WHITE, GREEN, RED, BLUE, ORANGE, YELLOW};

一个人脸可能长成这个样子，存储在单个64位整数中：

00000000 00000001 00000010 00000011 00000100 00000101 00000000 00000001

被解码为：

WGR
G B
WYO

使用这种结构的优点是可以使用rolq和rorq按位运算符来移动一个面。向左或向右滚动16位将影响90度旋转; 向左或向右滚动32位将产生180度翻转。相邻的块需要手动维护-即在旋转顶部时，还需要移动前面、左边、后面和右边面的顶层。以这种方式旋转面非常快速。例如，滚动

00000000 00000001 00000010 00000011 00000100 00000101 00000000 00000001

通过16位生成

00000000 00000001 00000000 00000001 00000010 00000011 00000100 00000101

解码后，它看起来像这样：

WGW
Y G
OBR

另一个优点是，有些情况下可以使用一些巧妙的位掩码和标准整数比较来比较魔方状态。对于求解器来说，这可能会加速很多。

无论如何，我的实现在Github上：https://github.com/benbotto/rubiks-cube-cracker/tree/2.2.0，请参阅Model/RubiksCubeModel.{h,cpp}。

延伸方法（4），编程解决魔方的一些算法使用了迭代加深的深度优先搜索和A*算法，并使用图案数据库作为启发式。例如，Korf算法使用三个模式数据库：一个存储8个角块的索引和方向；一个存储12个边缘块中的6个的索引和方向；最后一个存储另外6个边缘块的索引和方向。使用模式数据库时，一种快速的方法是将魔方存储为一组索引和方向。

任意定义一个约定，可以将边缘块按以下方式进行索引。

0  1  2  3  4  5  6  7  8  9  10 11 // Index.
UB UR UF UL FR FL BL BR DF DL DB DR // Position (up-back, ..., down-right).
RY RG RW RB WG WB YB YG OW OB OY OG // Colors (red-yellow, ..., orange-green).

因此，红黄边块位于索引0处，白绿边块位于索引4处。同样，角块可能被编号如下：

0   1   2   3   4   5   6   7
ULB URB URF ULF DLF DLB DRB DRF
RBY RGY RGW RBW OBW OBY OGY OGW

所以，红蓝黄角块的索引为0，橙绿黄角块的索引为6。

每个魔方块的方位也需要保持。边块可以有两种方向（定向或翻转），而角块则可以有三种不同的方向（定向、旋转一次或旋转两次）。有关块朝向的更多详细信息可以在这里找到：http://cube.rider.biz/zz.php?p=eoline#eo_detection。使用这个模型，旋转一个面意味着更新索引和方向。这种表示法最困难，因为对于人类来说（至少对于我来说）查看一大堆的索引和方向数字并验证它们的正确性很难。尽管如此，与使用上述其他模型动态计算索引和方向相比，这种模型显着更快，因此在使用模式数据库时是最佳选择。您可以在此处查看此模型的实现：https://github.com/benbotto/rubiks-cube-cracker/tree/4.0.0/Model （请参见 RubiksCubeIndexModel.{h,cpp}）。

如前所述，该程序还呈现了魔方。我为此部分使用了不同的结构。我定义了一个“cubie”类，它由六个正方形组成，中心块、边块和角块的颜色面数分别为1、2或3。魔方由26个cubies组成。面是使用四元数旋转的。 cubies和cube的代码在这里：https://github.com/benbotto/rubiks-cube-cracker/tree/4.0.0/Model/WorldObject

如果您对我的魔方求解程序感兴趣，则可以在YouTube上找到一个高级概述视频：https://www.youtube.com/watch?v=ZtlMkzix7Bw&feature=youtu.be。我还在Medium上撰写了更详细的关于编程解决魔方的文章。

- benbotto

13

一种方法是着重于视觉外观。

一个立方体有六个面，每个面都是一个三乘三的正方形阵列。所以

Color[][][] rubik = new Color[6][3][3];

然后每个移动都是一种方法，可以置换特定组合的彩色方块。

- joel.neely

这是我使用的方法。使旋转面更容易。new_cube[face][i][j] = clockwise ? old_cube[j][2 - i] : old_cube[2 - j][i]; } - azz

12

避免优化；使其面向对象。我使用的伪代码类概述是：

class Square
    + name : string
    + accronym : string

class Row
    + left_square : square
    + center_square : square
    + right_square : square

class Face
    + top_row : list of 3 square
    + center_row : list of 3 square
    + bottom_row : list of 3 square

    + rotate(counter_clockwise : boolean) : nothing

class Cube
    + back_face : face
    + left_face : face
    + top_face : face
    + right_face : face
    + front_face : face
    + bottom_face : face

    - rotate_face(cube_face : face, counter_clockwise : boolean) : nothing

使用的内存量非常小，处理也非常少，因此优化是完全不必要的，特别是当你为此牺牲代码的可用性时。

- Humphrey Bogart

2

虽然这不是“优化”，但我认为这是“面向对象的过度思考”，至少多少有点。这些精心设计的面和行的目的是什么呢？一个面可以简单地由9个正方形组成。更简单的是，一个立方体可以由54个正方形组成。无论哪种方式，正确地旋转都很困难。 - Jo So

8

一个有趣的方法来表示魔方，被软件“魔方探索者”所使用。该方法使用许多巧妙的数学，只需使用5个整数就可以表示魔方。作者在他的网站上解释了程序背后的数学。据作者称，该表示适用于实现快速求解器。

- mdm

6

有很多种方法可以做到这一点。有些方法比其他方法更有效地利用内存。

我见过人们使用一个3 x 3 x 3的立方体对象数组，其中立方体对象需要存储颜色信息（是的，那个中心对象从来没有被使用过）。我见过人们使用6个数组，每个数组都是一个3 x 3的立方体对象数组。我见过一个3 x 18的立方体对象数组。有很多可能性。

可能更大的问题是如何表示各种变换。旋转物理魔方的单个面（所有魔方移动本质上都是单个面的旋转）必须通过交换许多立方体对象来表示。

你的选择应该是适合你正在编写的任何应用程序的选择。可能只是渲染魔方。也可能没有用户界面。你可能正在解决魔方。

我会选择3 x 18的立方体对象数组。

- Paul Beckingham

5

有20个关键的小立方体。因此，一种方法是将其作为由20个字符串组成的数组。这些字符串将包含表示颜色的2或3个字符。任何单个移动都会影响7个小立方体。因此，您只需要为每个六个面制作一个重映射器。

注意：此解决方案无法记住白色中心上的标志贴纸的方向。

顺便说一句，我曾经帮助过某人制作魔方软件，大约15年前，但我不记得我们是如何表示它的。

- Nosredna

4

你可以把魔方想象成三个垂直的循环链表，它们和三个水平的链表相交。

每当魔方的某一行进行旋转，你只需旋转相应的指针即可。

看起来就像这样：

struct cubeLinkedListNode {
    cubedLinkedListNode* nextVertical;
    cubedLinkedListNode* lastVertical;
    cubedLinkedListNode* nextHorizontal;
    cubedLinkedListNode* lastHorizontal;
    enum color;
}

您可能实际上并不需要这两个“last”指针。

[我使用C语言实现了这个功能，但是只要使用一个简单的cubeLinkedListNode类，每个类都持有对其他节点的引用，就可以在Java或C#中完成。]

请记住，有六个互锁的循环链表，其中三个是纵向的，三个是横向的。

对于每次旋转，您只需要按顺序循环遍历相应的循环链表，逐个移动旋转圆的链接以及连接圆的链接。

至少大致如此...

- GordonG

1

一个魔方有：

- 8个角块，每个包含一个独特的角块。 - 12个棱块，每个包含一个独特的棱块。 - 6个中心块，每个包含一个独特的中心块。

每个角块可以有以下三种方向之一：

- 未旋转； - 顺时针旋转120度；或 - 逆时针旋转120度。

每个棱块可以有以下两种方向之一：

- 未翻转；或 - 翻转180度。

中心块相对于彼此固定；但是有24种可能的方向（忽略单个中心块的旋转，这只在你解决图片魔方时才相关），因为有6种方法可以选择位于“上”面的中心块，然后有4种方法可以选择位于“前”面的中心块。

你可以将其存储为：

- 包含八个3位整数的数组，每个整数代表一个角块在角落位置上。 - 包含八个2位整数的数组，每个整数代表角块在角落位置上的方向。 - 包含12个4位整数的数组，每个整数代表一个棱块在边缘位置上。 - 包含12个1位整数的数组，每个整数代表一个棱块在边缘位置上的方向。 - 一个5位整数，代表中心块的24种可能方向的枚举。

这总共需要105位（14字节）。

空间优化：

由于角块始终固定，因此可以假设它们永远不会移动，无需存储。这样，如果要进行 E 移动，则可以执行等效的 U D' 一对移动。这将减小大小到100位（13字节）。
如果限制表示为可解决魔方，则可以将魔方存储在更小的空间中，如下所示：
- 一旦您知道7个角块，就可以计算出第8个角块。
- 角块的方向具有固定的奇偶性，因此一旦您知道7个角的方向，就可以推导出第8个角块的方向。
- 棱块同理，您只需要存储11个12个棱块和棱块方向之一，并可以计算出剩余的棱块。
这可以节省另外10位，总共90位（12字节）。但是，计算所需的计算可能意味着这种空间优化不值得性能惩罚。

如何在代码中表示魔方（Rubik's Cube）？

空间优化：

更多空间优化：