C语言 以编程方式求解魔方

Solving Rubik's cube programmatically

提问by Aravindhan

I am trying to develop a program for solving a Rubik's cube in C. I used back tracking technique for this. It is a very long process and it takes lot of iterations, so I'm not able to solve it.

我正在尝试开发一个用 C 语言求解魔方的程序。为此我使用了回溯技术。这是一个很长的过程，需要大量的迭代，所以我无法解决它。

Please give me suggestions on how to solve this more efficiently - such as other techniques or adopting backtracking itself. In Google I found a lot of shortcuts for solving this but I don't want to solve this by using shortcuts.

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

回答by Toon Krijthe

Why not use a human oriented solution and program this.

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

You need some pattern matching, but it won't be that hard. (Besides there are programs solving the 1000x1000x1000).

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

The basic idea is to work in phases:

基本思想是分阶段工作：

• First layer
• Second layer
• Third layer

• 第一层
• 第二层
• 第三层

For each layer you implement a couple of algorithms that turn pattern X into pattern X'. Each step in a phase should bring the cube close to solving. You can do this by adding a value to each pattern (where higher values are given to more unsolved cubes). You can also add a difficulty (for example the number of turns) so you can select an algorithm based on the best value gain per difficulty (or reach the best result with the least turns).

对于每一层，您都实现了几种将模式 X 转换为模式 X' 的算法。阶段中的每一步都应该使立方体接近求解。您可以通过为每个模式添加一个值来实现这一点（其中更高的值被赋予更多的未解立方体）。您还可以添加难度（例如回合数），以便您可以根据每个难度的最佳值增益选择算法（或以最少的回合达到最佳结果）。

The fun of this approach, is that you can add new algorithms if you like and test how often they are used. So you can test the usefulness of each algorithm.

这种方法的乐趣在于，您可以根据需要添加新算法并测试它们的使用频率。所以你可以测试每个算法的有用性。

If you really want to earn those geekpoints, create a separate language to describe the algorithms and the pattern they are solving.

如果您真的想获得这些极客点，请创建一种单独的语言来描述它们正在解决的算法和模式。

回答by nicola

there are many algorithms to solve the rubik problem, however, you can refer to this optimal one http://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik's_Cube

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

回答by Asaf

I'm not sure I understand your problem and what you mean by shortcuts. If you are using some dynamic programming method for solving the rubik's cube you need to make sure you are looking at enough steps ahead in order to reach a solution. I believe that if you only support 2 types of moves (rotate right, rotate up) you need to look 12 steps (not sure) ahead before deciding on each move in order to ensure a solution.

我不确定我是否理解您的问题以及您所说的快捷方式是什么意思。如果您正在使用某种动态编程方法来解决魔方问题，您需要确保您提前考虑了足够多的步骤才能找到解决方案。我相信，如果您只支持 2 种类型的移动（向右旋转、向上旋转），则在决定每个移动之前，您需要向前看 12 个步骤（不确定）以确保解决方案。

If you are doing something like this and you found that you have run out of space in memory then keep in mind that you only need to retain the path you are traversing in order to decide on the right solution (not the entire tree).

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

I used this approach successfully for solving a rubik's cube in Java so C should have no problems (as far as memory footprint).

我成功地使用这种方法在 Java 中解决了魔方，所以 C 应该没有问题（就内存占用而言）。

回答by Antti Huima

Rubik's cube has state space size in the order of 2⁶⁵. A backtracking algorithm that searches the state space blindly may need to examine a large portion of the state space before it finds the solution, so clearly a simple backtracking algorithm is not going to work very well. But then, this problem is already solved many times. See e.g. http://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf

魔方的状态空间大小约为 2 ⁶⁵。盲目搜索状态空间的回溯算法在找到解之前可能需要检查大部分状态空间，因此很明显简单的回溯算法不会很好地工作。不过话说回来，这个问题已经解决了很多次了。参见例如http://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf

回答by fulmicoton

If you don't care about the number of move involved, here is a way to split the state space so that your bruteforces method work.

如果您不关心所涉及的移动次数，这里有一种分割状态空间的方法，以便您的蛮力方法起作用。

Finding a rubix cube solution for dummies

为傻瓜寻找 rubix 立方体解决方案

• First bruteforce all the rubix facets BUT the corners into places
• then find moves that let invariant thoses facet (e.g. (f.g.f-1.g-1)^3). Two moves are actually sufficient. To find them, consider the permutation involved for corners and for non corners subcubes, and then iterate the ppcm of the corners cycles length to get and invariant on the corners)
• Use your backtracking algorithm to get corners into places (but they still require a rotation, to align colors)
• Find the magic moves that makes to cube on the same segment to rotate together. There is no move that

• 首先蛮力所有rubix刻面但角落到位
• 然后找到让这些方面不变的移动（例如（fgf-1.g-1）^ 3）。其实两招就够了。要找到它们，请考虑角和非角子立方体所涉及的排列，然后迭代角循环长度的 ppcm 以获得角上的不变性）
• 使用您的回溯算法将角定位到位（但它们仍然需要旋转以对齐颜色）
• 找出使同一段上的立方体一起旋转的魔法动作。没有任何动作