魔方还原代码 python_如何用C语言还原三阶魔方？

本答案由3部分组成。第一部分是最早看到题目时我的想法。第二部分是我调研了一圈现有程序之后提出的我觉得比较暴力的解法，并附上C语言源代码。第三部分补充了一些思考，这部分会有少量魔方术语，如看不懂可以直接作为专业名词跳过即可。

根据经验，如果你没有玩过魔方，那么最简单的步骤是：先学会复原魔方。或者如果觉得背公式太烦，至少能够在看着教程的基础上一步一步跟着教程复原魔方。

把教程的每个步骤用C语言写出来。

其实有很多更简单粗暴有效的还原方法，但那些方法通常要求你对魔方有着更深刻的认识，可能会花费你更多的时间，并且更难调试。

==========分割线==========

花了大约半个晚上调研了一下百度到的各种C语言解魔方的程序，基本上还真都是层先法的计算机实现。讲道理，层先法是用来给人学的，用C语言实现自然不会有什么难点，只是非常繁琐，需要输入各种公式，做各种繁琐的状态判断。于是我决定不讲道理，用暴力流另辟蹊径。给题主提供一个完全不一样的思路。

具体算法思路如下：

每次随机做公式，检查还有多少个块没有好，如果比做公式之前少，则更新状态，否则推倒重来，继续随机做公式，直到还原。其中，我把棱块的优先级调整的比角块更高，主要是为了省事。

每次做的公式由以下三部分组成随机转5步。

随机选取3个转动，如A，B，C。构造如下公式：A B A' C A B' A' C'。然后做这个公司或其任意位置开始的循环8步，如B' A' C' A B A' C A等。其中带“'”代表逆转动。

转第1部分的逆序。

实测表明，大部分状态都能秒出解。有些状态会卡在两角翻，不过卡一会儿了以后基本也能最终解出来。当然解法肯定比较长，但相信我，相比别的算法，这个算法更容易实现，你甚至都不需要会还原魔方。

源代码如下。注释并不多，核心算法写在了void solve(int *)函数里，别的各种函数用来辅助。魔方的存储方式是直接用一个54长的数组来存魔方表面每一片的颜色，于是魔方的转动就变成了对数组的置换操作。剩下的就是在这样简单的数据结构上实现我说的暴力流算法了。

#include

#include

#include

// cube definition:

//

// |************|

// |*U1**U2**U3*|

// |************|

// |*U4**U5**U6*|

// |************|

// |*U7**U8**U9*|

// |************|

// ************|************|************|************|

// *L1**L2**L3*|*F1**F2**F3*|*R1**R2**R3*|*B1**B2**B3*|

// ************|************|************|************|

// *L4**L5**L6*|*F4**F5**F6*|*R4**R5**R6*|*B4**B5**B6*|

// ************|************|************|************|

// *L7**L8**L9*|*F7**F8**F9*|*R7**R8**R9*|*B7**B8**B9*|

// ************|************|************|************|

// |************|

// |*D1**D2**D3*|

// |************|

// |*D4**D5**D6*|

// |************|

// |*D7**D8**D9*|

// |************|

//

// -> U1U2U3U4U5U6U7U8U9R1R2R3R4R5R6R7R8R9F1F2F3F4F5F6F7F8F9D1D2D3D4D5D6D7D8D9L1L2L3L4L5L6L7L8L9B1B2B3B4B5B6B7B8B9

const int U1 = 0, U2 = 1, U3 = 2, U4 = 3, U5 = 4, U6 = 5, U7 = 6, U8 = 7, U9 = 8,

R1 = 9, R2 = 10, R3 = 11, R4 = 12, R5 = 13, R6 = 14, R7 = 15, R8 = 16, R9 = 17,

F1 = 18, F2 = 19, F3 = 20, F4 = 21, F5 = 22, F6 = 23, F7 = 24, F8 = 25, F9 = 26,

D1 = 27, D2 = 28, D3 = 29, D4 = 30, D5 = 31, D6 = 32, D7 = 33, D8 = 34, D9 = 35,

L1 = 36, L2 = 37, L3 = 38, L4 = 39, L5 = 40, L6 = 41, L7 = 42, L8 = 43, L9 = 44,

B1 = 45, B2 = 46, B3 = 47, B4 = 48, B5 = 49, B6 = 50, B7 = 51, B8 = 52, B9 = 53;

const char *move2str[18] = {

"U", "U2", "U'",

"R", "R2", "R'",

"F", "F2", "F'",

"D", "D2", "D'",

"L", "L2", "L'",

"B", "B2", "B'"

};

const int PRE_MOVE_LENGTH = 5;

// cube[idx1] -> cube[idx2] -> cube[idx3] -> cube[idx4] -> cube[idx1], rep+1 times

void swap4(int *cube, int idx1, int idx2, int idx3, int idx4, int rep) {

int tmp;

for (int i = 0; i <= rep; ++i) {

tmp = cube[idx4];

cube[idx4] = cube[idx3];

cube[idx3] = cube[idx2];

cube[idx2] = cube[idx1];

cube[idx1] = tmp;

}

}

//move = axis * 3 + power

//axis: U=0, R=1, F=2, D=3, L=4, B=5

//power: 0=clockwise, 1=180 degrees, 2=anti-clockwise

void doMove(int *cube, int move) {

int tmp;

int axis = move / 3;

int power = move % 3;

switch (axis) {

case 0:

swap4(cube, U1, U3, U9, U7, power);

swap4(cube, U2, U6, U8, U4, power);

swap4(cube, F1, L1, B1, R1, power);

swap4(cube, F2, L2, B2, R2, power);

swap4(cube, F3, L3, B3, R3, power);

break;

case 1:

swap4(cube, R1, R3, R9, R7, power);

swap4(cube, R2, R6, R8, R4, power);

swap4(cube, U3, B7, D3, F3, power);

swap4(cube, U6, B4, D6, F6, power);

swap4(cube, U9, B1, D9, F9, power);

break;

case 2:

swap4(cube, F1, F3, F9, F7, power);

swap4(cube, F2, F6, F8, F4, power);

swap4(cube, U7, R1, D3, L9, power);

swap4(cube, U8, R4, D2, L6, power);

swap4(cube, U9, R7, D1, L3, power);

break;

case 3:

swap4(cube, D1, D3, D9, D7, power);

swap4(cube, D2, D6, D8, D4, power);

swap4(cube, F7, R7, B7, L7, power);

swap4(cube, F8, R8, B8, L8, power);

swap4(cube, F9, R9, B9, L9, power);

break;

case 4:

swap4(cube, L1, L3, L9, L7, power);

swap4(cube, L2, L6, L8, L4, power);

swap4(cube, U1, F1, D1, B9, power);

swap4(cube, U4, F4, D4, B6, power);

swap4(cube, U7, F7, D7, B3, power);

break;

case 5:

swap4(cube, B1, B3, B9, B7, power);

swap4(cube, B2, B6, B8, B4, power);

swap4(cube, U3, L1, D7, R9, power);

swap4(cube, U2, L4, D8, R6, power);

swap4(cube, U1, L7, D9, R3, power);

break;

}

}

int distance(int *cube1, int *cube2) {

int distanceEdge = 0;

int distanceCorn = 0;

for (int i = 0; i < 54; ++i) {

if (cube1[i] == cube2[i]) {

continue;

}

if (i % 9 % 2 == 0) {

distanceCorn++;

} else {

distanceEdge++;

}

}

return distanceEdge * 100 + distanceCorn;

}

void copyCube(int *dist, const int *src) {

for (int i = 0; i < 54; ++i) {

dist[i] = src[i];

}

}

void initSolvedCube(int *cube) {

for (int i = 0; i < 54; ++i) {

cube[i] = i / 9;

}

}

int invMove(int move) {

return move / 3 * 3 + 2 - move % 3;

}

void solve(int *cube) {

int solvedCube[54];

int cubeTmp[54];

int algMoves[8];

int preMoveList[PRE_MOVE_LENGTH];

int algStartIdx;

initSolvedCube(solvedCube);

int curDistance = distance(cube, solvedCube);

int tmpDistance;

while (curDistance != 0) {

copyCube(cubeTmp, cube);

if (curDistance / 100 == 2) { //odd parity

doMove(cubeTmp, 0);

printf("U ");

curDistance = 10000;

}

for (int i = 0; i < PRE_MOVE_LENGTH; ++i) {

preMoveList[i] = rand() % 18;

doMove(cubeTmp, preMoveList[i]);

}

algMoves[0] = rand() % 18;

algMoves[1] = rand() % 18;

algMoves[2] = invMove(algMoves[0]);

algMoves[3] = rand() % 18;

algMoves[4] = algMoves[0];

algMoves[5] = invMove(algMoves[1]);

algMoves[6] = invMove(algMoves[0]);

algMoves[7] = invMove(algMoves[3]);

algStartIdx = rand() % 8;

for (int i = 0; i < 8; ++i) {

doMove(cubeTmp, algMoves[(i + algStartIdx) % 8]);

}

for (int i = PRE_MOVE_LENGTH - 1; i >= 0; --i) {

doMove(cubeTmp, invMove(preMoveList[i]));

}

tmpDistance = distance(cubeTmp, solvedCube);

if (tmpDistance < curDistance + 2 && distance(cubeTmp, cube) != 0) {

if (tmpDistance < curDistance) {

curDistance = tmpDistance;

}

copyCube(cube, cubeTmp);

for (int i = 0; i < PRE_MOVE_LENGTH; ++i) {

printf("%s ", move2str[preMoveList[i]]);

}

for (int i = 0; i < 8; ++i) {

printf("%s ", move2str[algMoves[(i + algStartIdx) % 8]]);

}

for (int i = PRE_MOVE_LENGTH - 1; i >= 0; --i) {

printf("%s ", move2str[invMove(preMoveList[i])]);

}

printf("\n");

}

}

printf("\n");

}

int main(int argc, char const *argv[]) {

int cube[54];

srand((unsigned) time(NULL));

initSolvedCube(cube);

for (int i = 0; i < 1000; ++i) {

int move = rand() % 18;

doMove(cube, move);

}

solve(cube);

return 0;

}

==========分割线==========

其实这是一个很有挑战性的问题。对于不了解魔方的人来说，用计算机求解魔方其实是个和自己学会魔方一样麻烦的问题，前者甚至更加困难一些。

我大致猜了一下题主的情况，应该刚好有一些C语言课安排了求解魔方的大作业，然后大家都一脸懵逼不知道该怎么做。根据经验，其实这些大作业并不是打算让大家和魔方打交道，只是希望通过魔方让同学们熟悉C语言，熟悉各种数据结构、函数调用、逻辑判断等。所以对于这类课的学生，我觉得过多讲解魔方相关知识意义不大，不如直接提供一个有效可行的算法来的实在。

于是我大概琢磨了半个晚上，什么样的算法不需要魔方的各种知识，一看就懂呢。和其他题主一样，第一反应肯定是直接上盲拧公式逐块搞定魔方。然而我发现即便这样，依然需要引入诸如魔方是由角块和棱块构成，角块和棱块有方向有位置有parity的问题，然后碰到各种情况人类是怎么一步步解决的等等。依然绕不开先学会人还原魔方，再把算法写进C语言的过程。

于是我就想到能不能干脆不用引入这些知识，直接随机做盲拧公式，碰到运气好(反正计算机计算能力强，1000个公式下去运气总不会差的)就刚好能还原一块，然后剩下的公式只要尽量不破坏它就好了。或者换句话说，我只需要不停地随机做盲拧公式，然后让魔方尽量接近复原状态，最后总归可以复原的。

这里“接近”在有些情况下其实也是头疼的问题，即如何定义当前状态和还原状态的距离。这个问题我想都没想，直接算计算还有几个颜色不对就好了。因为任何其他的定义又要涉及到魔方的很多知识，能避开当然避开就好了。ps. 其实如果可以换别的距离的定义，程序绝对可以更快。只是在运行速度和代码量、工作量之间，我觉得还是省事要紧，跑得慢点就慢点。

前面提到公式，那下一个问题就是：需要哪几个公式？能不能不手动输入那么多公式。答案是可以的，因为公式是可以临时创造的。比如，所有的角块三循环都可以通过preMove+Commutators搞定。那干脆我直接随机做preMove+Commutators，魔方是不是按照上面的思路就能还原了呢？

这就是我前面提到算法的本质。于是我先动手实现了一下这一简单的思路，仅仅暴力随机生成传统8步的Commutators+5步preMove。发现最后经常会卡在棱块3循环上。这是因为上面的这种结构并无法生成单独棱块的3循环。于是我试了下干脆先不管角块，优先还原棱块，即调整一下棱块和角块的优先级。调整后我发现果然我把棱块的parity忘记了。上述公式理论上并不会改变棱块和角块的parity，当处于奇置换的时候理论上棱块和角块一个都不可能搞得定的。好在如果有parity，棱块在上述算法之下一定会收敛到两棱换。于是加一个判断，如果有两个棱不对，直接转一下U搞定parity。

最后源代码就变成了上面贴出来的样子。它不再需要编码者对魔方有多深入的认识，唯一需要知道的事情就是记住一个公式：随机5步+A B A' C A B' A' C'+前面随机5步的逆序，以及棱块的优先级更高的设定。剩下的交给计算机随机搜索就好了。

最后，如果你确实对计算机求解各种魔方的问题感兴趣，我推荐你阅读：

Computer Puzzling 介绍了计算机求解魔方的一些经典技巧