Skip to content
/ cube Public

c++ simulator and solver of Rubik's cube (2×2×2 to 10×10×10) 正魔方2-10阶的模拟和还原

Notifications You must be signed in to change notification settings

harryhare/cube

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

33 Commits
 
 
 
 
 
 
 
 

Repository files navigation

程序说明

环境

windows,vs2008

语言

c++

图形

opengl,glut

运行时,请在环境中增加,否则可能会影响操作流畅性

PATH=$(SolutionDir)glut\

其他

程序第一次运行时,会在当前目录下生成一些数据文件,由于有大量计算所以启动可能比较慢 以后的运行,会直接加载这些文件,所以会快很多


功能说明

键盘控制说明:

数字键2-9——选择对应阶的魔方
s —— 自动还原魔方(2阶为最优解,3阶可能非最优解,不过一般少于30个face move,4阶及以上为模拟人工还原)
r —— 重置魔方
R —— 随机魔方 (该随机一定可解)
t —— 透明魔方

鼠标控制说明

拖拽魔方——魔方对应层旋转
拖拽黑色背景——魔方整体旋转

性能

  • 移动数 x-魔方阶数,y-还原步数,曲线为二次拟合 上面是的数据是对3到31,100,850 阶的魔方随机打乱并还原50次,然后分别取旋转次数的平均值。

  • 时间 x-魔方阶数,y-还原时间ms,曲线为二次拟合 上面是的数据是对3到31,100,850 阶的魔方随机打乱并还原50次,然后分别取旋转花费时间的平均值。

  • 900阶的时候解的长度过大,程序报std::bad_alloc错误,估计是堆空间用完了。

  • 具体数据

cube order repeat time total (s) time average(ms) move average
2 1000 0.007 0.007
3 100 37.449 374.49
4 50 16.695 333.9
5 50 13.516 270.32
6 50 15.617 312.34
7 50 21.543 430.86
8 50 20.381 407.62
9 50 14.685 293.7
10 50 16.008 320.16
11 50 35.858 717.16
12 50 20.17 403.4
13 50 19.681 393.62
14 50 27.282 545.64
15 50 31.797 635.94
16 50 31.525 630.5
17 50 27.643 552.86
18 50 28.863 577.26
19 50 29.651 593.02
20 50 27.923 558.46
21 50 38.591 771.82
22 50 35.416 708.32
23 50 34.338 686.76
24 50 40.879 817.58
25 50 35.642 712.84
26 50 43.829 876.58
27 50 42.42 848.4
28 50 41.459 829.18
29 50 49.304 986.08
30 50 51.157 1023.14
31 50 49.363 987.26
11 10 4.132 413.2
21 10 5.578 557.8
31 10 10.176 1017.6
41 10 16.372 1637.2
51 10 25.354 2535.4
61 10 34.48 3448
71 10 42.424 4242.4
81 10 58.974 5897.4
91 10 70.468 7046.8
101 10 84.932 8493.2
51 5 10.954 2190.8
101 5 43.207 8641.4
151 5 92.297 18459.4
201 5 163.375 32675
251 5 253.432 50686.4
301 5 365.872 73174.4
351 5 593.14 118628
401 5 765.271 153054
451 5 896.056 179211
501 5 1101.89 220377
551 5 1456.39 291278
601 5 1519.2 303840
651 5 1723.11 344621
701 5 1884.79 376958
751 5 2387.13 477426
801 5 2834.6 566920
851 5 2882.66 576532

自动还原算法

2阶还原

由于2阶魔方的状态数较少,所以把每种状态的深度,和当前的旋转动作,做成表,直接查找即可

3阶还原

two phase算法,具体参考
http://kociemba.org/cube.htm

n阶还原

模拟人工还原

随机打乱

根据魔方的状态数公式 打乱算法理论上可以到达所有可解状态

About

c++ simulator and solver of Rubik's cube (2×2×2 to 10×10×10) 正魔方2-10阶的模拟和还原

Topics

Resources

Stars

Watchers

Forks

Packages

No packages published