最少步的角块色向判断法

earthengine

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

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

earthengine

原帖由 <i>Atato</i> 于 2008-8-24 18:21 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&amp;pid=222274&amp;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&amp;highlight=%C9%AB%CF%F2
色向的问题啊...邱志红老师已经说的很清楚了...上面的连接就是帖 ...

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

earthengine

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









   

<br>太感谢了！<br>

earthengine

原帖由 <i>乌木</i> 于 2008-8-25 17:45 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&amp;pid=223203&amp;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种，第 ...

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

earthengine

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

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

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

earthengine

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

<br>你的理解完全正确！<br>

earthengine

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

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

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

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

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

earthengine

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

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

earthengine

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

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

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

earthengine

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