找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索
查看: 4383|回复: 1
收起左侧

魔方求解算法(基础拧十字法实现C语言描述)

[复制链接]
ID:102014 发表于 2016-1-6 02:35 | 显示全部楼层 |阅读模式
本帖最后由 51黑黑 于 2016-1-6 02:36 编辑

      两年前写了魔方的操作框架,这次把魔方求解也做出来准备用到C写的所以即可以很方便的移植到单片机上做解魔方机器人的核心算法,也可以直接在PC上运行然后通过数据线控制机械机构来操作。
     对魔方的解法也不是很精通所以用的最基本的十字解法来实现的,解魔方步骤一般会有100多步
  1. #include <iostream>
  2. #include <stdlib.h>
  3. //数据结构:
  4. typedef enum colors
  5. {white=1,blue,red,green,orange,yellow}Colors;//6种颜色

  6. typedef struct surface
  7. {
  8. Colors s[4][4];
  9. }Surface;//每个面有3*3个小格,从下标1开始表示,每一面的颜色是固定的

  10. typedef struct cube
  11. {
  12. Surface up,down,front,back,left,right;
  13. }Cube;//魔方的6个面

  14. typedef struct snode
  15. {
  16. char *chbuf;
  17. int times;
  18. struct snode *next;
  19. }SNode;

  20. typedef struct sequence
  21. {
  22. SNode *head;//存储魔方转换序列
  23. int num;//魔方转换的次数
  24. }Sequence;

  25. Sequence CD;

  26. //程序:
  27. void SaveChBuf(char *sur,int i)//将cb序列存入chbuf中
  28. {
  29. char *str;
  30. int len=strlen(sur);
  31. SNode *p,*q;
  32. if(i%4)
  33. {
  34. str=(char *)malloc(sizeof(char)*(len+2));
  35. if(!str)
  36. {
  37. printf("内存不足!\n");
  38. exit(0);
  39. }
  40. strcpy(str,sur);
  41. q=(SNode *)malloc(sizeof(SNode));
  42. if(!q)
  43. {
  44. printf("内存不足!\n");
  45. exit(0);
  46. }
  47. q->chbuf=str;
  48. q->times=i;
  49. q->next=NULL;
  50. if(CD.head==NULL)
  51. {
  52. CD.head=q;
  53. CD.num++;
  54. }
  55. else
  56. {
  57. for(p=CD.head;p->next;p=p->next);
  58. if(!strcmp(p->chbuf,q->chbuf))
  59. {
  60. p->times=(p->times+q->times)%4;
  61. free(q->chbuf);free(q);
  62. if(!(p->times))
  63. {
  64. if(p==CD.head)
  65. {
  66. CD.head=NULL;
  67. free(p->chbuf);free(p);
  68. CD.num--;
  69. }
  70. else
  71. {
  72. for(q=CD.head;q->next!=p;q=q->next);
  73. q->next=NULL;
  74. free(p->chbuf);free(p);
  75. CD.num--;
  76. }
  77. }
  78. }
  79. else
  80. {
  81. p->next=q;
  82. CD.num++;
  83. }
  84. }
  85. }
  86. }

  87. void clockwise(Surface *sur,int i)//将sur面顺时针旋转i次
  88. {
  89. Surface t;
  90. for(;i>0;i--)
  91. {
  92. t=*sur;
  93. sur->s[1][1]=t.s[3][1];
  94. sur->s[1][2]=t.s[2][1];
  95. sur->s[1][3]=t.s[1][1];
  96. sur->s[2][1]=t.s[3][2];
  97. sur->s[2][2]=t.s[2][2];
  98. sur->s[2][3]=t.s[1][2];
  99. sur->s[3][1]=t.s[3][3];
  100. sur->s[3][2]=t.s[2][3];
  101. sur->s[3][3]=t.s[1][3];
  102. }
  103. }

  104. void F(Cube *m,int i)//将魔方的正面顺时针转i次
  105. {
  106. Cube n;
  107. for(;i>0;i--)
  108. {
  109. n=*m;
  110. clockwise(&m->front,1);
  111. m->right.s[1][1]=n.up.s[3][1];
  112. m->right.s[2][1]=n.up.s[3][2];
  113. m->right.s[3][1]=n.up.s[3][3];
  114. m->down.s[1][1]=n.right.s[3][1];
  115. m->down.s[1][2]=n.right.s[2][1];
  116. m->down.s[1][3]=n.right.s[1][1];
  117. m->left.s[1][3]=n.down.s[1][1];
  118. m->left.s[2][3]=n.down.s[1][2];
  119. m->left.s[3][3]=n.down.s[1][3];
  120. m->up.s[3][1]=n.left.s[3][3];
  121. m->up.s[3][2]=n.left.s[2][3];
  122. m->up.s[3][3]=n.left.s[1][3];
  123. }
  124. }

  125. void B(Cube *m,int i)//将魔方的背面顺时针转i次
  126. {
  127. Cube n;
  128. for(;i>0;i--)
  129. {
  130. n=*m;
  131. clockwise(&m->back,1);
  132. m->right.s[1][3]=n.down.s[3][3];
  133. m->right.s[2][3]=n.down.s[3][2];
  134. m->right.s[3][3]=n.down.s[3][1];
  135. m->down.s[3][1]=n.left.s[1][1];
  136. m->down.s[3][2]=n.left.s[2][1];
  137. m->down.s[3][3]=n.left.s[3][1];
  138. m->left.s[1][1]=n.up.s[1][3];
  139. m->left.s[2][1]=n.up.s[1][2];
  140. m->left.s[3][1]=n.up.s[1][1];
  141. m->up.s[1][1]=n.right.s[1][3];
  142. m->up.s[1][2]=n.right.s[2][3];
  143. m->up.s[1][3]=n.right.s[3][3];
  144. }
  145. }

  146. void R(Cube *m,int i)//将魔方的右面顺时针转i次
  147. {
  148. Cube n;
  149. for(;i>0;i--)
  150. {
  151. n=*m;
  152. clockwise(&m->right,1);
  153. m->up.s[1][3]=n.front.s[1][3];
  154. m->up.s[2][3]=n.front.s[2][3];
  155. m->up.s[3][3]=n.front.s[3][3];
  156. m->front.s[1][3]=n.down.s[1][3];
  157. m->front.s[2][3]=n.down.s[2][3];
  158. m->front.s[3][3]=n.down.s[3][3];
  159. m->down.s[1][3]=n.back.s[3][1];
  160. m->down.s[2][3]=n.back.s[2][1];
  161. m->down.s[3][3]=n.back.s[1][1];
  162. m->back.s[3][1]=n.up.s[1][3];
  163. m->back.s[2][1]=n.up.s[2][3];
  164. m->back.s[1][1]=n.up.s[3][3];
  165. }
  166. }

  167. void L(Cube *m,int i)//将魔方的左面顺时针转i次
  168. {
  169. Cube n;
  170. for(;i>0;i--)
  171. {
  172. n=*m;
  173. clockwise(&m->left,1);
  174. m->up.s[1][1]=n.back.s[3][3];
  175. m->up.s[2][1]=n.back.s[2][3];
  176. m->up.s[3][1]=n.back.s[1][3];
  177. m->back.s[1][3]=n.down.s[3][1];
  178. m->back.s[2][3]=n.down.s[2][1];
  179. m->back.s[3][3]=n.down.s[1][1];
  180. m->down.s[1][1]=n.front.s[1][1];
  181. m->down.s[2][1]=n.front.s[2][1];
  182. m->down.s[3][1]=n.front.s[3][1];
  183. m->front.s[1][1]=n.up.s[1][1];
  184. m->front.s[2][1]=n.up.s[2][1];
  185. m->front.s[3][1]=n.up.s[3][1];
  186. }
  187. }

  188. void U(Cube *m,int i)//将魔方的上面顺时针转i次
  189. {
  190. Cube n;
  191. for(;i>0;i--)
  192. {
  193. n=*m;
  194. clockwise(&m->up,1);
  195. m->front.s[1][1]=n.right.s[1][1];
  196. m->front.s[1][2]=n.right.s[1][2];
  197. m->front.s[1][3]=n.right.s[1][3];
  198. m->right.s[1][1]=n.back.s[1][1];
  199. m->right.s[1][2]=n.back.s[1][2];
  200. m->right.s[1][3]=n.back.s[1][3];
  201. m->back.s[1][1]=n.left.s[1][1];
  202. m->back.s[1][2]=n.left.s[1][2];
  203. m->back.s[1][3]=n.left.s[1][3];
  204. m->left.s[1][1]=n.front.s[1][1];
  205. m->left.s[1][2]=n.front.s[1][2];
  206. m->left.s[1][3]=n.front.s[1][3];
  207. }
  208. }

  209. void D(Cube *m,int i)//将魔方的底面顺时针转i次
  210. {
  211. Cube n;
  212. for(;i>0;i--)
  213. {
  214. n=*m;
  215. clockwise(&m->down,1);
  216. m->front.s[3][1]=n.left.s[3][1];
  217. m->front.s[3][2]=n.left.s[3][2];
  218. m->front.s[3][3]=n.left.s[3][3];
  219. m->left.s[3][1]=n.back.s[3][1];
  220. m->left.s[3][2]=n.back.s[3][2];
  221. m->left.s[3][3]=n.back.s[3][3];
  222. m->back.s[3][1]=n.right.s[3][1];
  223. m->back.s[3][2]=n.right.s[3][2];
  224. m->back.s[3][3]=n.right.s[3][3];
  225. m->right.s[3][1]=n.front.s[3][1];
  226. m->right.s[3][2]=n.front.s[3][2];
  227. m->right.s[3][3]=n.front.s[3][3];
  228. }
  229. }

  230. void MR(Cube *m,int i)//将魔方的左面和右面之间的面以右面为基准顺时针旋转1次
  231. {
  232. Cube n;
  233. for(;i>0;i--)
  234. {
  235. n=*m;
  236. m->up.s[1][2]=n.front.s[1][2];
  237. m->up.s[2][2]=n.front.s[2][2];
  238. m->up.s[3][2]=n.front.s[3][2];
  239. m->front.s[1][2]=n.down.s[1][2];
  240. m->front.s[2][2]=n.down.s[2][2];
  241. m->front.s[3][2]=n.down.s[3][2];
  242. m->down.s[1][2]=n.back.s[3][2];
  243. m->down.s[2][2]=n.back.s[2][2];
  244. m->down.s[3][2]=n.back.s[1][2];
  245. m->back.s[3][2]=n.up.s[1][2];
  246. m->back.s[2][2]=n.up.s[2][2];
  247. m->back.s[1][2]=n.up.s[3][2];
  248. }
  249. }

  250. void MF(Cube *m,int i)//将魔方的前面和后面之间的面以前面为基准顺时针旋转i次
  251. {
  252. Cube n;
  253. for(;i>0;i--)
  254. {
  255. n=*m;
  256. m->right.s[1][2]=n.up.s[2][1];
  257. m->right.s[2][2]=n.up.s[2][2];
  258. m->right.s[3][2]=n.up.s[2][3];
  259. m->up.s[2][1]=n.left.s[3][2];
  260. m->up.s[2][2]=n.left.s[2][2];
  261. m->up.s[2][3]=n.left.s[1][2];
  262. m->left.s[1][2]=n.down.s[2][1];
  263. m->left.s[2][2]=n.down.s[2][2];
  264. m->left.s[3][2]=n.down.s[2][3];
  265. m->down.s[2][1]=n.right.s[3][2];
  266. m->down.s[2][2]=n.right.s[2][2];
  267. m->down.s[2][3]=n.right.s[1][2];
  268. }
  269. }

  270. void MU(Cube *m,int i)//将魔方的上面和底面之间的面以上面为基准顺时针旋转i次
  271. {
  272. Cube n;
  273. for(;i>0;i--)
  274. {
  275. n=*m;
  276. m->front.s[2][1]=n.right.s[2][1];
  277. m->front.s[2][2]=n.right.s[2][2];
  278. m->front.s[2][3]=n.right.s[2][3];
  279. m->right.s[2][1]=n.back.s[2][1];
  280. m->right.s[2][2]=n.back.s[2][2];
  281. m->right.s[2][3]=n.back.s[2][3];
  282. m->back.s[2][1]=n.left.s[2][1];
  283. m->back.s[2][2]=n.left.s[2][2];
  284. m->back.s[2][3]=n.left.s[2][3];
  285. m->left.s[2][1]=n.front.s[2][1];
  286. m->left.s[2][2]=n.front.s[2][2];
  287. m->left.s[2][3]=n.front.s[2][3];
  288. }
  289. }

  290. void MoveCube(Cube *m,char *sur,int i)//根据序列cb转换魔方m
  291. {
  292. SaveChBuf(sur,i);//将魔方转换序列存入chbuf中
  293. if(!strcmp(sur,"f"))
  294. F(m,i);//将魔方的正面顺时针旋转i次
  295. if(!strcmp(sur,"b"))
  296. B(m,i);//将魔方的背面顺时针旋转i次
  297. if(!strcmp(sur,"r"))
  298. R(m,i);//将魔方的右面顺时针旋转i次
  299. if(!strcmp(sur,"l"))
  300. L(m,i);//将魔方的左面顺时针旋转i次
  301. if(!strcmp(sur,"u"))
  302. U(m,i);//将魔方的上面顺时针旋转i次
  303. if(!strcmp(sur,"d"))
  304. D(m,i);//将魔方的底面顺时针旋转i次
  305. if(!strcmp(sur,"mr"))
  306. MR(m,i);//将魔方的左面和右面之间的面以右面为基准顺时针旋转i次
  307. if(!strcmp(sur,"mf"))
  308. MF(m,i);//将魔方的前面和后面之间的面以前面为基准顺时针旋转i次
  309. if(!strcmp(sur,"mu"))
  310. MU(m,i);//将魔方的上面和底面之间的面以上面为基准顺时针旋转i次
  311. }

  312. void InputSurface(Surface *sur)
  313. {
  314. int i,j,a;
  315. for(i=1;i<=3;i++)
  316. for(j=1;j<=3;j++)
  317. {
  318. scanf("%d",&a);
  319. sur->s[i][j]=(Colors)a;
  320. }
  321. }

  322. void Input(Cube *magiccube)//存储魔方
  323. {
  324. printf("获取魔方每个面的颜色值:\n");
  325. printf("Blue--------1\tRed---------2\tYellow------3\n");
  326. printf("Green-------4\tWhite-------5\tOrange------6\n\n");
  327. printf("获取顶面(UP)颜色值:\n");
  328. InputSurface(&(magiccube->up));//储存顶面
  329. printf("获取底面(Down)颜色值:\n");
  330. InputSurface(&(magiccube->down));//储存底面
  331. printf("获取前面(Front)颜色值:\n");
  332. InputSurface(&(magiccube->front));//储存前面
  333. printf("获取后面(Back)颜色值:\n");
  334. InputSurface(&(magiccube->back));//储存后面
  335. printf("获取左面(Left)颜色值:\n");
  336. InputSurface(&(magiccube->left));//储存左面
  337. printf("获取右面(Right)颜色值:\n");
  338. InputSurface(&(magiccube->right));//储存右面
  339. }

  340. void DownCross(Cube *magiccube)//将底面拼出一个十字
  341. {
  342. while(!((magiccube->down.s[1][2]==magiccube->down.s[2][2]&&magiccube->front.s[3][2]==magiccube->front.s[2][2])
  343. &&(magiccube->down.s[2][1]==magiccube->down.s[2][2]&&magiccube->left.s[3][2]==magiccube->left.s[2][2])
  344. &&(magiccube->down.s[2][3]==magiccube->down.s[2][2]&&magiccube->right.s[3][2]==magiccube->right.s[2][2])
  345. &&(magiccube->down.s[3][2]==magiccube->down.s[2][2]&&magiccube->back.s[3][2]==magiccube->back.s[2][2])))
  346. {
  347. Surface *sur[4]={&magiccube->front,&magiccube->left,&magiccube->back,&magiccube->right};
  348. char *s[4]={"f","l","b","r"};
  349. int subscript_of_down[4][2]={{1,2},{2,1},{3,2},{2,3}};
  350. int subscript_of_up[4][2]={{3,2},{2,1},{1,2},{2,3}};
  351. char ch[3];
  352. int n;
  353. for(int i=0;i<4;i++)
  354. {
  355. if(magiccube->down.s[subscript_of_down[i][0]][subscript_of_down[i][1]]==magiccube->down.s[2][2]
  356. &&sur[i]->s[3][2]!=sur[i]->s[2][2])
  357. {
  358. strcpy(ch,s[i]);
  359. MoveCube(magiccube,ch,2);
  360. }//底面棱块为底面色位置不对
  361. if(magiccube->up.s[subscript_of_up[i][0]][subscript_of_up[i][1]]==magiccube->down.s[2][2])
  362. {
  363. n=0;
  364. while(sur[(i+n)%4]->s[2][2]!=sur[(i+n)%4]->s[1][2])
  365. {
  366. MoveCube(magiccube,"u",1);
  367. n++;
  368. }
  369. strcpy(ch,s[(i+n)%4]);
  370. MoveCube(magiccube,ch,2);
  371. }//以上是底面棱块在顶面的情况
  372. if(sur[i]->s[1][2]==magiccube->down.s[2][2])//侧面上棱是底面色的情况
  373. {
  374. n=0;
  375. while(sur[(i+n+1)%4]->s[2][2]!=magiccube->up.s[subscript_of_up[(i+n)%4][0]][subscript_of_up[(i+n)%4][1]])
  376. {
  377. MoveCube(magiccube,"u",1);
  378. n++;
  379. }
  380. strcpy(ch,s[(i+n)%4]);
  381. MoveCube(magiccube,ch,3);
  382. strcpy(ch,s[(n+1+i)%4]);
  383. MoveCube(magiccube,ch,1);
  384. strcpy(ch,s[(i+n)%4]);
  385. MoveCube(magiccube,ch,1);
  386. }
  387. if(sur[i]->s[2][1]==magiccube->down.s[2][2])//侧面左棱是底面色的情况
  388. {
  389. strcpy(ch,s[(i+1)%4]);
  390. MoveCube(magiccube,ch,3);
  391. MoveCube(magiccube,"u",1);
  392. MoveCube(magiccube,ch,1);
  393. }
  394. if(sur[i]->s[2][3]==magiccube->down.s[2][2])//侧面右棱是底面色的情况
  395. {
  396. strcpy(ch,s[(i+3)%4]);
  397. MoveCube(magiccube,ch,1);
  398. MoveCube(magiccube,"u",1);
  399. MoveCube(magiccube,ch,3);
  400. }
  401. if(sur[i]->s[3][2]==magiccube->down.s[2][2])//侧面底棱是底面色的情况
  402. {
  403. strcpy(ch,s[i]);
  404. MoveCube(magiccube,ch,1);
  405. strcpy(ch,s[(i+1)%4]);
  406. MoveCube(magiccube,ch,3);
  407. MoveCube(magiccube,"u",1);
  408. MoveCube(magiccube,ch,1);
  409. strcpy(ch,s[i]);
  410. MoveCube(magiccube,ch,3);
  411. }//以上是侧面棱块色是底面色的情况
  412. }
  413. }
  414. }

  415. void DownCornerRestore(Cube *magiccube)//底角还原
  416. {
  417. while(!((magiccube->down.s[1][1]==magiccube->down.s[2][2]&&magiccube->front.s[3][1]==magiccube->front.s[2][2]&&magiccube->left.s[3][3]==magiccube->left.s[2][2])
  418. &&(magiccube->down.s[1][3]==magiccube->down.s[2][2]&&magiccube->front.s[3][3]==magiccube->front.s[2][2]&&magiccube->right.s[3][1]==magiccube->right.s[2][2])
  419. &&(magiccube->down.s[3][1]==magiccube->down.s[2][2]&&magiccube->right.s[3][1]==magiccube->right.s[2][2]&&magiccube->back.s[3][3]==magiccube->back.s[2][2])
  420. &&(magiccube->down.s[3][3]==magiccube->down.s[2][2]&&magiccube->back.s[3][1]==magiccube->back.s[2][2]&&magiccube->right.s[3][3]==magiccube->right.s[2][2])))//直到底角全部归位
  421. {
  422. Surface *sur[4]={&magiccube->front,&magiccube->left,&magiccube->back,&magiccube->right};
  423. char *s[4]={"f","l","b","r"};
  424. int subscript_of_down[4][2]={{1,1},{3,1},{3,3},{1,3}};
  425. int subscript_of_up[4][2]={{3,1},{1,1},{1,3},{3,3}};
  426. char ch[3];
  427. int n;
  428. for(int i=0;i<4;i++)
  429. {
  430. if(magiccube->down.s[subscript_of_down[i][0]][subscript_of_down[i][1]]==magiccube->down.s[2][2]&&
  431. (sur[i]->s[3][1]!=sur[i]->s[2][2]||sur[(i+1)%4]->s[3][3]!=sur[(i+1)%4]->s[2][2]))
  432. {
  433. strcpy(ch,s[i]);
  434. MoveCube(magiccube,ch,1);
  435. MoveCube(magiccube,"u",1);
  436. MoveCube(magiccube,ch,3);
  437. }//底面角块颜色归位但是位置不对
  438. if(magiccube->up.s[subscript_of_up[i][0]][subscript_of_up[i][1]]==magiccube->down.s[2][2])
  439. {
  440. n=0;
  441. while(sur[(i+n)%4]->s[1][1]!=sur[(i+n+1)%4]->s[2][2])
  442. {
  443. MoveCube(magiccube,"u",1);
  444. n++;
  445. }
  446. strcpy(ch,s[(i+n)%4]);
  447. MoveCube(magiccube,ch,1);
  448. MoveCube(magiccube,"u",3);
  449. MoveCube(magiccube,ch,3);
  450. MoveCube(magiccube,"u",2);
  451. }//顶面有底角色块的情况
  452. if(sur[i]->s[1][1]==magiccube->down.s[2][2])//侧面左上角是底面色的情况
  453. {
  454. n=0;
  455. while(sur[(i+n+1)%4]->s[2][2]!=sur[(i+n+1)%4]->s[1][3])
  456. {
  457. MoveCube(magiccube,"u",1);
  458. n++;
  459. }
  460. strcpy(ch,s[(n+i)%4]);
  461. MoveCube(magiccube,ch,1);
  462. MoveCube(magiccube,"u",1);
  463. MoveCube(magiccube,ch,3);
  464. }
  465. if(sur[i]->s[1][3]==magiccube->down.s[2][2])//侧面右上角是底面色的情况
  466. {
  467. n=0;
  468. while(sur[(i+n+3)%4]->s[2][2]!=sur[(i+n+3)%4]->s[1][1])
  469. {
  470. MoveCube(magiccube,"u",1);
  471. n++;
  472. }
  473. strcpy(ch,s[(n+i)%4]);
  474. MoveCube(magiccube,ch,3);
  475. MoveCube(magiccube,"u",3);
  476. MoveCube(magiccube,ch,1);
  477. }
  478. if(sur[i]->s[3][1]==magiccube->down.s[2][2])//侧面左下角是底面色的情况
  479. {
  480. strcpy(ch,s[i]);
  481. MoveCube(magiccube,ch,1);
  482. MoveCube(magiccube,"u",1);
  483. MoveCube(magiccube,ch,3);
  484. }
  485. if(sur[i]->s[3][3]==magiccube->down.s[2][2])//侧面右下角是底面色的情况
  486. {
  487. strcpy(ch,s[i]);
  488. MoveCube(magiccube,ch,3);
  489. MoveCube(magiccube,"u",3);
  490. MoveCube(magiccube,ch,1);
  491. }//侧面有底面色块
  492. }
  493. }
  494. }

  495. void CentreEdgeRestore(Cube *magiccube)//中棱归位
  496. {
  497. while(!((magiccube->front.s[2][1]==magiccube->front.s[2][2]&&magiccube->front.s[2][3]==magiccube->front.s[2][2])
  498. &&(magiccube->left.s[2][1]==magiccube->left.s[2][2]&&magiccube->left.s[2][3]==magiccube->left.s[2][2])
  499. &&(magiccube->back.s[2][1]==magiccube->back.s[2][2]&&magiccube->back.s[2][3]==magiccube->back.s[2][2])
  500. &&(magiccube->right.s[2][1]==magiccube->right.s[2][2]&&magiccube->right.s[2][3]==magiccube->right.s[2][2])))
  501. {
  502. Surface *sur[4]={&magiccube->front,&magiccube->left,&magiccube->back,&magiccube->right};
  503. char *s[4]={"f","l","b","r"};
  504. int subscript_of_up[4][2]={{3,2},{2,1},{1,2},{2,3}};
  505. char ch[3];
  506. int n;
  507. for(int i=0;i<4;i++)
  508. {
  509. if(!(sur[i]->s[2][1]==sur[i]->s[2][2]&&sur[(i+1)%4]->s[2][3]==sur[(i+1)%4]->s[2][2])
  510. &&(sur[i]->s[2][1]!=magiccube->up.s[2][2]&&sur[(i+1)%4]->s[2][3]!=magiccube->up.s[2][2]))
  511. {
  512. strcpy(ch,s[i]);
  513. MoveCube(magiccube,ch,3);
  514. MoveCube(magiccube,"u",3);
  515. MoveCube(magiccube,ch,3);
  516. MoveCube(magiccube,"u",3);
  517. MoveCube(magiccube,ch,3);
  518. MoveCube(magiccube,"u",1);
  519. MoveCube(magiccube,ch,1);
  520. MoveCube(magiccube,"u",1);
  521. MoveCube(magiccube,ch,1);
  522. MoveCube(magiccube,"u",2);
  523. }
  524. if(sur[i]->s[1][2]!=magiccube->up.s[2][2]
  525. &&magiccube->up.s[subscript_of_up[i][0]][subscript_of_up[i][1]]!=magiccube->up.s[2][2])
  526. {
  527. n=0;
  528. while(sur[(i+n)%4]->s[1][2]!=sur[(i+n)%4]->s[2][2])
  529. {
  530. n++;
  531. MoveCube(magiccube,"u",1);
  532. }
  533. if(magiccube->up.s[subscript_of_up[(i+n)%4][0]][subscript_of_up[(i+n)%4][1]]==sur[(i+n+3)%4]->s[2][2])
  534. {
  535. strcpy(ch,s[(i+n)%4]);
  536. MoveCube(magiccube,ch,1);
  537. MoveCube(magiccube,"u",1);
  538. MoveCube(magiccube,ch,1);
  539. MoveCube(magiccube,"u",1);
  540. MoveCube(magiccube,ch,1);
  541. MoveCube(magiccube,"u",3);
  542. MoveCube(magiccube,ch,3);
  543. MoveCube(magiccube,"u",3);
  544. MoveCube(magiccube,ch,3);
  545. }
  546. if(magiccube->up.s[subscript_of_up[(i+n)%4][0]][subscript_of_up[(i+n)%4][1]]==sur[(i+n+1)%4]->s[2][2])
  547. {
  548. strcpy(ch,s[(i+n)%4]);
  549. MoveCube(magiccube,ch,3);
  550. MoveCube(magiccube,"u",3);
  551. MoveCube(magiccube,ch,3);
  552. MoveCube(magiccube,"u",3);
  553. MoveCube(magiccube,ch,3);
  554. MoveCube(magiccube,"u",1);
  555. MoveCube(magiccube,ch,1);
  556. MoveCube(magiccube,"u",1);
  557. MoveCube(magiccube,ch,1);
  558. }
  559. }
  560. }
  561. }
  562. }

  563. void UpCross(Cube *magiccube)//顶面十字
  564. {
  565. while(!(magiccube->up.s[1][2]==magiccube->up.s[2][2]&&magiccube->up.s[2][1]==magiccube->up.s[2][2]
  566. &&magiccube->up.s[2][3]==magiccube->up.s[2][2]&&magiccube->up.s[3][2]==magiccube->up.s[2][2]))
  567. {
  568. Surface *sur[4]={&magiccube->front,&magiccube->left,&magiccube->back,&magiccube->right};
  569. char *s[4]={"f","l","b","r"};
  570. int subscript_of_up[4][2]={{3,2},{2,1},{1,2},{2,3}};
  571. char ch[3];
  572. if(magiccube->up.s[1][2]!=magiccube->up.s[2][2]&&magiccube->up.s[2][1]!=magiccube->up.s[2][2]
  573. &&magiccube->up.s[2][3]!=magiccube->up.s[2][2]&&magiccube->up.s[3][2]!=magiccube->up.s[2][2])
  574. {
  575. MoveCube(magiccube,"f",1);
  576. MoveCube(magiccube,"r",1);
  577. MoveCube(magiccube,"u",1);
  578. MoveCube(magiccube,"r",3);
  579. MoveCube(magiccube,"u",3);
  580. MoveCube(magiccube,"f",3);
  581. }
  582. for(int i=0;i<4;i++)
  583. {
  584. if(magiccube->up.s[subscript_of_up[(i+1)%4][0]][subscript_of_up[(i+1)%4][1]]==magiccube->up.s[2][2]
  585. &&magiccube->up.s[subscript_of_up[(i+2)%4][0]][subscript_of_up[(i+2)%4][1]]==magiccube->up.s[2][2]
  586. &&magiccube->up.s[subscript_of_up[i][0]][subscript_of_up[i][1]]!=magiccube->up.s[2][2]
  587. &&magiccube->up.s[subscript_of_up[(i+3)%4][0]][subscript_of_up[(i+3)%4][1]]!=magiccube->up.s[2][2])
  588. {//形成一个倒"L"
  589. strcpy(ch,s[i]);
  590. MoveCube(magiccube,ch,1);
  591. strcpy(ch,s[(i+3)%4]);
  592. MoveCube(magiccube,ch,1);
  593. MoveCube(magiccube,"u",1);
  594. MoveCube(magiccube,ch,3);
  595. MoveCube(magiccube,"u",3);
  596. strcpy(ch,s[i]);
  597. MoveCube(magiccube,ch,3);
  598. }
  599. if(magiccube->up.s[subscript_of_up[(i+1)%4][0]][subscript_of_up[(i+1)%4][1]]==magiccube->up.s[2][2]
  600. &&magiccube->up.s[subscript_of_up[(i+3)%4][0]][subscript_of_up[(i+3)%4][1]]==magiccube->up.s[2][2]
  601. &&magiccube->up.s[subscript_of_up[i][0]][subscript_of_up[i][1]]!=magiccube->up.s[2][2]
  602. &&magiccube->up.s[subscript_of_up[(i+2)%4][0]][subscript_of_up[(i+2)%4][1]]!=magiccube->up.s[2][2])
  603. {//形成一个横"一"
  604. strcpy(ch,s[i]);
  605. MoveCube(magiccube,ch,1);
  606. strcpy(ch,s[(i+3)%4]);
  607. MoveCube(magiccube,ch,1);
  608. MoveCube(magiccube,"u",1);
  609. MoveCube(magiccube,ch,3);
  610. MoveCube(magiccube,"u",3);
  611. strcpy(ch,s[i]);
  612. MoveCube(magiccube,ch,3);
  613. }
  614. }
  615. }
  616. }

  617. void UpSurfaceCornerRestore(Cube *magiccube)//顶角面位
  618. {
  619. while(!(magiccube->up.s[1][1]==magiccube->up.s[2][2]&&magiccube->up.s[1][3]==magiccube->up.s[2][2]
  620. &&magiccube->up.s[3][1]==magiccube->up.s[2][2]&&magiccube->up.s[3][3]==magiccube->up.s[2][2]))
  621. {
  622. Surface *sur[4]={&magiccube->front,&magiccube->left,&magiccube->back,&magiccube->right};
  623. char *s[4]={"f","l","b","r"};
  624. int subscript_of_up[4][2]={{3,1},{1,1},{1,3},{3,3}};
  625. char ch[3];
  626. int n;
  627. for(int i=0;i<4;i++)
  628. {
  629. if((magiccube->up.s[1][1]!=magiccube->up.s[2][2]&&magiccube->up.s[1][3]!=magiccube->up.s[2][2]
  630. &&magiccube->up.s[3][1]!=magiccube->up.s[2][2]&&magiccube->up.s[3][3]!=magiccube->up.s[2][2])
  631. &&(sur[i]->s[1][1]==magiccube->up.s[2][2]&&sur[i]->s[1][3]==magiccube->up.s[2][2]))
  632. {//十字型(前左右与上同色)
  633. n=0;
  634. while(sur[(i+n)%4]->s[1][2]!=sur[(i+n)%4]->s[2][2])
  635. {
  636. MoveCube(magiccube,"u",1);
  637. n++;
  638. }
  639. strcpy(ch,s[(i+n+3)%4]);
  640. MoveCube(magiccube,ch,3);
  641. MoveCube(magiccube,"u",2);
  642. MoveCube(magiccube,ch,1);
  643. MoveCube(magiccube,"u",1);
  644. MoveCube(magiccube,ch,3);
  645. MoveCube(magiccube,"u",1);
  646. MoveCube(magiccube,ch,1);
  647. }
  648. if(magiccube->up.s[subscript_of_up[(i+3)%4][0]][subscript_of_up[(i+3)%4][1]]==magiccube->up.s[2][2]
  649. &&magiccube->up.s[subscript_of_up[i][0]][subscript_of_up[i][1]]!=magiccube->up.s[2][2]
  650. &&magiccube->up.s[subscript_of_up[(i+1)%4][0]][subscript_of_up[(i+1)%4][1]]!=magiccube->up.s[2][2]
  651. &&magiccube->up.s[subscript_of_up[(i+2)%4][0]][subscript_of_up[(i+2)%4][1]]!=magiccube->up.s[2][2])
  652. {//鱼头朝右下的鱼
  653. if(sur[i]->s[1][1]!=magiccube->up.s[2][2])//前左与上异色
  654. {
  655. strcpy(ch,s[(i+3)%4]);
  656. MoveCube(magiccube,ch,3);
  657. MoveCube(magiccube,"u",2);
  658. MoveCube(magiccube,ch,1);
  659. MoveCube(magiccube,"u",1);
  660. MoveCube(magiccube,ch,3);
  661. MoveCube(magiccube,"u",1);
  662. MoveCube(magiccube,ch,1);
  663. }
  664. else//前左与上同色
  665. {
  666. MoveCube(magiccube,"u",3);
  667. strcpy(ch,s[(i+3)%4]);
  668. MoveCube(magiccube,ch,1);
  669. MoveCube(magiccube,"u",2);
  670. MoveCube(magiccube,ch,3);
  671. MoveCube(magiccube,"u",3);
  672. MoveCube(magiccube,ch,1);
  673. MoveCube(magiccube,"u",3);
  674. MoveCube(magiccube,ch,3);
  675. }
  676. }
  677. if(magiccube->up.s[subscript_of_up[(i+1)%4][0]][subscript_of_up[(i+1)%4][1]]==magiccube->up.s[2][2]
  678. &&magiccube->up.s[subscript_of_up[i][0]][subscript_of_up[i][1]]!=magiccube->up.s[2][2]
  679. &&magiccube->up.s[subscript_of_up[(i+3)%4][0]][subscript_of_up[(i+3)%4][1]]!=magiccube->up.s[2][2]
  680. &&magiccube->up.s[subscript_of_up[(i+2)%4][0]][subscript_of_up[(i+2)%4][1]]==magiccube->up.s[2][2])
  681. {//大炮型
  682. if(sur[i]->s[1][1]==magiccube->up.s[2][2]&&sur[i]->s[1][3]==magiccube->up.s[2][2])
  683. {//前左右与上同色
  684. strcpy(ch,s[(i+1)%4]);
  685. MoveCube(magiccube,ch,3);
  686. MoveCube(magiccube,"u",2);
  687. MoveCube(magiccube,ch,1);
  688. MoveCube(magiccube,"u",1);
  689. MoveCube(magiccube,ch,3);
  690. MoveCube(magiccube,"u",1);
  691. MoveCube(magiccube,ch,1);
  692. }
  693. else
  694. {//前左右与上异色
  695. strcpy(ch,s[(i+2)%4]);
  696. MoveCube(magiccube,ch,3);
  697. MoveCube(magiccube,"u",2);
  698. MoveCube(magiccube,ch,1);
  699. MoveCube(magiccube,"u",1);
  700. MoveCube(magiccube,ch,3);
  701. MoveCube(magiccube,"u",1);
  702. MoveCube(magiccube,ch,1);
  703. }
  704. }
  705. if(magiccube->up.s[subscript_of_up[(i+3)%4][0]][subscript_of_up[(i+3)%4][1]]==magiccube->up.s[2][2]
  706. &&magiccube->up.s[subscript_of_up[i][0]][subscript_of_up[i][1]]!=magiccube->up.s[2][2]
  707. &&magiccube->up.s[subscript_of_up[(i+1)%4][0]][subscript_of_up[(i+1)%4][1]]==magiccube->up.s[2][2]
  708. &&magiccube->up.s[subscript_of_up[(i+2)%4][0]][subscript_of_up[(i+2)%4][1]]!=magiccube->up.s[2][2])
  709. {//双凌型
  710. MoveCube(magiccube,"u",3);
  711. strcpy(ch,s[(i+3)%4]);
  712. MoveCube(magiccube,ch,3);
  713. MoveCube(magiccube,"u",2);
  714. MoveCube(magiccube,ch,1);
  715. MoveCube(magiccube,"u",1);
  716. MoveCube(magiccube,ch,3);
  717. MoveCube(magiccube,"u",1);
  718. MoveCube(magiccube,ch,1);
  719. }
  720. }
  721. }
  722. }

  723. void UpCornerRestore(Cube *magiccube)//顶角还原
  724. {
  725. while(magiccube->front.s[1][1]!=magiccube->front.s[2][2])
  726. MoveCube(magiccube,"u",1);
  727. while(!((magiccube->front.s[1][1]==magiccube->front.s[2][2]&&magiccube->front.s[1][3]==magiccube->front.s[2][2])
  728. &&(magiccube->left.s[1][1]==magiccube->left.s[2][2]&&magiccube->left.s[1][3]==magiccube->left.s[2][2])
  729. &&(magiccube->back.s[1][1]==magiccube->back.s[2][2]&&magiccube->back.s[1][3]==magiccube->back.s[2][2])
  730. &&(magiccube->right.s[1][1]==magiccube->right.s[2][2]&&magiccube->right.s[1][3]==magiccube->right.s[2][2])))
  731. {
  732. Surface *sur[4]={&magiccube->front,&magiccube->left,&magiccube->back,&magiccube->right};
  733. char *s[4]={"f","l","b","r"};
  734. int n;
  735. char ch[3];
  736. int i;
  737. for(i=0;i<4;i++)
  738. {
  739. n=0;
  740. if(sur[i]->s[1][1]==sur[i]->s[1][3])
  741. {
  742. while(sur[(i+n)%4]->s[1][1]!=sur[(i+n)%4]->s[2][2])
  743. {
  744. MoveCube(magiccube,"u",1);
  745. n++;
  746. }
  747. break;
  748. }
  749. }
  750. strcpy(ch,s[(i+n+3)%4]);
  751. MoveCube(magiccube,ch,1);
  752. strcpy(ch,s[(i+n+2)%4]);
  753. MoveCube(magiccube,ch,3);
  754. strcpy(ch,s[(i+n+3)%4]);
  755. MoveCube(magiccube,ch,1);
  756. strcpy(ch,s[(i+n)%4]);
  757. MoveCube(magiccube,ch,2);
  758. strcpy(ch,s[(i+n+3)%4]);
  759. MoveCube(magiccube,ch,3);
  760. strcpy(ch,s[(i+n+2)%4]);
  761. MoveCube(magiccube,ch,1);
  762. strcpy(ch,s[(i+n+3)%4]);
  763. MoveCube(magiccube,ch,1);
  764. strcpy(ch,s[(i+n)%4]);
  765. MoveCube(magiccube,ch,2);
  766. strcpy(ch,s[(i+n+3)%4]);
  767. MoveCube(magiccube,ch,2);
  768. while(magiccube->front.s[1][1]!=magiccube->front.s[2][2])
  769. MoveCube(magiccube,"u",1);
  770. }
  771. }

  772. void UpEdgeRestore(Cube *magiccube)//顶棱还原
  773. {
  774. while(magiccube->front.s[1][1]!=magiccube->front.s[2][2])
  775. MoveCube(magiccube,"u",1);
  776. while(!(magiccube->front.s[1][2]==magiccube->front.s[2][2]&&magiccube->left.s[1][2]==magiccube->left.s[2][2]
  777. &&magiccube->back.s[1][2]==magiccube->back.s[2][2]&&magiccube->right.s[1][2]==magiccube->right.s[2][2]))
  778. {
  779. Surface *sur[4]={&magiccube->front,&magiccube->left,&magiccube->back,&magiccube->right};
  780. char *s[4]={"f","l","b","r"};
  781. int n;
  782. char ch[3];
  783. int i;
  784. for(i=0;i<4;i++)
  785. {
  786. n=0;
  787. if(sur[i]->s[1][1]==sur[i]->s[1][2]&&sur[i]->s[1][2]==sur[i]->s[1][3])
  788. {
  789. while(sur[(i+n)%4]->s[1][1]!=sur[(i+n)%4]->s[2][2])
  790. {
  791. MoveCube(magiccube,"u",1);
  792. n++;
  793. }
  794. break;
  795. }
  796. }
  797. strcpy(ch,s[(i+n+1)%4]);
  798. MoveCube(magiccube,ch,1);
  799. MoveCube(magiccube,"u",3);
  800. MoveCube(magiccube,ch,1);
  801. MoveCube(magiccube,"u",1);
  802. MoveCube(magiccube,ch,1);
  803. MoveCube(magiccube,"u",1);
  804. MoveCube(magiccube,ch,1);
  805. MoveCube(magiccube,"u",3);
  806. MoveCube(magiccube,ch,3);
  807. MoveCube(magiccube,"u",3);
  808. MoveCube(magiccube,ch,2);
  809. while(magiccube->front.s[1][1]!=magiccube->front.s[2][2])
  810. MoveCube(magiccube,"u",1);
  811. }
  812. }

  813. void printsurface(Surface sur)//输出某一面的颜色
  814. {
  815. int i,j;
  816. for(i=1;i<=3;i++)
  817. {
  818. for(j=1;j<=3;j++)
  819. printf("%d ",(int)sur.s[i][j]);
  820. printf("\n");
  821. }
  822. }

  823. void PrintMagicCube(Cube m)//输出整个魔方的当前颜色值状态
  824. {
  825. printf("\nUp面颜色值如下:\n");      
  826. printsurface(m.up);
  827. printf("\nDown面颜色值如下:\n");
  828. printsurface(m.down);
  829. printf("\nFront面颜色值如下:\n");
  830. printsurface(m.front);
  831. printf("\nBack面颜色值如下:\n");
  832. printsurface(m.back);
  833. printf("\nLeft面颜色值如下:\n");
  834. printsurface(m.left);
  835. printf("\nRight面颜色值如下:\n");
  836. printsurface(m.right);
  837. }

  838. void PrintBuf()
  839. {
  840. SNode *p;
  841. int i;
  842. printf("\n还原魔方所用的操作步骤如下:\n");
  843. for(p=CD.head,i=1;p;p=p->next,i++)
  844. {
  845. printf("%s%d\t",p->chbuf,p->times);
  846. if(i==5)
  847. {
  848. putchar('\n');
  849. printf("------------------------------------\n");
  850. i=0;
  851. }
  852. }
  853. printf("\n\n本次魔方还原一共进行了%d步!\n",CD.num);
  854. }

  855. void InitializationMagiccube(Cube *m)//初始化魔方
  856. {

  857. m->up.s[1][1]=(Colors)2;m->up.s[1][2]=(Colors)4;m->up.s[1][3]=(Colors)4;
  858. m->up.s[2][1]=(Colors)3;m->up.s[2][2]=(Colors)5;m->up.s[2][3]=(Colors)6;
  859. m->up.s[3][1]=(Colors)2;m->up.s[3][2]=(Colors)1;m->up.s[3][3]=(Colors)5;

  860. m->down.s[1][1]=(Colors)3;m->down.s[1][2]=(Colors)3;m->down.s[1][3]=(Colors)6;
  861. m->down.s[2][1]=(Colors)5;m->down.s[2][2]=(Colors)3;m->down.s[2][3]=(Colors)1;
  862. m->down.s[3][1]=(Colors)4;m->down.s[3][2]=(Colors)6;m->down.s[3][3]=(Colors)6;

  863. m->front.s[1][1]=(Colors)5;m->front.s[1][2]=(Colors)5;m->front.s[1][3]=(Colors)1;
  864. m->front.s[2][1]=(Colors)2;m->front.s[2][2]=(Colors)4;m->front.s[2][3]=(Colors)6;
  865. m->front.s[3][1]=(Colors)2;m->front.s[3][2]=(Colors)2;m->front.s[3][3]=(Colors)3;

  866. m->back.s[1][1]=(Colors)5;m->back.s[1][2]=(Colors)2;m->back.s[1][3]=(Colors)3;
  867. m->back.s[2][1]=(Colors)6;m->back.s[2][2]=(Colors)1;m->back.s[2][3]=(Colors)4;
  868. m->back.s[3][1]=(Colors)3;m->back.s[3][2]=(Colors)3;m->back.s[3][3]=(Colors)6;
  869. m->left.s[1][1]=(Colors)1;m->left.s[1][2]=(Colors)4;m->left.s[1][3]=(Colors)1;
  870. m->left.s[2][1]=(Colors)5;m->left.s[2][2]=(Colors)6;m->left.s[2][3]=(Colors)1;
  871. m->left.s[3][1]=(Colors)5;m->left.s[3][2]=(Colors)2;m->left.s[3][3]=(Colors)4;

  872. m->right.s[1][1]=(Colors)6;m->right.s[1][2]=(Colors)5;m->right.s[1][3]=(Colors)2;
  873. m->right.s[2][1]=(Colors)1;m->right.s[2][2]=(Colors)2;m->right.s[2][3]=(Colors)4;
  874. m->right.s[3][1]=(Colors)1;m->right.s[3][2]=(Colors)3;m->right.s[3][3]=(Colors)4;
  875. }
  876. void Exit()
  877. {
  878. SNode *p,*q;
  879. for(p=CD.head;p;p=q)
  880. {
  881. q=p->next;
  882. free(p->chbuf);free(p);//释放所有内存空间
  883. }
  884. printf("按任意键继续....");
  885. getchar();
  886. }
  887. int main(int argc, char *argv[])
  888. {
  889. Cube magiccube;
  890. int i=0;
  891. CD.num=0;
  892. CD.head=NULL;
  893. Input(&magiccube);//输入魔方初始状态
  894. //InitializationMagiccube(&magiccube);//初始化魔方  调试用
  895. printf("\n获取到的魔方状态为:");
  896. PrintMagicCube(magiccube);//输出初始化后的魔方
  897. DownCross(&magiccube);//底部十字
  898. DownCornerRestore(&magiccube);//底角还原
  899. CentreEdgeRestore(&magiccube);//中棱还原
  900. UpCross(&magiccube);//顶面十字
  901. UpSurfaceCornerRestore(&magiccube);//顶角面位
  902. UpCornerRestore(&magiccube);//顶角还原
  903. UpEdgeRestore(&magiccube);//顶棱还原
  904. printf("\n还原转换后的魔方状态为:");
  905. PrintMagicCube(magiccube);//输出变换后的魔方
  906. PrintBuf();//输出变更序列
  907. Exit();
  908. system("PAUSE");
  909. return 0;
  910. }
复制代码



回复

使用道具 举报

ID:281514 发表于 2018-2-1 17:29 | 显示全部楼层
最终能还原吗
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

手机版|小黑屋|51黑电子论坛 |51黑电子论坛6群 QQ 管理员QQ:125739409;技术交流QQ群281945664

Powered by 单片机教程网

快速回复 返回顶部 返回列表