我正在尝试开发一个程序来解决C中的魔方问题。我使用了反向追踪技术。这是一个非常漫长的过程，需要大量的迭代，所以我无法解决它。以编程方式解决魔方问题

请给我关于如何更有效地解决这个问题的建议 - 比如其他技术或采用回溯本身。在谷歌我发现了很多解决这个问题的捷径，但我不想通过使用快捷方式来解决这个问题。

来源

2011-04-06 Aravindhan

你所说的“快捷方式”意思？ – 2011-04-06 08:47:36

http://www.chessandpoker.com/rubiks-cube-solution.html看到这个链接..在这里他们将在5分钟内解决这个问题。 – Aravindhan 2011-04-06 08:49:25

您是否介意修改您的问题以包含更清楚地说明您当前方法的代码？为了清晰起见，我已经编辑了一些问题。 – 2011-04-06 08:58:00

为什么不使用以人为本的解决方案并对其进行编程。

你需要一些模式匹配，但它不会那么难。（除了有解决1000x1000x1000的程序）。

的基本思想是在阶段的工作：对于每个层要实现一对夫妇的算法，把模型X

第一层
第二层
第三层

到模式X'中。阶段中的每一步都应该使立方体接近解决。您可以通过为每个模式添加一个值来实现这一点（更高的值赋予更多未解决的多维数据集）。您还可以添加一个难度（例如转数），以便您可以根据每个难度的最佳值增益选择算法（或以最小转数达到最佳结果）。

这种方法的好处是，如果你喜欢，你可以添加新的算法，并测试它们的使用频率。所以你可以测试每种算法的有用性。

如果您确实想要获得这些geekpoints，请创建一种单独的语言来描述算法和他们正在解决的模式。

来源

2011-04-06 08:55:25

对于较大的立方体来说，比逐层更好的方法是解决中心然后边缘问题，最终解决由此产生的3x3x3 – hoang 2012-10-30 15:42:09

这是可以通过DP来解决的吗？ – pranavk 2012-12-24 08:42:29

@pranavk这取决于[什么DP意味着]（https://en.wikipedia.org/wiki/DP#Technology）。 – 2014-04-27 01:17:04

我不确定我是否理解你的问题，以及你的意思是什么。如果您正在使用一些动态编程方法来解决rubik的立方体，那么您需要确保您正在寻找足够的步骤才能找到解决方案。我相信，如果您只支持两种类型的移动（向右旋转，向上旋转），则需要在确定每一步之前查看12个步骤（未知），以确保解决方案。

如果您正在做这样的事情，并且您发现内存空间不足，那么请记住，您只需要保留要穿过的路径，以便决定正确的解决方案（而不是整个树）。

我用这种方法成功地解决了Java中的rubik's cube，所以C应该没有问题（就内存占用情况而言）。

来源

2011-04-06 08:56:55 Asaf

有很多算法来解决魔方问题，但是，你可以参考这个最佳的一个 http://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik's_Cube

来源

2011-04-06 09:03:22 nicola

魔方具有在2 订单状态空间的大小。一种盲目搜索状态空间的回溯算法可能需要在找到解决方案之前检查大部分状态空间，因此显然，简单的回溯算法不能很好地工作。但是，这个问题已经解决了很多次了。见例如http://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf

来源

2011-04-07 04:53:38

如果你不关心此举涉及的数量，这里是分裂的状态空间，使您的bruteforces方法的工作方式。

找到适合假人的Rubix立方体的解决方案

首先暴力破解所有的Rubix方面，但边角到地方
然后找到举动，让不变放入系统方面（例如，（FGF-1.G-1）^3）。两招实际上就足够了。为了找到它们，考虑包含角落和非角落子骰子的置换，然后迭代拐角周长的ppcm以得到并且在角落上不变）
使用你的回溯算法来获得角落（但它们仍然需要旋转，对齐颜色）
发现魔术的举动，使得以立方体在同一网段一起转动。没有举动

来源

2011-04-17 13:54:41 fulmicoton

以编程方式解决魔方问题

回答

找到适合假人的Rubix立方体的解决方案

相关问题