mmc*_*ole 22
本ACM论文描述了几种用于表示魔方的立方体并将它们与彼此进行比较的替代方法.可悲的是,我没有帐号来获取全文,但说明中说明:
提出并比较了Rubik's Cube的七种替代表示:3乘3乘3的3位数整数; 一个6乘3乘3的文字阵列; 一个5乘12的字面矩阵; 一个ll-by-ll稀疏文字矩阵; 一个54元素的向量; 一个四维数组; 和一个3乘3乘3的嵌套数组.APL功能用于定向移动和四分之一圈以及几个用于解决立方体的有用工具.
此外,这个RubiksCube.java文件包含一个非常干净的表示以及旋转部分的相关代码(如果您正在寻找实际代码).它使用一个单元格和面数组.
Hum*_*art 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
使用的内存量非常小,处理量非常小,以至于完全没有必要进行优化,尤其是在牺牲代码可用性时.
joe*_*ely 11
一种方法是专注于视觉外观.
一个立方体有六个面,每个面是一个三乘三的正方形阵列.所以
Color[][][] rubik = new Color[6][3][3];
然后每次移动都是一种置换一组特定彩色方块的方法.
ave*_*dah 10
简短的回答是，这取决于您将如何解出立方体。如果您的求解器将使用人工方法，如逐层方法或弗里德里希方法，那么底层数据结构不会有太大区别。即使使用最慢的编程语言，计算机也可以在可以忽略不计的时间内（远低于一秒）使用人类方法解出立方体。但是，如果您要使用计算量更大的方法求解立方体，例如 Thistlethwaite 的 52-move 算法、Reid 的 29-move 算法或 Korf 的 20-move 算法，那么数据结构和编程语言是最重要的。
我实现了一个使用 OpenGL 渲染立方体的魔方程序，它内置了两种不同类型的求解器（Thistlethwaite 和 Korf）。求解器必须生成数十亿次移动并将每个立方体状态进行数十亿次比较，因此底层结构必须很快。我尝试了以下结构：
对上面的方法（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.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上以编程方式解决魔方问题。
有很多方法可以做到这一点。有些方法比其他方法更有效地利用内存。
我见过人们使用3 x 3 x 3的长方体数组，长方体对象需要存储颜色信息（是的，从未使用过中心对象）。我见过人们使用6个数组，每个数组都是3 x 3的长方体数组。我看过3 x 18的长方体阵列。有很多可能性。
可能更大的问题是如何表示各种转换。旋转一个物理立方体的一个面（所有立方体的移动本质上都是一个面的旋转）必须通过围绕许多长方体对象进行交换来表示。
您的选择应该对您正在编写的任何应用程序都有意义。可能是您仅在渲染多维数据集。可能是没有UI。您可能正在解决多维数据集。
我会选择3 x 18阵列。
有 20 个立方体很重要。因此，一种方法是使用包含 20 个字符串的数组。这些字符串将包含 2 或 3 个表示颜色的字符。任何一个移动都会影响 7 个立方体。所以你只需要为六个面的每一个重新映射器。
注意：此解决方案无法记住白色中心徽标贴纸的方向。
顺便说一句，我曾经帮助某人做过一个魔方软件，大概是 15 年前，但我不记得我们是如何表现它的。