如果您正在开发解决魔方的软件，您将如何表示魔方？
Mendokusai
问问题
31696 次
12 回答
24
这篇ACM 论文描述了它用来表示魔方的几种替代方法，并将它们相互比较。可悲的是，我没有获得全文的帐户，但描述指出：
展示并比较了七种魔方的替代表示形式： 3×3×3 的 3 位整数数组；一个 6×3×3 的文字数组；一个 5×12 的文字矩阵；一个 ll-by-ll 稀疏文字矩阵；一个 54 元素的向量；一个4维数组；和一个 3×3×3 嵌套数组。为定向移动和四分之一转提供了 APL 函数，以及一些用于求解立方体的有用工具。
此外，这个RubiksCube.java文件包含一个非常干净的表示以及用于旋转部分的相关代码（如果您正在寻找实际代码）。它使用单元格和面数组。
于 2009-02-01T05:33:08.427 回答
14
一种方法是专注于视觉外观。
一个立方体有六个面，每个面都是一个 3×3 的正方形阵列。所以
Color[][][] rubik = new Color[6][3][3];
然后每一步都是一种排列一组特定彩色方块的方法。
于 2009-02-01T05:11:24.273 回答
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
使用的内存量如此之小，处理量如此之小，以至于完全没有必要进行优化，尤其是当您牺牲代码可用性时。
于 2010-08-26T15:00:55.017 回答
12
简短的回答是，这取决于您将如何解决多维数据集。如果您的求解器要使用人工方法，例如逐层方法或 Fridrich 方法，那么底层数据结构不会有太大的不同。即使在最慢的编程语言中，计算机也可以使用人类方法在可忽略不计的时间内（远低于一秒）求解立方体。但是，如果您要使用计算量更大的方法来求解立方体，例如 Thistlethwaite 的 52 步算法、Reid 的 29 步算法或 Korf 的 20 步算法，那么数据结构和编程语言至关重要。
我实现了一个使用 OpenGL 渲染立方体的魔方程序，它内置了两种不同类型的求解器（Thistlethwaite 和 Korf）。求解器必须生成数十亿次移动并对每个立方体状态进行数十亿次比较，因此底层结构必须快速。我尝试了以下结构：
- 一个 3 维字符数组，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
解码，看起来像这样：
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 个角块的索引和方向。一个存储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.crider.co.uk/zz.php?p=eoline#eo_detection 使用此模型，旋转面部意味着更新索引和方向。这种表示是最困难的，因为人类（至少对我而言）很难查看一大堆索引和方向数字并验证它们的正确性。话虽如此，该模型比使用上述其他模型之一动态计算索引和方向要快得多，因此它是使用模式数据库时的最佳选择。您可以在此处看到此模型的实现：https ://github.com/benbotto/rubiks-cube-cracker/tree/2.2.0/Model （参见 参考资料RubiksCubeIndexModel.{h,cpp}）。
如前所述，该程序还呈现立方体。我为那部分使用了不同的结构。我定义了一个“cubie”类，它是一个六个正方形，分别有 1、2 或 3 个彩色面，分别用于中心、边缘和角块。魔方由 26 个魔方组成。使用四元数旋转面。立方体和立方体的代码在这里：https ://github.com/benbotto/rubiks-cube-cracker/tree/2.2.0/Model/WorldObject
如果您对我的魔方求解程序感兴趣，YouTube 上有一个高级概述视频：https ://www.youtube.com/watch?v=ZtlMkzix7Bw&feature=youtu.be我也有更广泛的文章在Medium上以编程方式求解魔方。
于 2019-04-03T23:35:56.690 回答
8
“Cube Explorer”软件使用了一种有趣的方法来表示立方体。使用许多巧妙的数学方法，该方法可以仅使用 5 个整数来表示立方体。作者在他的网站上解释了他的程序背后的数学。根据作者的说法，该表示适合实现快速求解器。
于 2009-02-09T06:26:50.393 回答
6
有很多方法可以做到这一点。有些方法比其他方法更有效地利用内存。
我见过人们使用 3 x 3 x 3 的长方体对象数组，长方体对象需要存储颜色信息（是的，从不使用该中心对象）。我见过人们使用 6 个数组，每个数组都是 3 x 3 的长方体数组。我见过一个 3 x 18 的长方体阵列。有很多可能性。
可能更大的问题是如何表示各种变换。旋转物理立方体的单个面（所有立方体移动本质上都是单个面的旋转）必须通过交换许多立方体对象来表示。
您的选择应该对您正在编写的任何应用程序都有意义。可能您只是在渲染立方体。可能是没有UI。你可能正在解魔方。
我会选择 3 x 18 阵列。
于 2009-02-01T05:04:18.610 回答
5
有 20 个立方体很重要。因此，一种方法是作为 20 个字符串的数组。字符串将包含 2 或 3 个指示颜色的字符。任何一个动作都会影响 7 个小方块。因此，您只需要为六个面中的每一个面重新映射。
注意：此解决方案无法记住位于白色中心的徽标贴纸的方向。
顺便说一句，我曾经帮助某人做过一次软件魔方，也许是 15 年前，但我不记得我们是如何表示它的。
于 2009-02-01T05:24:19.647 回答
3
你可以把立方体想象成三个垂直的循环链表，它们与三个水平链表相交。
每当旋转立方体的某一行时，您只需旋转相应的指针。
它看起来像这样：
struct cubeLinkedListNode {
cubedLinkedListNode* nextVertical;
cubedLinkedListNode* lastVertical;
cubedLinkedListNode* nextHorizontal;
cubedLinkedListNode* lastHorizontal;
enum color;
}
您实际上可能不需要 2 个“最后一个”指针。
[我用 C 做这个，但它可以在 Java 或 C# 中完成，只需为 cubeLinkedListNode 使用一个简单的类，每个类都包含对其他节点的引用。]
请记住，有六个互锁的循环链表。3 垂直 3 水平。
对于每次旋转，您只需遍历相应的循环链表，依次移动旋转圆的链接以及连接圆。
至少是这样的……
于 2009-02-01T05:24:16.977 回答
1
最短的表示是这样的：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);
}
于 2020-06-24T15:24:26.063 回答
0
其他人很好地描述了物理立方体，但关于立方体的状态......我会尝试使用一组矢量变换来描述立方体的变化。这样，您可以在进行更改时保留魔方的历史记录。我想知道您是否可以将向量乘以变换矩阵以找到最简单的解决方案？
于 2009-02-01T05:52:43.817 回答
0
作为可以移动的48个面的排列。基本的旋转也是排列，排列可以组合，它们形成一个群。
在程序中，这样的排列将由包含数字 0 到 47 的 48 个元素的数组表示。与数字对应的颜色是固定的，因此可以从排列中计算出视觉表示，反之亦然。
于 2009-02-01T06:38:08.903 回答
0
我发现将状态存储为从面外立方体中心坐标到颜色的映射非常有用。因此，例如，前右上方立方体的上表面是state[1, -1, 2]。因此，只需对索引应用旋转即可完成移动。
您可以在这里看到我使用它编写的一个简单模拟器：https ://github.com/noamraph/cube
于 2022-01-08T21:54:40.837 回答