魔方吧·中文魔方俱乐部

标题: 最少步的角块色向判断法 [打印本页]

作者: earthengine 时间: 2008-8-24 17:59:57 标题: 最少步的角块色向判断法

要判断N阶魔方角块方向，盲拧编码法为我们提供了基本依据。但是，盲拧编码法需要确定3个面的坐标，确定高中低级面。这样，同一个魔方在不同的参照系下将会有不同的编码结果，也就有不同的解法。当然，其中会有一些简单些，有些复杂些。对于最少步的判断，这一区别是关键性的。所以，本文旨在提出一种不同的方法，确保能使结果与参照系无关。 首先，我们要明白的一点是，魔方的每个角块其实可以处于6种不同的方向状态，而不是3种。但是，在每一个特定的位置，确实只能处于其中的3种。这是因为8个角块可以被分成2组，组内的块必须通过偶数次转动90度才能达到，而要移到别的组则需要奇数次。这两个组各有4块，通过各面的对角线分别构成一个正四面体。如果我们每次都转动180度，那么两个组的块就不能互换。如果我们观察特定的角块，可以把它所在的块组称为偶组，另一个组叫奇组。 其次，让我们看看偶组和奇组的方向状态有何不同。如果你对盲拧编码很熟练，不难观察到： 如果一个块的原始位置在偶组上，那么它的编码在各种高中低面选择下要么都为0，要么都不是0。下面简称这种块为偶块。 如果一个块的原始位置在奇组上，那么它的编码在不同参照选择下可以有各种不同的值，且总有一些参照选择能让它为0，另一些则不。这种块就是奇块。 对于偶块，我们在对角轴向外的方向观察，则它要么顺时针转120度（用+表示），要么逆时针转120度（用-表示），要么就已经在正确位置。这里我们采用类似盲拧的方法，把相对面的颜色看作相同。 对于奇块，我用xyz进行编码。如果X向（LR）选为高级面它的编码为0，它的状态为x，余类推。 好了，编码完成之后，我们要组织复原策略了。对于偶块，它们的状态不会变化，可不加以考虑。而容易证明奇块的数目总会是偶数且总是两个组各占一半，因此我们把奇块成对进行考虑。且总是一个在奇组，一个在偶组。 这两个成对的角块要么编码相同，要么不同。要是相同，它们可以消去。因此，我们只需要考虑它们不同的情形，这可以用实例说明。 首先考虑３阶公式F D' L2 B D' B R2 D B2 L2 D F' U（希望谁能帮我做个JAVA），这个公式把2个角块（ULF和URF）调换，把一个角块（DLF）翻转。它们都在同一个面上。因为单单调换一对角块是做不到的，这个公式会把一对边块（UF和DF）调换以达成平衡。按照我的编码，它们的状态分别表示为 ULF：x URF：y DLF：+ 这里的DLF是跟URF同组的。这个公式说明xy的组合相当于y所在组上一个-。 现在考虑另一个公式R U L' U' L U' L' R U' L U R2 F2，它和以上公式的结果非常相像，但它翻转了DRF而非DLF。这时候它们的状态是 ULF：x 
URF：y 
DRF：- xy组合的结果现在相当于x所在组上的一个+。看到没有？只要把结果所在的组改变，结果就从-变成了+。 下面可以列出一个表了，大家可以自行验证一下。 节点１　节点２　节点１所在组　节点２所在组 x            y          +                      - y            z          +                      - 
z            y          +                      - 以上很有规律：按照xyz的循环顺序，结果组对应的节点状态排在前面就是正的，在后面就是负的。现在我们可以推算角块复原的方法了。 按照以上方案组织一个证明应该不难。基本上就是应用魔方归纳法：证明如果任何一个状态按照以上方案算出的正号数量等于负号数量，那么从它进行一次基本动作之后也一样。 

[ 本帖最后由 earthengine 于 2008-8-24 20:29 编辑 ]

作者: kexin_xiao 时间: 2008-8-24 18:05:15

学习一下，要仔细看！

作者: Atato 时间: 2008-8-24 18:21:06

楼主说的真玄乎..N阶角块...你就说判断2阶就可以了..
LZ把表示换了一种..
<A href="http://bbs.mf8-china.com/viewthread.php?tid=3196&highlight=%C9%AB%CF%F2">http://bbs.mf8-china.com/viewthread.php?tid=3196&highlight=%C9%AB%CF%F2</A>
色向的问题啊...邱志红老师已经说的很清楚了...上面的连接就是帖子.
LZ实在是应该多搜索搜索帖子..
 

[ 本帖最后由 Atato 于 2008-8-24 19:04 编辑 ]

作者: 魔鱼儿 时间: 2008-8-24 18:36:25

好东西要学习,不过得仔细看哦,要不看不明白的,呵呵

作者: junior_sky 时间: 2008-8-24 19:35:43

实在不懂

作者: 乌木 时间: 2008-8-24 19:37:31

1楼要的java图：
 
<APPLET height=250 codebase='http://zmb.fnfnet.com/puzzletoy/java/' archive=AnimCube.jar width=250 code=AnimCube.class>
<PARAM NAME="colorscheme" VALUE="wbgyor">
<PARAM NAME="bgcolor" VALUE="FFFFFF">
<PARAM NAME="butbgcolor" VALUE="99AACC">
<PARAM NAME="movetext" VALUE="2">
<PARAM NAME="metric" VALUE="2">
<PARAM NAME="fonttype" VALUE="0">
<PARAM NAME="move" VALUE="F D' L2 B D' B R2 D B2 L2 D F' U">
<PARAM NAME="facelets" VALUE="rrrrrrrrrooooooooowwwwwwwwwyyyyyyyyybbbbbbbbbggggggggg">
</APPLET> <APPLET height=250 codebase='http://zmb.fnfnet.com/puzzletoy/java/' archive=AnimCube.jar width=250 code=AnimCube.class>
<PARAM NAME="colorscheme" VALUE="wbgyor">
<PARAM NAME="bgcolor" VALUE="FFFFFF">
<PARAM NAME="butbgcolor" VALUE="99AACC">
<PARAM NAME="movetext" VALUE="2">
<PARAM NAME="metric" VALUE="2">
<PARAM NAME="fonttype" VALUE="0">
<PARAM NAME="move" VALUE="R U L' U' L U' L' R U' L U R2 F2">
<PARAM NAME="facelets" VALUE="rrrrrrrrrooooooooowwwwwwwwwyyyyyyyyybbbbbbbbbggggggggg">
</APPLET>

[ 本帖最后由乌木于 2008-8-24 19:50 编辑 ]

作者: earthengine 时间: 2008-8-24 20:11:09

原帖由 Atato 于 2008-8-24 18:21 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=222274&ptid=13002" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
楼主说的真玄乎..N阶角块...你就说判断2阶就可以了..
LZ把表示换了一种..
http://bbs.mf8-china.com/viewthread.php?tid=3196&highlight=%C9%AB%CF%F2
色向的问题啊...邱志红老师已经说的很清楚了...上面的连接就是帖 ...

呵呵，那个我看过。不过那是用于理论论证的，且可用于角块边块面块等，不过较繁琐。我这个只能用在角块，虽然没有盲拧编码简明，但是有它的优点。几种方案应该是殊途同归的，各有千秋吧。

作者: earthengine 时间: 2008-8-24 20:11:48

原帖由 乌木 于 2008-8-24 19:37 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=222358&ptid=13002" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
1楼要的java图：

太感谢了！

作者: Atato 时间: 2008-8-24 20:36:42

呵呵我倒是同意搂主 7#的说法

作者: 知Shmily足 时间: 2008-8-24 20:37:47

看不见JAVA的图啊

作者: 乌木 时间: 2008-8-24 21:40:09

那么，换个版本看得到吗？唉，何时论坛自己的java助手恢复就好了。
 
<APPLET codeBase=http://bbs.mf100.org height=250 archive=rubikplayer.jar width=250

code=ch.randelshofer.rubik.RubikPlayerApp.class>
<PARAM NAME="scrgpt" VALUE="F D' L2 B D' B R2 D B2 L2 D F' U">
<PARAM NAME="scrgptlanguage" VALUE="SupersetENG">
<PARAM NAME="colortable" VALUE="0xf8f8f8,0x00732f,0xff4400,0xffd200,0x003373,0x8c000f,0x858585">
<param name="scriptProgress" value="0">
<param name="beta" value="29">
</APPLET> <APPLET codeBase=http://bbs.mf100.org height=250 archive=rubikplayer.jar width=250

code=ch.randelshofer.rubik.RubikPlayerApp.class>
<PARAM NAME="scrgpt" VALUE="R U L' U' L U' L' R U' L U R2 F2">
<PARAM NAME="scrgptlanguage" VALUE="SupersetENG">
<PARAM NAME="colortable" VALUE="0xf8f8f8,0x00732f,0xff4400,0xffd200,0x003373,0x8c000f,0x858585">
<param name="scriptProgress" value="0">
<param name="beta" value="29">
</APPLET>

[ 本帖最后由乌木于 2008-8-24 21:42 编辑 ]

作者: kexin_xiao 时间: 2008-8-24 22:04:18

两个JAVA帖子都可以看见，谢谢乌木老师！

作者: 乌木 时间: 2008-8-25 17:45:22

1楼的一时还看不懂，再说，先问问这个问题。你说“魔方的每个角块其实可以处于6种不同的方向状态，……”这句话里的“6种”是否应为“24种”？而且确切说来是否应为：头一个角块有24种不同的方向状态，第二个21种，第三个18种，第四个15种，第五个12种，第六个9种，第七个6种，第八个就只有1种－－3种色向之一，但不能改色向，即不能任选了。具体哪一色向，取决于前7个角块当时的色向如何。
 
如果不考虑这样依次（经转层来）布排角块，仅仅任选一个角块考查它的可能有的方向状态，那就应有24种。对吗？

[ 本帖最后由乌木于 2008-8-25 17:48 编辑 ]

作者: earthengine 时间: 2008-8-25 17:59:08

原帖由 乌木 于 2008-8-25 17:45 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=223203&ptid=13002" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
1楼的一时还看不懂，再说，先问问这个问题。你说“魔方的每个角块其实可以处于6种不同的方向状态，……”这句话里的“6种”是否应为“24种”？而且确切说来是否应为：头一个角块有24种不同的方向状态，第二个21种，第 ...

你的24态是正确的，但是应用上就比较繁琐了。24态的变换不是那么简单的。但是，本质上我们都知道，每个角块确定位置之后，只能有3中可能的方向。盲拧编码就是每个角块都只有3个方向的，但是这是牺牲了对称性换来的，造成的结果是在高级面的转动和其它面有不同的变化规律，且计算出来的复原方案取决于高级面的选择。我这套方案是两者的折衷，态数比24态少，而方向比盲拧多，计算比盲拧复杂。好处则是恢复了对称性。

作者: smok 时间: 2008-8-25 18:09:20

三个角块独立逆转，对称谁了？

作者: 乌木 时间: 2008-8-25 20:49:57

1楼说“如果一个块的原始位置在偶组上，那么它的编码在各种高中低面选择下要么都为0，要么都不是0。”  这句话的前提是否为“限于180°转”？一个角块在偶组（就是自己所属的那个四面体的四个顶点）上移位时限于用180°转动的话，才有这种现象吧？ 
 
1楼说“奇块的数目总会是偶数且总是两个组各占一半”  是否指8个角块总的说来“奇块的数目总会是偶数”？这一组有几个角块是原属那一组的，那一组必定也有几个角块是原属这个组的。对吗？凡是错组的角块，就叫奇块，对吗？此外，应该也可以有两组没有交换角块的情况的，对吧？

[ 本帖最后由乌木于 2008-8-25 21:15 编辑 ]

作者: earthengine 时间: 2008-8-25 21:18:18

1。如果在偶组上，那么它必然要通过偶数次旋转90度才能复原。由于容许转动90度，所以它的方向仍然可以旋转120度。要是这样的话，它的盲拧编码在调整高中低级面的选择不能把它的编码从非0变为0或者相反，但是选定之后它的方向仍然可以通过操作魔方发生变化。但如果操作限于旋转180度，则它的盲拧编码将不会再有任何变化。举例：如果一个节点在原位置转动了120度，那么任何盲拧编码都不可能把它编码为0；但是如果容许转动90度，则一个LU之类的操作可以将它移动后移回来，最终复原。这在仅允许180度旋转时是做不到的。 

2。你的理解是正确的。注意奇偶块和奇偶组不一样。块的奇偶是它本身的属性，表示它本身与复原位置的关系。奇偶组则是块之间的关系：以任意一个块为基准，偶组是它所在的组，奇组是相对的另一个组。

[ 本帖最后由 earthengine 于 2008-8-25 21:25 编辑 ]

作者: 乌木 时间: 2008-8-25 22:19:12

一个角块的奇偶性随着转层进程，或有变，或不变－－90°转，且涉及它时，它的奇偶性就切换一下。180°转且涉及它时，或者转层动作不涉及它时，它的奇偶性不变。对吗？

作者: earthengine 时间: 2008-8-25 22:51:01

原帖由 乌木 于 2008-8-25 22:19 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=223605&ptid=13002" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
一个角块的奇偶性随着转层进程，或有变，或不变－－90°转，且涉及它时，它的奇偶性就切换一下。180°转且涉及它时，或者转层动作不涉及它时，它的奇偶性不变。对吗？

你的理解完全正确！

作者: 乌木 时间: 2008-8-26 10:16:15

1楼的还没懂，还得继续看。好像文章有的地方你是让参照物围着考查对象转的，对吗？这对我来说很搅脑子。
 
此外，你说（关于）“判断N阶魔方角块方向”要“提出一种不同的方法，确保能使结果与参照系无关”，对吗？一个物体的方向怎么会与参照系无关呢？ 

[ 本帖最后由乌木于 2008-8-26 10:33 编辑 ]

作者: 乌木 时间: 2008-8-26 10:55:04 标题: 回复 14# 的帖子

你在看一个指定的角块时，说它有6种方向，那么排除了哪18种方向，或留下哪6种方向呢？你不妨具体说说，我弄明白后可试试画个图上来。
－－－－－－－－－－－－－－－－－－－
或者贴个下图（略去别的块，只留下8个角块，设第一个为复原态）供你取舍，你不妨标记一下，哪6种取，哪18种舍：
 
                 一个角块的24种方向.GIF

[ 本帖最后由乌木于 2008-8-26 11:32 编辑 ]

附件: 一个角块的24种方向.GIF (2008-8-26 11:32:49, 9.51 KB) / 下载次数 101
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjQxMDB8MWU5YTk5MDl8MTcxNDc5NzQ4NHwwfDA%3D

作者: earthengine 时间: 2008-8-26 11:22:40

原帖由 乌木 于 2008-8-26 10:55 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=223836&ptid=13002" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
你在看一个指定的角块时，说它有6种方向，那么排除了哪18种方向，或留下哪6种方向呢？你不妨具体说说，我弄明白后可试试画个图上来。

我不是排除了若干方向，而是把相似的方向合而为一。方法很简单：把魔方两个对面的颜色看成是一样的，于是在偶组上它总有一个方向能满足各面均与中心块同色。但是在奇组上，它只能有一个面和中心块同色。概括说，我们仅限180度转动的操作看成是保持方向不变的，于是只要确定了组，组内的位置可以忽略，于是4种可能的朝向合而为一，最终就得到24/4=6种状态。

你这里24种不同的状态的编码如下： 第一行 0 - + z x y 第二行 0 - + z x y 第三行 z x y 0 - + 第四行 z x y 0 - +

（之前三四行正负号写错，谢谢乌木指正） 其实判断很简单：如果红色在上面或下面，就是z，黄色在前面或者后面，就是x，蓝色在左面或者右面，就是y。如果同时有两个以上符合，那就是0。一个都不符合，看怎么样能转成0。如果把x面（黄色）转到了y向（左面或者右面），那就是+，否则就是-。 

[ 本帖最后由 earthengine 于 2008-8-26 17:36 编辑 ]

作者: earthengine 时间: 2008-8-26 11:37:49

原帖由 乌木 于 2008-8-26 10:16 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=223818&ptid=13002" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
1楼的还没懂，还得继续看。好像文章有的地方你是让参照物围着考查对象转的，对吗？这对我来说很搅脑子。
 
此外，你说（关于）“判断N阶魔方角块方向”要“提出一种不同的方法，确保能使结果与参照系无关”， ...

我说的“无关”含义是：无论如何选择参照系，对错位角块的判断都一致。不会出现象盲拧编码那样，在某些参照系下为0（不需要动）的块在别的参照系下可能不是0。此外，还有一个含义是无论如何选择参照系，任何90度旋转都会改变状态，而不是象盲拧编码那样，在高级面的转动是不改变角块方向状态的。

作者: 乌木 时间: 2008-8-26 11:53:09

如何理解22楼你这6类角块的编码法我还要继续看1楼的文字。现在有个感觉：有一种盲拧法是色向问题和位置问题分开处理的，而你这是同时解决，是吗？而且，从你1楼的话来看，此文是用于最少步复原法的？（真是的话，我是蛮怕这种高级复原法啊。）
 
还有，22楼中你说的两个“－”是要求逆转120°，另两个“－”却是要顺转。“＋”也有类似问题，是否有笔误？

[ 本帖最后由乌木于 2008-8-26 16:32 编辑 ]

作者: earthengine 时间: 2008-8-26 17:42:09

原帖由 乌木 于 2008-8-26 11:53 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=223899&ptid=13002" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
如何理解22楼你这6类角块的编码法我还要继续看1楼的文字。现在有个感觉：有一种盲拧法是色向问题和位置问题分开处理的，而你这是同时解决，是吗？而且，从你1楼的话来看，此文是用于最少步复原法的？（真是的话，我是 ...

这不算同时解决，但是解决后可以单靠180度转还原。此法当然不限于最少步，对于其它很多问题的研究也很有帮助。我正在准备把你那个2阶三轮换的帖子中所有例子用此法编码，说明其中的异同。 此外，主楼我漏了一点没有提及，就是对于不在同一组的块，只要编码相同，它们就可以消去，哪怕它们都没有移动到别组。这样，两个+如果不在同一组是可以消掉的，两个-也一样。但是同一组的块只能消掉符号相反的，也就是说把一个组解决后另一个组必须正号和负号相等，才算平衡状态。 

[ 本帖最后由 earthengine 于 2008-8-26 19:07 编辑 ]

作者: earthengine 时间: 2008-8-26 19:05:47

乌木先生可以参考http://bbs.mf8-china.com/viewthr ... &extra=page%3D1
我当初是因为研究这个方法的改进，而找到这里来的。其中一个大难点就是状态2到3的转换中，角块如何辨认位置正确。

作者: 乌木 时间: 2008-8-26 20:41:35 标题: 回复 26# 的帖子

谢谢，那帖子我看过，吓退了。说实话，这类话题以及你的话题，我目前还啃不动。期待着你们能有些副产品惠及普通玩法就好了。或者直接给我们一些应用之类的结果也好，要问原理者再看有关文章。偷懒了，只想坐享现成。

[ 本帖最后由乌木于 2008-8-26 22:20 编辑 ]

作者: ggglgq 时间: 2008-9-13 15:29:01

              呵呵，看了半天，earthengine 好象是指“最少步骤的角块色向判断法”呀！           这些天也不见 earthengine 在 ☆ 最少步还原问题 ☆ 更新完善您的理论，   很是想念呀！呵呵！

作者: earthengine 时间: 2008-9-13 21:30:44

原帖由 ggglgq 于 2008-9-13 15:29 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=238080&ptid=13002" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
              呵呵，看了半天，earthengine 好象是指“最少步骤的角块色向判断法”呀！          这些天也不见 earthengine 在 ☆ 最 ...

你说得对。用于最小步的色向判断必定要跟盲拧有所区别，因为盲拧编码重点在于方便记忆，所以必须简明。而用在最小步研究的时候，这个编码方法应该不要依赖于什么高中低级面的选定才好，因为不同的选定方式将有不同的编码，带来的结果是有不同的复原方法。这样其中有些步骤可能少些有些多些。

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)