当前位置：文江博客话题详情

您将如何用代码表示魔方？

发布于 2024-07-13 12:49:12 字数 33 浏览 9 评论 0原文

如果您正在开发解决魔方问题的软件，您会如何表示魔方？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

歌入人心 2024-07-20 12:49:13

有 20 个立方体很重要。因此，一种方法是使用包含 20 个字符串的数组。这些字符串将包含 2 或 3 个表示颜色的字符。任何单个移动都会影响 7 个立方体。所以你只需要为六个面的每一个重新映射器。

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

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

回复收藏 0 原文

安静被遗忘 2024-07-20 12:49:13

您可以将立方体想象为三个垂直的圆形链表，它们与三个水平链表相交。

每当立方体的某一行旋转时，您只需旋转相应的指针即可。

它看起来像这样：

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

您实际上可能不需要 2 个“最后”指针。

[ 我使用 C 语言完成了此操作，但也可以在 Java 或 C# 中完成，只需使用cubeLinkedListNode 的一个简单类，每个类都保存对其他节点的引用。 ]

请记住，有六个互锁的循环链表。 3 垂直 3 水平。

对于每次旋转，您只需循环遍历相应的圆形链表，依次移动旋转圆的链接以及连接圆。

至少是这样的……

You could imagine the cube as three vertical circular linked lists, which intersect three horizontal linked lists.

Whenever a certain row of the cube is rotated you would just rotate the corresponding pointers.

It would look like this:

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

You might not actually need the 2 'last'-pointers.

[ I did this with C, but it could be done in Java or C# just using a simple class for cubeLinkedListNode, with each class holding references to other nodes. ]

Remember there are six interlocking circular linked lists. 3 vertical 3 horizontal.

For each rotation you would just loop through the corresponding circular linked list sequentially shifting the links of the rotating circle, as well as the connecting circles.

Something like that, at least...

回复收藏 0 原文

写下不归期 2024-07-20 12:49:13

最短的表示形式如下所示： codepen.io/Omelyan/pen/BKmedK

立方体展开为一维数组（54 个元素的向量）。几行旋转功能交换贴纸并基于立方体的对称性。这是 C 语言的完整工作模型，我在 2007 年还是一名学生时制作的：

const byte // symmetry
  M[] = {2,4,3,5},
  I[] = {2,0,4,6};

byte cube[55]; // 0,0,0,0,0,0,0,0,0, 1,1,1,1,1,1,1,1,1, ... need to be filled first

#define m9(f, m) (m6(f, m)*9)

byte m6(byte f, byte m) {return ((f&~1)+M[m+(f&1)*(3-2*m)])%6;}

void swap(byte a, byte b, byte n) {
  while (n--) {byte t=cube[a+n]; cube[a+n]=cube[b+n]; cube[b+n]=t;}
}

void rotate(byte f, byte a) { // where f is face, and a is number of 90 degree turns
  int c=m9(f, 3), i;
  swap(c, c+8, 1);
  while (a--%4) for (i=2; i>=0; --i)
    swap(m9(f, i) + I[i], m9(f, i+1) + I[i+1], 3),
    swap(f*9+i*2, f*9+i*2+2, 2);
  swap(c, c+8, 1);
}

The shortest representation is something like this one: codepen.io/Omelyan/pen/BKmedK

The cube is unwrapped in 1D array (vector of 54 elements). A few-line rotation function swaps stickers and based on the cube's symmetry. Here's complete working model in C, I made it in 2007 when was a student:

const byte // symmetry
  M[] = {2,4,3,5},
  I[] = {2,0,4,6};

byte cube[55]; // 0,0,0,0,0,0,0,0,0, 1,1,1,1,1,1,1,1,1, ... need to be filled first

#define m9(f, m) (m6(f, m)*9)

byte m6(byte f, byte m) {return ((f&~1)+M[m+(f&1)*(3-2*m)])%6;}

void swap(byte a, byte b, byte n) {
  while (n--) {byte t=cube[a+n]; cube[a+n]=cube[b+n]; cube[b+n]=t;}
}

void rotate(byte f, byte a) { // where f is face, and a is number of 90 degree turns
  int c=m9(f, 3), i;
  swap(c, c+8, 1);
  while (a--%4) for (i=2; i>=0; --i)
    swap(m9(f, i) + I[i], m9(f, i+1) + I[i+1], 3),
    swap(f*9+i*2, f*9+i*2+2, 2);
  swap(c, c+8, 1);
}

回复收藏 0 原文

维持三分热 2024-07-20 12:49:13

魔方有：

8 个角，每个角包含一个独特的角立方体。
12 个边，每个边包含一个独特的边立方体。
6 个中心，每个中心包含一个独特的中心立方体。

每个角立方体可以处于 3 个方向之一：

不旋转；
顺时针旋转120°；或
逆时针旋转120°。

每个边缘立方体可以处于 2 个方向之一：

不翻转；或
翻转 180°。

中心立方体相对于彼此固定；然而，有 24 种可能的方向（忽略各个中心的旋转，这仅在您求解图片立方体时才相关），因为有 6 种方法来选取位于立方体“上”面上的中心立方体，然后有 4 种方法选择位于“正面”面上的中心立方体。

您可以将其存储为：

一个由八个 3 位整数组成的数组，每个整数代表角位置的角立方体。
八个 2 位整数的数组，每个整数表示角立方体在角位置的方向。
一个由 12 个 4 位整数组成的数组，每个整数代表边缘位置中的边缘立方体。
一个由 12 个 1 位整数组成的数组，每个整数表示边缘立方体的方向和边缘位置。
一个 5 位整数，表示中心立方体的所有 24 个可能方向的枚举。

总共 105 位（14 字节）。

空间优化：

由于角始终是固定的，因此您可以假设它们永远不会移动并且不需要存储。这样，如果您想要进行 E 移动，则可以进行等效的 U D' 移动对。
这会将大小减少到 100 位（13 字节）。
如果将表示限制为可解立方体，则可以将立方体存储在较小的空间中，如下所示：
- 知道 7 个角立方体后，您就可以算出第 8 个角立方体是什么。
- 角立方体的方向具有固定的奇偶性，因此一旦您知道 7 个角的方向，您就可以推导出第 8 个角的方向。
- 与边类似，您只需存储 12 个边立方体中的 11 个边立方体和边方向，并可以计算剩余的一个。
这又节省了 10 位，总共 90 位（12 字节）。然而，计算出缺失信息所需的计算可能意味着这种空间优化不值得以性能损失为代价。

Space optimisations:

Since the corners are always fixed then you can assume that they never move and do not need to be stored. With this, if you want to do an E move then do an equivalent U D' pair of moves instead.
This would reduce the size to 100 bits (13 bytes).
If you restrict the representation to solvable cubes then it is possible to store the cube in a smaller space as:
- Once you know 7 corner cubelets you can work out what the 8th is.
- The orientation of the corner cubelets has a fixed parity so once you know the orientation of 7 corners you can derive the 8th.
- Similar for the edges, you only need to store 11-of-12 edge cubelets and edge orientations and can calculate the remaining one.
This saves a further 10 bits for a total of 90 bits (12 bytes). However, the calculations required to work out the missing information may mean that this space optimisation is not worth the performance penalty.

More Space Optimisations:

If you really want to optimise the space for the cube the:

the 8 corner cubelets can be arranged in 8! = 40320 permutations and 40320 can be represented in 16 bits.
7 ternary (base-3) digits can represent the orientation of the corners (deriving the position of the 8th) and 3^7 = 2187 and can be represented in 12 bits.
the 12 edge cubelets can be arranged in 12! = 479001600 permutations and 479001600 can be represented in 29 bits.
11 binary digits can represent the orientation of the edges (deriving the position of the 12th) which would be 11 bits.

This gives a total of 68 bits (9 bytes).

The maximum number of permutations of a solvable rubik cube is (8!*3^8*12!*2^12)/12 = 43,252,003,274,489,856,000 ~= 4.3*10^19 which can be stored in 66 bits (9 bytes) and while its possible to enumerate all the possible solutions it is not worth it to save those last 2 bits.

回复收藏 0 原文

固执像三岁 2024-07-20 12:49:13

其他人很好地描述了物理立方体，但是关于立方体的状态......我会尝试使用向量变换数组来描述立方体的变化。这样，您就可以在进行更改时保留魔方的历史记录。我想知道你是否可以将向量乘以变换矩阵来找到最简单的解决方案？

回复收藏 0 原文

邮友 2024-07-20 12:49:13

作为 48 个可以移动的面的排列。基本旋转也是排列，排列可以组合，它们形成一个群。

在程序中，这样的排列将由包含数字 0 到 47 的 48 个元素的数组表示。与数字对应的颜色是固定的，因此可以根据排列计算视觉表示，反之亦然。

回复收藏 0 原文

梦里兽 2024-07-20 12:49:13

我发现将状态存储为从立方体表面外部的中心坐标到颜色的映射非常有用。因此，例如，前右上立方体的上表面是状态[1, -1, 2] 。因此，只需对指数进行旋转即可完成移动。

您可以在这里看到我使用它编写的一个简单模拟器： https://github.com/noamraph/cube

回复收藏 0 原文

真心难拥有 2024-07-20 12:49:12

这篇 ACM 论文描述了几种替代方法用来表示魔方并将它们相互比较。遗憾的是，我没有帐户来获取全文，但描述指出：

提出并比较了魔方的七种替代表示形式：一个由 3 位整数组成的 3×3×3 数组； 6×3×3 文字数组； 5×12 文字矩阵；逐个稀疏文字矩阵； 54 元素向量； 4 维数组；和一个 3×3×3 嵌套数组。给出了用于定向移动和四分之一圈的 APL 函数以及用于求解立方体的几个有用工具。

此外，这个 RubiksCube.java 文件包含一个非常干净的表示与旋转部分的相关代码（如果您正在寻找实际的代码）。它使用单元格和面孔数组。

回复收藏 0 原文

毁梦 2024-07-20 12:49:12

简而言之，这取决于您将如何解决立方体问题。如果您的求解器要使用人工方法（例如逐层方法或 Fridrich 方法），那么底层数据结构不会产生太大影响。即使使用最慢的编程语言，计算机也可以在可忽略不计的时间内（远低于一秒）使用人类方法解算立方体。但是，如果您要使用计算量更大的方法（例如 Thistlethwaite 的 52 步算法、Reid 的 29 步算法或 Korf 的 20 步算法）来解魔方，那么数据结构和编程语言就至关重要。

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

三维字符数组，6x3x3。面的颜色的索引类似于立方体[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

Decoded，如下所示：

WGW
Y G
OBR

另一个优点是，在某些情况下，可以使用一些巧妙的位掩码和标准整数比较来比较立方体状态。对于求解器来说，这可能是一个相当大的加速。

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

扩展上述方法 (4)，一些以编程方式求解魔方的算法使用带有 A* 的迭代加深深度优先搜索，并使用模式数据库作为启发式。例如，Korf 算法使用三种模式数据库：一个存储 8 个角块的索引和方向；另一个存储 8 个角块的索引和方向；另一个存储 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 个立方体组成。使用四元数旋转面。立方体和立方体的代码位于：https:/ /github.com/benbotto/rubiks-cube-cracker/tree/4.0.0/Model/WorldObject

如果您对我的魔方解算器程序感兴趣，YouTube 上有一个高级概述视频：https://www.youtube.com/watch?v=ZtlMkzix7Bw&feature=youtu .be 我在中。

The short answer is that it depends on how you're going to solve the cube. If your solver is going to use a human method like the layer-by-layer approach or the Fridrich method then the underlying data structure won't make much of a difference. A computer can solve a cube using a human method in negligible time (well under a second) even in the slowest of programming languages. But if you are going to solve the cube using a more computationally intensive method such as Thistlethwaite's 52-move algorithm, Reid's 29-move algorithm, or Korf's 20-move algorithm, then the data structure and programming language are of utmost importance.

I implemented a Rubik's Cube program that renders the cube using OpenGL, and it has two different types of solvers built in (Thistlethwaite and Korf). The solver has to generate billions of moves and compare each cube state billions of times, so the underlying structure has to be fast. I tried the following structures:

A three-dimensional array of chars, 6x3x3. The color of a face is indexed like cube[SIDE][ROW][COL]. This was intuitive, but slow.
A single array of 54 chars. This is faster than (1), and the row and stride are calculated manually (trivial).
6 64-bit integers. This method is essentially a bitboard, and is significantly faster than methods (1) and (2). Twisting can be done using bit-wise operations, and face comparisons can be done using masks and 64-bit integer comparison.
An array of corner cubies and a separate array of edge cubies. The elements of each array contain a cubie index (0-11 for edges; 0-7 for corners) and an orientation (0 or 1 for edges; 0, 1, or 2 for corners). This is ideal when your solver involves pattern databases.

Expanding on method (3) above, each face of the cube is made up of 9 stickers, but the center is stationary so only 8 need to be stored. And there are 6 colors, so each color fits in a byte. Given these color definitions:

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

A face might look like this, stored in a single 64-bit integer:

00000000 00000001 00000010 00000011 00000100 00000101 00000000 00000001

Which is decoded as:

WGR
G B
WYO

An advantage of using this structure is that the rolq and rorq bit-wise operators can be used to move a face. Rolling by 16 bits effects a 90-degree rotation; rolling by 32 bits gives a 180-degree turn. The adjacent pieces need to be up-kept manually--i.e. after rotating the top face, the top layer of the front, left, back, and right faces need to be moved, too. Turning faces in this manner is really fast. For example, rolling

00000000 00000001 00000010 00000011 00000100 00000101 00000000 00000001

by 16 bits yields

00000000 00000001 00000000 00000001 00000010 00000011 00000100 00000101

Decoded, that looks like this:

WGW
Y G
OBR

Another advantage is that comparing cube states can in some instances be done using some clever bit masks and standard integer comparisons. That can be a pretty big speed-up for a solver.

Anyway, my implementation is on github: https://github.com/benbotto/rubiks-cube-cracker/tree/2.2.0 See Model/RubiksCubeModel.{h,cpp}.

Expanding on method (4) above, some of the algorithms for programmatically solving the Rubik's Cube use an iterative deepening depth-first search with A*, using pattern databases as a heuristic. For example, Korf's algorithm utilizes three pattern databases: one stores the index and orientation of the 8 corner cubies; one stores the index and orientation of 6 of the 12 edge pieces; the last stores the index and orientation of the other 6 edges. When using pattern databases, a fast approach is to store the cube as a set of indexes and orientations.

Arbitrarily defining a convention, the edge cubies could be indexed as follows.

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).

So the red-yellow edge cubie is at index 0, and the white-green edge cubie is at index 4. Likewise, the corner cubies might be indexed like so:

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

So the red-blue-yellow corner cubie is at index 0, and the orange-green-yellow corner cubie is at index 6.

The orientation of each cubie needs to be kept as well. An edge piece can be in one of two orientations (oriented or flipped), while a corner piece can be in three different orientations (oriented, rotated once, or rotated twice). More details about the orientation of pieces can be found here: http://cube.rider.biz/zz.php?p=eoline#eo_detection With this model, rotating a face means updating indexes and orientations. This representation is the most difficult because it's hard for a human (for me at least) to look at a big blob of index and orientation numbers and verify their correctness. That being said, this model is significantly faster than dynamically calculating indexes and orientations using one of the other models described above, and so it's the best choice when using pattern databases. You can see an implementation of this model here: https://github.com/benbotto/rubiks-cube-cracker/tree/4.0.0/Model (see RubiksCubeIndexModel.{h,cpp}).

As mentioned, the program also renders the cube. I used a different structure for that part. I defined a "cubie" class, which is six squares with 1, 2, or 3 colored faces for center, edge, and corner pieces, respectively. The Rubik's Cube is then composed of 26 cubies. The faces are rotated using quaternions. The code for the cubies and cube is here: https://github.com/benbotto/rubiks-cube-cracker/tree/4.0.0/Model/WorldObject

If you're interested in my Rubik's Cube solver program, there's a high-level overview video on YouTube: https://www.youtube.com/watch?v=ZtlMkzix7Bw&feature=youtu.be I also have a more extensive write-up on solving the Rubik's Cube programmatically on Medium.

回复收藏 0 原文

寄人书 2024-07-20 12:49:12

一种方法是关注视觉外观。

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

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

每一步都是一种排列一组特定彩色方块的方法。

One way would be to focus on the visual appearance.

A cube has six faces and each face is a three-by-three array of squares. So

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

Then each move is a method that permutes a specific set of colored squares.

回复收藏 0 原文

安穩 2024-07-20 12:49: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

使用的内存量非常小，处理量也非常小，以至于完全没有必要进行优化，特别是当您牺牲代码可用性时。

Eschew optimisation; make it object-oriented. A pseudocode class outline I've used is:

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

The amount of memory used is so small and processing so minimal that optimisation is totally unnecessary, especially when you sacrifice code usability.

回复收藏 0 原文