魔方机器人的研究与实现
曾鋆1，孙悦红2**
作者简介：曾鋆，(1988- )，男，无，服务器端程序开发。
通信联系人：孙悦红，（1963- ），女，副教授，人工智能. E-mail: 13651089370@139.com
（1. 北京工商大学艺术与传媒学院，北京 100048；
5 2. 北京工商大学计算机与信息学院人工智能实验室，北京 100048）
摘要：作为人工智能技术学科的一项分支，魔方机器人越来越受到关注。本文设计了一个基
于51 单片机和PC 机的三阶魔方还原机器人，充分利用了PC 机及单片机各自的优势，并且
通过改进了传统的CFOP 算法、使用了经过改进的数据结构，不仅节省了系统资源，还提高
了还原速度。并且通过重新设计驱动和采用独特的图片识别算法，加快了图片识别并和核心
10 控制模块交互的速度。本文的创新点主要在于设计了更加适合的算法和数据结构，有效地减
小了程序的空间复杂度和时间复杂度。
关键词：人工智能；魔方还原；CFOP 算法
 0 引言
30 作为人工智能技术学科的一项分支，魔方机器人越来越受到关注，本课题旨在设计一个
魔方还原机器人，能够快速还原被任意打乱的三阶魔方，设计中综合运用了模式识别，机器
人动力学，单片机控制技术等学科知识，并且魔方还原算法实现上做了一些改进。
1 系统原理及结构
一个被任意打乱的魔方,只要按照一定的规律转动各个面,都能被还原,.因此,可以在计算
35 机上设计一套算法程序,由计算机指导执行部件将一个被打乱的魔方还原.本设计将还原步骤
的算法主程序放在PC 端运行,通过PC 与单片机之间的通信,将算法运行结果,也就是魔方各
面的旋转方向发送至单片机,再由单片机控制三路步进电机,实现对魔方的旋转.
系统框架图1 所示
 40 图1 系统框架图
魔方机器人的结构图如图2 所示
图2 魔方机器人的转动手臂三视图
45
2 硬件设计
由于魔方每一面的转动角度通常是一定的,均为90 度的整数倍,因此采用步进电机来控
制魔方的转动,考虑到步进电机的特点,采用单片机发出逻辑指令来控制步进电机的转动方向
及转动角度.并且由PC 机上算法程序的运行结果来生成每一步的转动方式指令.
50 2.1 单片机的硬件设计
单片机选用目前最成熟的80C51.用RS232 串口将其与PC 机相连,以接收PC 机发来的
数据.由于RS232 通信的典型工作电平为3~12V 与-3~-12V,而C8051 输出为TTL 电平,所以
在通信时,必须进行电平转换,以便与RS232 标准的电平相匹配[1]。选用MAX3232 来达到这
一电平转换目的。如图3 所示
 图3 MAX232 转换芯片电路原理图
2.2 步进电机的选取
选用86BYG350FC 型号的步进电机，这是一个三相步时电机，相电流为3.35A,相电阻
60 为9Ω，相电感41mH，步距角0.6/1.2o。[2]
3 算法实现及改进
3.1 算法
魔方的算法上采用了CFOP 算法，这种算法对于任意魔方情况都可以适用[3]。
此方法使用了119 个公式，分为4 个步骤复原魔方，分别是，Cross->First 2 layers(简
65 称f2l)->Orientation of last layer(简称oll)->Permutation of last layer(简称pll)，也就是：
底层十字->同时对好前两层->调整好最后一层的朝向->调整好最后一层的顺序（排
列）。
该算法的基本原理是只转动底面和侧面，不会影响顶层结构。
3.2 数据结构
70 将魔方的六个面按下图顺序分别编号为0、1、2、3、4、5 面。如图4 所示, 然后将魔
方的每个面按图5 的顺序进行编号.
 0 1 2
3 4 5
6 7 8
1 4 4
2 0 2
5 0 2
图4 图5 图6
75 设定0 表示0 面中心点的颜色，1 表示1 面中心点的颜色，以此类推，用0-5 这六个数
来表示魔方的六种颜色。再根据上图中的坐标系，就可以用一个9 位数来表示一个面的颜色
分布情况。例如：144202502，根据第5 个位置的数0 可以判断出这是描述0 面的情况，然
后根据每一位的的数可以还原出这样的一个面的情况，如图6 所示：
这样，就可以用一个装有6 个九位数的数组来表示一个魔方。在程序中，可以设定一个
80 字符串数组cube[6]，这个数组里装了6 个9 位数，用来表示魔方的六个面的情况。
这种以6 个9 位数的字符串作为表示魔方的数据结构，有一定的便利性：
1） 如果给每个面每个点设置一个变量，后存成结构体或联合体的状况，或者是用多维
数组的形式来表示的情况，都比较占内存，而且程序上也不够简便，运行效率也非常低
[4]；
85 2） C#中的字符串处理函数很丰富，不用自己开发测试子函数，在开发上更为简便。
3.3 程序设计
本算法一共分为六个步骤。
1） 使0 面的1357 位置的颜色等于4 位置的颜色；
2） 使0 面的0268 位置的颜色等于4 位置的颜色；
90 3） 将1234 层的345678 六个位置全部变成和4 位置颜色相同的颜色；
4） 将5 面变成全部由颜色5 构成；
5） 将5 面的4 个角的颜色和1234 面对齐。
6） 将1234 面的7 位置颜色对换，完成魔方还原工作
软件流程图7 所示
95 3.4 驱动摄像头的方法
调用系统文件夹system32 下avicap.dll 文件提供的capCreateCaptureWindow 函数创建一
个视频窗口form，然后利用System.Windows.forms 类的Clipboard.GetDataObject()方法对这
个windows form 进行截图，然后存储为BMP 图像，文件名分别命名为0.bmp-5.bmp。调用
图像分析程序对这6 个图进行分析。分析完成后删除这6 个图片[5]。
100 3.5 图像分析
由于该系统的摄像头截取出来的图像大小为320*240,摄像头和魔方之间的距离为
30cm 。根据试验发现(120,80) ， (120,120) ， (120,160),(160,80), (160,120) ，
(160,160),(200,80),(200,120),(200,160)这九个点为魔方六个面的中心点，这9 个点的rgb 值能
反映出该面的颜色。运用windows framework 提供的bitmap 类的getpixel 方法取得图像中的
105 一个点的信息，这个点的R、G、B 这三个属性就是该点的RGB 值。蒋这些取到的RGB 值
的每个数不足三位的在左边补上0 然后组成一个9 位数。然后在左边再加上面和具体的点，
依照规定的数据结构那样，存入一个数组，设这个数组为yuanshi[54]。
取出每一位，去掉左边两位，然后存入另外一个数组,设定这个数组为paixu[54]，进行
 排序,如果想比较的两个数相等那么就按照下标决定小下标的数在前。取第piaxu[8]，
paixu[17]，paixu[26]，paixu[35]，paixu[110 44]，paixu[53]位的数，假设其分别为abcdef。然后
在数组yuanshi 中，选择第一位相同的数字然后组成一个数组sides[9]，然后再依次去掉第二
位为0123445678 的数，和abcdefg 比较，如果大于a 则认定该格子颜色为0，依次类推，然
后得出一个9 位数。
再依次循环其他5 个首字母相同的面，得出另外五个9 位数。得到这6 个数后，存入
115 cube[6]数组。
图7 软件设计流程图
 4 结论
120 本文论述了一个简易的三阶魔方相器人的设计方法，充分发挥了PC 机和单片机各自的
优势，利用PC 机作为主要计算单元，可在机械手臂转动魔方的同时，在PC 机的屏幕上用
模拟图方式显示出转动方法，在人的视觉感观上有一定的吸引效果，经多次实验，能用效快
的速度还原一个被任意打乱的三阶魔方。