RubiksCube-TwophaseSolver（魔方两阶段求解器）

概述

本项目用Python实现了完全开发的两阶段算法来求解魔方。虽然Python比C++或Java等语言慢得多，但这个实现足够高效，可以在几秒钟内在树莓派3等低性能硬件上平均用不到20步解开随机魔方。

如果你的目标只是解魔方并探索其模式，Cube Explorer可能是更好的选择。但是，如果你想深入了解两阶段算法的复杂性，或者正在进行一个项目来构建一个能达到近乎最优解的魔方解题机器人，那么这就是合适的资源。

使用方法

该包可在PyPI上获得，可以通过以下命令安装：

$ pip install RubikTwoPhas

安装完成后，你可以在代码中导入twophase.solver模块：

>>> import twophase.solver as sv

一些表格需要创建，但只在首次运行时需要。这些表格占用约80 MB的磁盘空间，根据你的硬件情况，生成可能需要半小时或更长时间。然而，正是通过这些计算成本高昂的表格，算法才能高效运行，通常能找到近乎最优的解法。

魔方由其定义字符串来表示。一个已解开的魔方的字符串为'UUUUUUUUURRRRRRRRRFFFFFFFFFDDDDDDDDDLLLLLLLLLBBBBBBBBB'。

>>> cubestring = 'DUUBULDBFRBFRRULLLBRDFFFBLURDBFDFDRFRULBLUFDURRBLBDUDL'

具体格式请参考 https://github.com/hkociemba/RubiksCube-TwophaseSolver/blob/master/enums.py。

>>> sv.solve(cubestring,19,2)

这将解决由定义字符串描述的魔方，期望最大步数为19步，超时时间为2秒。如果达到超时时间，将返回到目前为止计算出的最短解法，即使它超过了期望的最大步数。

'L3 U1 B1 R2 F3 L1 F3 U2 L1 U3 B3 U2 B1 L2 F1 U2 R2 L2 B2 (19f)'

这里，U、R、F、D、L和B分别表示魔方的上、右、前、下、左和后面。1、2和3表示相应面顺时针旋转90°、180°和270°。

如果你想为每个解法分配固定时间t，并只接收在该时间t内找到的最短操作序列，可以使用以下命令：

>>> sv.solve(cubestring,0,t)

你可以用类似以下的方式在你的机器上测试算法的性能：

>>> import twophase.performance as pf
>>> pf.test(100,0.3)

这个例子生成100个随机魔方，每个用0.3秒求解，并显示解法长度的统计信息。

你还可以选择将魔方解到非标准状态，而是解到由goalstring表示的某个喜欢的模式。

>>> sv.solveto(cubestring,goalstring,20,0.1)

这将给予0.1秒的时间来找到不超过20步的解法。

另一个功能是启动一个本地服务器，监听你选择的端口。它接受魔方定义字符串并返回解法。

>>> import twophase.server as srv
>>> srv.start(8080, 20, 2)

或者，在后台启动服务器：

>>> import twophase.start_server as ss
>>> from threading import Thread
>>> bg = Thread(target=ss.start, args=(8080, 20, 2))
>>> bg.start()

成功启动后，会显示类似以下的消息：

Server socket created Server now listening...

表示服务器正常运行。在这个例子中，服务器在8080端口监听，期望最大步数为20步，超时时间为2秒。

你可以通过多种方式访问服务器，该服务器也可能在远程机器上运行：

http://localhost:8080/DUUBULDBFRBFRRULLLBRDFFFBLURDBFDFDRFRULBLUFDURRBLBDUDL 通过网络浏览器访问同一台机器上8080端口的服务器。

http://myserver.com:8081/DUUBULDBFRBFRRULLLBRDFFFBLURDBFDFDRFRULBLUFDURRBLBDUDL 通过网络浏览器访问远程机器myserver.com上8081端口的服务器。

echo DUUBULDBFRBFRRULLLBRDFFFBLURDBFDFDRFRULBLUFDURRBLBDUDL | nc localhost 8080 使用netcat (nc)访问同一台机器上8080端口的服务器。您还可以使用一个小型GUI程序与服务器通信，该程序允许您交互式地输入魔方定义字符串：

>>> import twophase.client_gui

请注意，以下模块是实验性的，需要安装OpenCV包，可以通过以下命令完成： $ pip install opencv-python 此外，您还需要numpy包，可以通过以下命令安装： $ pip install numpy

使用以下命令加载模块：

>>> import twophase.computer_vision

确保网络服务器正在运行，并且有摄像头连接到客户端。您可以使用摄像头输入魔方的颜色。有几个参数会影响小面检测的质量。如果您使用的是带有树莓派摄像头模块的树莓派，而不是USB摄像头，请确保先执行"sudo modprobe bcm2835-v4l2"。

您可以在这里找到有关如何设置参数的更多信息：计算机视觉与魔方

性能指标

我们在Windows 10机器上使用AMD Ryzen 7 3700X 3.59 GHz处理器，在各种情况下测试了1000个随机魔方的求解。区分标准CPython解释器和带有即时编译器的PyPy (pypy3)，后者的速度提高了约10倍。

test(1000, t)生成1000个随机魔方，每个魔方的计算时间为t秒。还给出了求解步骤长度的分布。

标准CPython

test(1000,30): {14: 0, 15: 2, 16: 12, 17: 74, 18: 279, 19: 534, 20: 99, 21: 0}，平均18.63步 test(1000,10): {14: 0, 15: 1, 16: 8, 17: 51, 18: 242, 19: 532, 20: 166, 21: 0}，平均18.79步 test(1000,1): {14: 0, 15: 2, 16: 4, 17: 28, 18: 127, 19: 401, 20: 405, 21: 33, 22: 0}，平均19.27步 test(1000,0.1): {15: 0, 16: 2, 17: 6, 18: 46, 19: 186, 20: 451, 21: 293, 22: 16, 23: 0}，平均20.02步

带有即时编译器的PyPy (pypy3)

test(1000,10): {14: 0, 15: 1, 16: 11, 17: 100, 18: 423, 19: 433, 20: 32, 21: 0}，平均18.37步 test(1000,1): {14: 0, 15: 1, 16: 10, 17: 49, 18: 259, 19: 535, 20: 145, 21: 1, 22: 0}，平均18.76步 test(1000,0.1): {15: 0, 16: 4, 17: 23, 18: 100, 19: 429, 20: 401, 21: 43, 22: 0}，平均19.33步 test(1000,0.01): {16: 0, 17: 1, 18: 25, 19: 95, 20: 349, 21: 461, 22: 69, 23: 0}，平均20.45步

要达到平均不到19步，在CPython的情况下需要10秒的计算时间，在PyPy的情况下需要1秒。要多0.5步，CPython需要1秒的计算时间，PyPy需要0.1秒。