A naive Rubik's cube implementation

marveloustau

虽然在Demonstration Project上面已经有Roman Maeder老师写的魔方演示，我还是用Dynamic写了一个naive的版本，因为这样有利于和以后的魔方求解器接驳

1. Matrix = Map[
   
2.    Function[x,
   
3.     Map[x + # &, {{-1.5, -1.5}, {-0.5, -1.5}, {-0.5, -0.5}, {-1.5, \
   
4. -0.5}}]], {{{0, 0}, {0, 1}, {0, 2}}, {{1, 0}, {1, 1}, {1, 2}}, {{2,
   
5.       0}, {2, 1}, {2, 2}}}, {-2}];
   
6. (*这是一个面9个小方格的坐标，由16个不同的顶点组成。这16个顶点的坐标是由-1.5,-0.5,0.5以及1.5四个数字Outer出来的*)
   
7. 
   
8. 
   
9. FinalMatrix =
   
10.   Flatten[Table[
    
11.     Map[Insert[#, i, j] &,
    
12.      Matrix, {-2}], {i, {-1.5, 1.5}}, {j, {1, 2, 3}}], 1];
    
13. (*将其变换为六个三维的面*)
    
14. FinalGraphics =
    
15.   Flatten@Riffle[{Yellow, Green, Orange, White, Blue, Red},
    
16.     Map[Polygon, FinalMatrix, {-3}]];
    
17. (*插入图形Primitive以及颜色*)
    
18. 
    
19. Twist[a_, b_] :=
    
20. Do[FinalGraphics[[Flatten[
    
21.       Position[FinalGraphics,
    
22.        Polygon[{___,
    
23.          Insert[{_, _}, x_ /; If[a > 0, x > a, x < a], b], ___}]]]]] =
    
24.     Map[#.RotationMatrix[Pi/90, Insert[{0, 0}, a, b]] &,
    
25.     FinalGraphics[[Flatten[
    
26.        Position[FinalGraphics,
    
27.         Polygon[{___,
    
28.           Insert[{_, _}, x_ /; If[a > 0, x > a, x < a],
    
29.            b], ___}]]]]], {-2}], {i, 45}]
    
30. (*旋转应用了模式匹配。一次旋转需要改变21个小方块的坐标，这21个小方块的特点是它们一定会有至少两个在相同的平面上。用Position找到\
    
31. 它们在FinalGraphics中的原始位置，然后乘以用RotationMatrix生成的旋转矩阵*)
    
32. QuickTwist[a_, b_] :=
    
33. Do[FinalGraphics[[Flatten[
    
34.       Position[FinalGraphics,
    
35.        Polygon[{___,
    
36.          Insert[{_, _}, x_ /; If[a > 0, x > a, x < a], b], ___}]]]]] =
    
37.     Map[#.RotationMatrix[Pi/2, Insert[{0, 0}, a, b]] &,
    
38.     FinalGraphics[[Flatten[
    
39.        Position[FinalGraphics,
    
40.         Polygon[{___,
    
41.           Insert[{_, _}, x_ /; If[a > 0, x > a, x < a],
    
42.            b], ___}]]]]], {-2}], {1}]
    
43. (*考虑魔方由原始位置打乱顺序不需要详细显示旋转过程，所以在此采取\[OpenCurlyDoubleQuote]一步到位\
    
44. \[CloseCurlyDoubleQuote]的旋转*)
    
45. 
    
46. Scramble[n_] :=
    
47. Do[QuickTwist[RandomChoice[{-1, 1}], RandomChoice[{1, 2, 3}]], {n}]
    
48. (*随机地旋转，制定打乱顺序的操作次数*)
    
49. 
    
50. Dynamic[Graphics3D[FinalGraphics, PlotRange -> 2.1]]

复制代码

使用方法：运行之后输入Twist[a,b]，其中a可为1和-1两个值，b为1，2，3三个值。b代表xyz三个方向，而a代表三个方向上的正负，加起来刚好6个，神奇吧。

不过由于它需要不断进行模式匹配，所以不可避免地会在计算下一个转动位置时浪费大量时间，这样导致转动很不流畅。
我正在寻求解决方案，如果大家有意见请千万不要犹豫。
Danke!

--补充了Scramble，打乱顺序。使用方法为Scramble[n]，其中n为打乱顺序操作的步数。

--------------------------------------------
如果将RotationMatrix换成RotationTransform速度会大大提高。我想是因为RotationTransform生成的是编译过的TransformFunction，而这要比对两个向量求内积要快很多。改进后的Twist为

1. Twist2[a_, b_] :=(*RotateTransform version (much faster) *)
   
2. Do[FinalGraphics[[
   
3.     Flatten[Position[FinalGraphics,
   
4.       Polygon[{___,
   
5.         Insert[{_, _}, x_ /; If[a > 0, x > a, x < a], b], ___}]]]]] =
   
6.    Map[RotationTransform[Pi/270, Insert[{0, 0}, a, b]],
   
7.     FinalGraphics[[
   
8.      Flatten[Position[FinalGraphics,
   
9.        Polygon[{___,
   
10.          Insert[{_, _}, x_ /; If[a > 0, x > a, x < a],
    
11.           b], ___}]]]]], {-3}], {i, 135}]

复制代码

[ 本帖最后由 marveloustau 于 2009-1-18 13:42 编辑 ]

FreddyMusic

Appears cool ! 版主加技术分鼓励。

界面搞出来了，有关Solver，Cubic 是不是把情况全部罗列出来然后搜索？

一点小建议用 Manipulate 比 Dynamic 强，好处在于你自己能操控。

你先自己尝试尝试，有问题我来帮忙。

marveloustau

不可能列出全部状态，魔方状态空间太庞大。Mathworld上面说魔方全部状态共有43252003274489856000种。能将魔方状态空间缩减的数学方法已经找到了，但是需要用一个好一点的搜索算法。

Roman Maeder那个版本用的就是Manipulate，我也没打算让用户自己操控。这个东西只是solver的一部分，主要是为了显示这个算法的工作原理。此外Roman Maeder用的是Cuboid，我用的是Polygon，要比他的看着流畅很多。

Anyway, 我先把我开始的想法都实现一下再看如何改进吧。

FreddyMusic

Manipulate 的意思是不仅用户可以操控，作者自己也可以操控。
这样方便很多，避免了作者自己重复打命令。
在Dynamic的基础上只要设置几个操控的动参数即可。

marveloustau

那要不你改吧，我先写solver了

'~'

marveloustau

Solver写完了，涉及到两个很麻烦的算法证明。明天把Solver和上面的那坨代码整理到一起。

marveloustau

问题主要处在白色的那面，别的倒还看得清。好像如果禁用一个光照的参数就可以解决这问题，但是我忘了是哪个了。:(

FreddyMusic

tau,

I spend some time try to move your model into Manipulate.
However, I find that is not easy without deep study your project.

Using manipulate need to design and define some key dynamic parameters that you wish to control later.
You should address and concern about it in the beginning. If we re-inforce and put into manipulate, it's not good.
E.g. Each time you want a cubic to rotate, you send axis and plane on setter, then use a button for start.

[ 本帖最后由 FreddyMusic 于 2009-2-8 13:40 编辑 ]

marveloustau

我原来想过能不能使用EventHandler来实现类似Manipulate的控制效果，但是很不方便