主页 / 问题 / 845868
Accepted
Isaev
Asked:2020-06-24 00:59:42 +0000 UTC2020-06-24 00:59:42 +0000 UTC

在任意大小的魔方上排列贴纸的算法

  • 772

面旋转示例 RU R' 假设有一个任意大小 NxNxN 的魔方。

在输入处，我们有块 A(Xa, Ya, Za) 的初始位置，最终位置 B(Xb, Yb, Zb) 以及围绕块在移动过程中转向的三个轴的旋转角度。 .. 运动轨迹可能非常混乱，我们并不感兴趣。这些输入数据绝对唯一地确定了其中一个块的最终状态（位置和转弯）。我正在尝试推导一种算法，根据输入数据，该算法将返回贴纸在此块上移动的位置。

我们来看图中的一个例子：

数字 1 表示块 A(0, 2, 2) 的初始位置。
数字 2 是块 B(2, 2, 0) 的最终位置。
为了更好地理解，我们可以添加从第一个位置开始的第二个位置，在这种情况下，我们通过滚动获得： (RU R ') （下面的描述）因此，我们围绕三个轴 R (-90, 90, 0) (即当旋转 R 块 1 没有改变位置时，U 顺时针转动 Y，R' - 逆时针转动 X）。

在输出中，你需要计算如果初始位置的白色贴纸在上面，那么在最终位置它变成了前面，分别是橙色在左边，变成了上面，蓝色在后面，变成了右边

重要的是我们不知道转弯是什么，输入处没有转弯，您可以以不同的方式到达最终位置并进行其他转弯，尽管外观上没有任何变化（其他块将在其他地方，但我们对它们不感兴趣），因为尚不清楚在算法中使用它们，但它们是必要的！
那些。使用链，例如（LF），我们会发现自己处于相同的位置，也颠倒了，但颠倒将在输入 R(90, 0, 90) 处，使用链 (L2 DR)，我们也会达到所需位置并反转，但反转将是 R(90, -90, 0)。

需要从外面焕然一新，我有点挂了！

PS：

  1. 旋转的经典符号： U p, D own, L eft, R ight, F ront, B ack 用于顺时针旋转的边名的首字母（如果它在我们面前）并带有撇号，例如 R ' 用于逆时针旋转，以及 2，例如 R2 用于 180 度旋转。

  2. 经典配色：F-绿色、U-白色、B-蓝色、R-红色、L-橙色、D-黄色。

  3. 这项工作是通过立方体的二维标记进行的。

    二维立方体布局

深思熟虑：我是唯一一个认为这里存在某种逻辑错误的人吗？让我们看几个简单的例子（在每个例子中，我们按照右上角）：

  1. 我们滚动F2 L2
    我们有一个反转向量 R(180, 0, 180)，它没有沿 Y 轴旋转，但是如果我们不知道它是如何放置在那里的，我们可以肯定地说它围绕 Y 轴旋转了180！

  2. 滚动RBLF
    观察到的立方体回到原来的位置，即 坐标向量 (0, 0, 0) 的差异，绕轴的圈数减少，我们也得到 R(0, 0, 0)。那些。完全没有信息，但立方体顺时针旋转！

  3. 滚动F' L' B' R'
    观察到的立方体回到原来的位置，即 坐标向量 (0, 0, 0) 的差异，围绕轴的旋转也减少了，我们也得到 R(0, 0, 0)。那些。再一次，完全没有信息，但是立方体已经逆时针转动了！

алгоритм

2 个回答

  1. Best Answer

    让我们试着写一个算法。我提出了一种算法——广度优先搜索。

    1. 让我们定义立方体的对象。一个立方体有 6 个面。6种颜色。每边有9个元素。6 × 9 = 54让我们用一个由 54 ( ) 个元素组成的数组来描述立方体。那么最终目标是每 9 个元素相等。让我们“绘制”模型。

                18 19 20
          21 22 23
          24 25 26
0  1  2   9  10 11  36 37 38   45 46 47
3  4  5   12 13 14  39 40 41   48 49 50
6  7  8   15 16 17  42 43 44   51 52 53
          27 28 29
          30 31 32
          33 34 35

    2. 让我们定义可以用多维数据集完成的操作。因此，我们有 6 个面，每条边都可以围绕自己的轴在两个方向上旋转。所以，我们有6 × 2 = 12行动。您需要描述所有 12 个动作。我将向您描述一个，其余的 - 我自己。为了描述，将交换元素。为清楚起见，让我们围绕自己旋转面 9-17，然后我成对指示将交换位置的元素：

                  18     19    20
            21     22    23
            24-36  25-39 26-42
0  1  2-26  9-11  10-14 11-17    36-29  37 38   45 46 47
3  4  5-25  12-10  13    14-16    39-28  40 41   48 49 50
6  7  8-24  15-9   16-12 17-15    42-27  43 44   51 52 53
            27-2   28-5  29-8
            30     31     32
            33     34     35

    以对的形式，这将是形式

    24-36、25-39、26-42、2-26、9-11、10-14、11-17、36-29.5-25、12-10、14-16、39-28、8-24、 15-9、16-12、17-15、42-27、27-2、28-5、29-8

    20双出来了。12 + 8 = 20。如果这对反转，将会有相反方向的旋转。应该有 12 对这样的 20 件。我展示一个。

    我将尝试在 3D 中描述图形的旋转。旋转只会发生在 9 个元素上，从第 9 个到第 17 个，包括 13 个。如果是 2D 投影，其余的将不会旋转，并且已经将其转换为 3D 投影，我们有更多选择。

    打包版本的反转 a[i] = (a[i] & 7) + ((a[i] + 8) & (8+16))并a[i] = (a[i] & 7) + ((a[i] - 8) & (24))在排列后将其应用于 9 个元素。然后(a[i] & 24) = {0,8,16,24}根据转弯。

    反转选项很简单，使用 and x.size = (x.side+1)&3orx.size = (x.side-1)&3

    转弯选项很复杂if (x.size=3) x.size = 0; else x.size++或 if (x.size=0) x.size = 3; else x.size--

    UPD重要提示：旋转时，最好创建一个单独的数组，因为您可能会“不小心”两次分配同一个单元格。例如，当我们在 11 分配 9，在 17 我们分配 11 - 我们得到一个“失败”，所以在分配的左边应该有原始数组，而在右边（我们分配的地方） -原始数组的副本。

    TOTAL：我们做了 20 次排列操作，然后是 9 次 2D 旋转操作，而 9 次中的一个是 20 次中未包含的中心元素。

    1. 拥有一个立方体对象，让我们定义最终条件：它将是 o[0]=o[1]=...=o[8], o[9]=o[10]=...=o[17], ...,即。数组的每 9 个元素都必须相等。

    2. 现在我们有了一个“对象”，我们创建一个对象数组，并开始构建一棵树。每个新级别都会向数组中添加几个元素。这是必要的，以消除“额外”运动，并使用广度优先搜索找到解决方案。

      我们创建一个结构 (#iteration, #action(1-12), #element 导致 this 的出现, "object" (array by 54)) 接下来，我们构建第一次迭代，即 循环 12 个面的排列，我们得到

       a[0]=(0,0,0,-1,obj),a[1]=(1,1,0,obj),a[2]=(1,2,0,obj),a[3]=(1,3,0,obj),
 a[4]=(1,4,0,obj)..a[12]=(1,12,0,obj);

      每个对象，我们检查条件[3]。我们进行第二次迭代。这里已经有问题了。将出现重复项。当我们首先将同一张脸向左旋转，然后在第二次迭代中向右旋转时，就会形成双打。您可以弄清楚如何通过算法避免这种情况，但这很困难。此外，您仍然需要过滤 4x 旋转等，因此仅过滤重复项会更容易。也就是说，对于我来说——这更容易——通过添加一个新的数组元素来检查——在元素a[0]…a[n]( a[12]) 中是否有重复项。第二次迭代将带来12 × 12 = 144元素，但一半将完全重复。因此，某处会有+72个元素。为了简化，让我们这样做。第二层看起来像这样

       a[0]=(0,0,0,-1,obj),a[1]=(1,1,0,obj),a[2]=(1,2,0,obj),a[3]=(1,3,0,obj),
 a[4]=(1,4,0,obj)..a[12]=(1,12,0,obj);
 a[13]=(2,1,1,obj),a[14]=(2,1,2,obj)...a[84]=(2,12,6,obj)

    之后，我们重复迭代直到找到解决方案（即不满足条件 [3]。可以从数组中建立事件的过程（即如果答案是 84，则 84 生成元素 6，它产生元素 0。在元素 6 中，指示它们旋转的位置）。

    PS 3D渲染时，会有6 × 4 = 24图片的位置。如果渲染是平滑的，则需要从 24 个位置之一平滑过渡到另一个位置。正方形可以通过 4 种方式粘在立方体上。

    立方体有 6 个面，因此对于 3D，您有 24 个选项。但是如果你用24个选项来操作，那么轮换任务就变得更复杂了，因为 您将不得不旋转所有 20 个元素（来自 [2] 的 20 对）。用 4 种组合旋转 9 元素更容易，并在 3D 渲染阶段添加 +6 组合（6 - 取决于我们在立方体的哪一侧）。那些。渲染时，它将是realside = side+ kubeside* 4where size- 54 个元素之一的值，sizewithin[0..3]和kubesidewithin [0..5]- 表示我们在立方体的哪一侧。投影到 2D 空间后，这 24 个选项可能会变成 12 个或更少，但数字 24 提供了“消除”混乱的基础。那些。设置顺序，使得面部不能“朝错误的方向”转动。

    在我看来，大约 24 种组合并不完全清楚。我会努力画

            ^ ^ ^
        < ^ v
        > > > 
 < ^ >  ^ ^ >  ^ ^ ^  > > >
 < v >  v v >  ^ < <  < ^ v
 < v >  ^ ^ v  < < <  v v v
        < < >
        ^ ^ >
        V V V

    这是二维尺度上 4 个位置的组合。它乘以 6 个选项，因为 6 个面中的每一个都必须以 6 种方式在 3D 中渲染。并且 3D 模型将是……您需要考虑可以快速绘制的内容……这意味着该组合0..53 × 4 варианта развотота × 6 вариантов нахожнения на стороне将始终提供独特的 3D 矢量。0..53 将给出向量的明确 3D 坐标，并且 24 ( 4 × 6) 将给出一个转弯，向量的方向是三维的。那些。您可以制作一个包含 54 个坐标和 24 个方向向量的数组 - 并且 3D 转换将顺利进行。

    我画了 24。在 2D 中，我们将有 4 个平面向量：0、90、180、270（在 XY 平面中旋转）。

    在 3D 中，此类旋转（XY、XZ、YZ）将被叠加。

      ^y           2 (0,0,90)
  0(0,270,0)   1 (0,0,0)   4(0,90,0)  5(0,0,180)
               3 (0,0,270)        --x>

    我希望我正确地以度数绘制了旋转矢量。通过将 (0, 90, 180, 270) 添加到第一个 XY 旋转坐标，我们得到 24 种旋转组合。

    第 5 个（后）是有争议的，如果它在 XZ 中旋转 180 度，在 YZ 中再次旋转 180 度，那么我们将得到几乎“镜像形式”的“物体的初始位置”。 5(0,180,0)分不清哪个是对的，哪个是对的，哪个是 5(0,180,0) 对5(0,180,180)的5(0,0,180)。

    加速。由于左右转动立方体的一侧等是没有意义的，因此您可以在 12 的循环中添加禁止此操作的条件。例如，所以

       if (level >= 2) /*then*/ {
      if (( a[a[i].prev].turn & 14 ) == (turn & 14)) /*then*/{ 
         // Если предыдущую грань двигали  ту же самую
         if (a[a[i].prev].turn != turn )  /*then*/
            continue; //Если Если предыдущую грань двигали в другую сторону
         // то не рассматриваем дальше, убрать туда-сюда движение
         // сюда код прийдёт, если более одного раза двигаем одну грань   
         if (a[a[a[i].prev].prev].turn == turn)
            continue; // Запрет поворачивать третий раз куб в одну сторону                      
      }

    那些。最后，算法会是这样的。

    1. 我们设置初始条件
    2. 迭代开始，循环 12 个动作
    3. 我们检查不必要的动作的条件，如果有，转到2。
    4. 我们执行动作，准备一个`
    5. 我们检查立方体被“收集”的“边界条件”。如果组装，则已找到解决方案。
    6. 检查 a' 是否不在数组 a 中。如果存在，请转到步骤 2。
    7. 将 a' 添加到数组中，然后移至 2。
    8. 在循环结束时，我们创建另一个迭代。

    在阅读了 Wikipedia 上的魔方后，我找到了一个条目，在 20 步中你可以找到解决方案。也许限制为 20 的深度优先搜索会更有效。对于这样的搜索，将需要一个 20 的数组，而不是像这个选项中的几千个。

    • 9

  2. 也许有人会派上用场：使用四元数找到了“正确”的解决方案。如果您不需要每个面的平滑旋转，而是需要固定旋转（如在二维扫描中），那么一盘单位四元数就足够了。它们通过旋转来描述所有可能的值，并且比矩阵旋转有一个很好的优势：无限相乘，它们相互传递而不会落入所谓的“铰链锁”。对于平滑的 3D 动画，在最终位置的四元数之间进行插值同样容易。
    此外，作为优化，生成了它们的整数乘法表，以免降低浮点运算的性能，也不会累积计算误差。
    结果，总运行时间几乎没有受到影响（每增加 1 亿个组合需要 2 秒）

    • 1

相关问题