2

TrialPay在他们的博客上发布了一个关于蛇魔方谜题的编程问题。

最近，我们的一位工程师向我们介绍了蛇形魔方。蛇形魔方是由一串魔方链组成的拼图，由贯穿每个魔方的松紧带连接。每个立方体可以围绕松紧带旋转 360°，允许根据最初构建链的方式构建各种结构，最终目标是以创建立方体的方式排列立方体。

例子：

在此处输入图像描述

这种特殊的排列包含 17 组立方体，由 8 组两个立方体和 9 组三个立方体组成。这种排列可以用多种方式表达，但为了本练习的目的，让“0”表示旋转不会改变拼图方向的棋子，或者可以认为是“直”棋子，而“1”将表示旋转会改变拼图配置或“弯曲”蛇的部分。使用该模式，上面的蛇拼图可以描述为 001110110111010111101010100。

挑战：

你的挑战是用你选择的任何语言编写一个程序，它将立方体维度（X、Y、Z）和二进制字符串作为输入，如果可以解决问题，则输出“1”（不带引号）谜题，即在给定立方体方向的情况下构造一个适当的 X Y Z 立方体，如果当前排列无法解决，则为“0”。

我发布了解决方案的半详细说明，但是如何确定程序是否解决了问题？本来想弄更多的测试用例，但是遇到了一些问题：

  1. TrialPay 博客中的蛇形立方体示例与维基百科的蛇形立方体页面和 www.mathematische-basteleien.de 上的图片具有相同的组合。
  2. 手动将图像转换为字符串非常繁琐。

我试图制作一个可以产生很多组合的程序：

#We should start at the binary representation of 16777216 (00100...), because
#lesser numbers have more than 2 consecutive 0s (000111...)
i = 16777216
solved = []
while i <= 2**27:
    s = str(bin(i))[2:]
    #Add 0s
    if len(s) < 27:
        s = '0'*(27-len(s)) + s
    #Check if there are more than 2 consecutive 0s
    print s
    if s.find("000") != -1:
        if snake_cube_solution(3, 3, 3, s) == 1:
            solved.append(s)
    i += 1

但它只需要永远完成执行。有没有更好的方法来验证程序？

提前致谢！

4

3 回答 3

3

TL;DR：这不是编程问题，而是数学问题。math.stackexchange.com可能会为您提供更好的服务。

由于立方体大小和蛇长度作为输入传递，因此检查程序需要验证的输入空间基本上是无限的。即使检查单个输入的解决方案的答案是合理的，但在整个输入空间中强制进行这种检查显然是不合理的。

如果您的解决方案在某些情况下失败，您的检查程序可以帮助您找到这些。但是它不能确定您的程序的正确性：如果您的解决方案实际上是正确的，则检查器将永远运行并让您感到疑惑。

不幸的是（或不是，取决于您的口味），您要寻找的不是程序，而是数学证明。

（证明）算法正确性本身就是一个完整的研究领域，你可以花很长时间在里面。也就是说，归纳证明通常是适用的（尤其是对于递归算法。）

其他时候，在状态配置之间导航可以重述为优化效用函数。证明正在优化的空间（例如它只有一个极值）可以转化为程序正确性的证明。

您在第二种方法中的状态配置可能是蛇方向，或者它们可能是一些更深层次的结构。例如，解决魔方的一般策略通常不是在字面的魔方状态上陈述，而是在一组相关对称性的表达式上陈述。这就是我个人期望您的解决方案最终会发挥作用的结果。

编辑：多年后，我觉得我应该指出，对于给定的、固定的立方体大小和蛇的长度，当然搜索空间实际上是有限的。您可以编写一个程序来蛮力检查所有组合。如果你很聪明，你甚至可以争辩说检查一组案例的时间可以被视为一组独立的随机变量。由此您可以建立一个合理的进度条来估计您的等待时间（非常）长。

于 2012-07-24T07:29:43.740 回答
0

我认为您关于不能连续三个 0 的断言是错误的。考虑这种安排：

000
  100
    101
      100
        100
          101
            100
              100
                100

我在这个谜题中遇到的问题之一是符号。A1表示立方体可以改变拼图的方向，但是关于哪个轴？在上面的示例中，假设 Y 轴是垂直的，X 轴是水平的。1左边的A表示绕立方体 Y 轴旋转1的能力，右边的 a 表示绕立方体 X 轴旋转的能力。

我认为可以构建一个类似于上面的安排，但有三个000组。但我没有它的符号。显然，可以修改上面的示例，以便前三行是：

001
  000
    101

第一段1表示绕 Y 轴旋转。

于 2012-07-24T11:17:36.967 回答
0

不久前，我为同样的问题编写了一个 Java 应用程序。

我为此使用了回溯算法。

您只需在整个立方体中进行递归搜索，检查哪些方向是可能的。如果你找到了，你可以停下来打印解决方案（我选择打印出所有解决方案）。

对于 3x3x3 的立方体，我的程序在一秒钟内解决了它们，对于较大的立方体，它需要大约 5 秒到 15 分钟。

很抱歉，我现在找不到任何代码。

于 2015-09-08T20:30:53.223 回答