herbert-kociemba求解魔方的两相算法的python/c实现
kociemba的Python项目详细描述
科辛巴
这个Python包包含了Herbert Kociemba求解魔方的两阶段算法的两个等价实现(在C和Python中)。 原始java实现可以在这里找到:http://kociemba.org/download.htm。
这些端口非常简单(不说是哑的),而且很可能是可以优化的。但是它们已经在我们的魔方解题机(FAC System Solver和Meccano Rubik's Shrine)中得到了广泛的测试,所以请相信算法是有效的
nb请注意,两阶段算法不能保证生成的解是尽可能短的。相反,它会在很短的时间内给你一个“足够好”的解决方案例如,您可以在这个库的顶部实现额外的检查,以便在多维数据集已经解决的情况下不产生任何移动。
安装
此软件包在PYPI上发布,可使用以下软件包安装:
$ pip install kociemba
它在Python2.7和3.3+下进行了测试
基于Unix的系统
您可能需要事先安装libffi系统库。例如,在基于debian的发行版(例如raspbian)上,您将运行sudo apt-get install libffi-dev
。
窗口
库应该可以在windows上运行,但是目前还没有自动测试:travis cidoesn't have windows support。
正常的pip install kociemba
(或者python 3.3+的pip3 install kociemba
)应该可以工作,但是您需要首先从微软安装免费的构建工具。检查以下链接:
- 对于python 2.7:https://www.microsoft.com/en-us/download/details.aspx?id=44266
- 对于python 3:https://www.visualstudio.com/downloads/#build-tools-for-visual-studio-2017
用法
该包只公开一个函数solve()
,该函数接受多维数据集定义字符串并以标准表示法返回解决方案字符串(见下文)。
可选的第二个参数允许对特定模式进行求解。
>>>importkociemba>>>kociemba.solve('DRLUUBFBRBLURRLRUBLRDDFDLFUFUFFDBRDUBRUFLLFDDBFLUBLRBD')u"D2 R' D' F2 B D R2 D2 R' F2 D' F2 U' B2 L2 U2 D R2 U">>>kociemba.solve('FLBUULFFLFDURRDBUBUUDDFFBRDDBLRDRFLLRLRULFUDRRBDBBBUFL','BBURUDBFUFFFRRFUUFLULUFUDLRRDBBDBDBLUDDFLLRRBRLLLBRDDF')u"R' D2 R' U2 R F2 D B2 U' R F' U R2 D L2 D' B2 R2 B2 U' B2"
独立工具
使用pip安装时,kociemba
还将注册同名的命令行工具。所以你也可以这样使用它:
$ kociemba <cubestring>
立方体字符串表示法
立方体的面板位置的名称(字母表示上、左、前、右、后和下):
|************|
|*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*|
|************|
立方体定义字符串“UBL…”表示在位置U1中我们有U颜色,在位置U2中我们有
b-色,在u3位置我们有l-色等。根据顺序,U1
,U2
,U3
,U4
,U5
,U6
,U7
,U8
,U9
,R1
,R2
,
R3
, R4
, R5
, R6
, R7
, R8
, R9
, F1
, F2
, F3
, F4
, F5
, F6
, F7
, F8
, F9
, D1
, D2
, D3
, D4
, D5
, D6
, D7
, D8
, D9
, L1
, L2
, L3
, L4
,
L5
,L6
,L7
,L8
,L9
,B1
,B2
,B3
,B4
,B5
,B6
,B7
,B8
,B9
例如,一个已求解立方体的定义是UUUUUUUUURRRRRRRRRFFFFFFFFFDDDDDDDDDLLLLLLLLLBBBBBBBBB
解决方案字符串由空格分隔的部分组成,每个部分表示单个移动:
- 一个字母本身意味着顺时针旋转90度
- 后跟撇号的字母表示将该面逆时针旋转90度。
- 后面带有数字2的字母表示将该面旋转180度
例如R U R’ U R U2 R’ U
C版
c源位于ckociemba
文件夹中。在这个目录中运行make
将编译一个独立的二进制文件。它接受多维数据集表示作为命令行参数,并将解决方案写入标准输出。当然,您可以在项目中直接使用ckociemba
源代码
性能
如果可能,kociemba
将在引擎盖下使用c实现。如果出了问题(C版本无法导入),它将自动返回到纯Python实现。不过,速度会慢得多
测试
进行测试,cl打开存储库并运行:
$ python setup.py test
多亏了
- @JarheadJoe对Windows支持的贡献