[原创]基于N阶定律的三阶最远状态计算分析

pengw

要研究魔方最远状态，如果选择的方法是与魔方状态数较劲，是相当不理智的，不幸的是，这样的事一直在发生，且执迷不悟，事实上，改变一下思路，处理方法则要简单很多。魔方从来就是，为头脑清淅，逻辑严密，善于归纳总结的玩家准备的，然而，仍然随处可见到，概念定义似是而非，逻辑倒错，似乎可以解决所有问题又无法证明的描述，事实上，魔方就像一面镜，从中可以对人的一些能力给预一个判断或评估。

探讨最远状态,如同面对一个没有地图说明的公路网,要想知道了解任何二地的最短距离,其难度可想而知,然而,如果我们知道任意二地的经纬度,则可以合理推断出最少须要行驶段多少距离就可以完成行程,基于这个思路,偿试分析一下三阶的最远状态.

基本思路

分析1步转式能构造的状态数，再分析2步转式构造的状态数，如果能找到一个长度为n的转式，正好能构构造出所有魔方状态,那么最小的n 值就是最远状态,.在这里,我们假定所有长度为n的转式正好与魔方状态数一一对应,由于魔方状态数可以准确计算出来，因而可以倒推出一个长度为n的转式，显然，由于存在不改变魔方状态的无效转式( 仅当 n是偶数，为什么?谁能解答?)和生成同一状态的等效转式，因而，这个算出来的长度为 n的转式生成的状态数总是小于魔方状态数的一半，这个n的意义是，说明魔方的的最远状态的长度至少大于n。

这个思路在过滤无效转式与等效转式方面还有极大的优化可能,优化的结果是更逼近真实值。满足魔方一半的状态被构造出来的最小n值最少有2个，分别代表偶数步最远状态和奇数步最远状态，其中最大者就是魔方最远状态，由于奇数步转式不含无效转式，预计，奇数步最远状态比偶数步最远状态更短，因此，魔方最远状态可能由偶数步转式生成。

定义

最远状态:从复原魔方到任意状态的最短步数构成一个集合,这个集合中步数最长者对应的状态称为最远状态,在这里,90度转算一步，本文中，结合上下文相关性，最远状态也指生成该状态的最短转式的长度

转式：一个有限长度的转动序列a1,a2,...an,1=<an<=12(在三阶上执行90度/步，共有12种情况）

长度为1的转式有：L1=12^1种
长度为2的转式有：L2=12^2种
长度为n的转式有：Ln=12^n种

分析

1。基于N阶定律，魔方的状态数可以准确计算出来
2。N阶定律预言，奇数步状态数与偶数步状态数各占一半，互无交集
3。分析可知，如果n是奇数，Ln可以转达出Lk的所有状态，其中K是奇数，1=<K<=n
4。分析可知，如果n是偶数，Ln可以转达出Lk的所有状态，其中K是偶数，2=<K<=n

计算

基于以上分析，可以列出以下算式:

三阶纯色:

三阶纯色魔方状态数T=8!/2*12!/2*3^7*2^11*2，T/2=3^7*8!*12!*2^9=21626001637244928000

Ln=12^n=T/2=3^7*8!*12!*2^9=21626001637244928000

n=17.91

Ln构造的所有纯色魔方状态中，显然存在重复状态，也就是说，步长约为17的所有转式并不能构造出一半的魔方状态，但由此计算可以准确地给出一个极限值，即，最远状态至少大于17步(90度/步)。在此基础上，对于奇数步最远状态的合理推断应该是不小于19，偶数步最远状态不小于18

三阶全色:

三阶全色魔方状态数T=8!/2*12!/2*3^7*2^11*4^5*2*2，T/2=3^7*8!*12!*2^9*4^5*2
Ln=12^n=T/2=3^7*8!*12!*2^9*4^5*2

n=20.98

Ln构造的所有全色魔方状态中，显然存在重复状态，也就是说，步长约为20的所有转式并不能构造出一半的魔方状态，但由此计算可以准确地给出一个极限值，即，最远状态至少大于20步(90度/步)。在此基础上，对于奇数步最远状态的合理推断应该是不小于21，偶数步最远状态不小于22

国外对三阶纯色魔方，动用了庞大的计算资源，历经20多年努力，得出的最终结果是20，而这里采用严密又又极其简单的计算法,算出的非优化结果是不小于19，二者是不是非常接近?作者是非常害怕与天文单位的状态数迎头对决,但,确实有人敢于面对.很多事情,只要愿意,经耐心细至地分析,总能找出更为巧妙的解决方法.这里采用的方法,稍加变更,可用于N阶最远状态推断.


算法

在上面的分析计算的基础上，可以构造一个相当简单而又精确的算法:

1.设转式长度初值(奇数或偶数)为这里的合理推断值n
2.构造一个n重循环，每层循环初值是1终值是12，由些生成所有长度为n的转式
3.将长度为n的每个转式在复原魔方上分别执行一次，产生一个状态，将此状态与已经产生的状态比较，记录新状态，丢弃重复产生的状态
4.转式执行完后(也许没有执行完，所有状态都生成了,此时可以退出，但是有可能无法找出所有状态的最短生成转式），检查生成的状态数，如果状态数与奇数步或偶数步状态数相等,则这个n就是魔方的奇数步或偶数步最远状态,否则，转式长度加2,回到第一步
5.比较的奇数步与偶数步最远状态,最大者就是魔方的最远状态

说明

相信，稍有编程经验的玩家，都很容易将上面的算法变成代码。上面的算法中,可以设置无效转式(不改变魔方状态的转式)和等效转式过滤器，改善算法效率，当然这不是必须的.此算法只适用于二阶与三阶.显然，这个算法一定会精确找出三阶的最远状态。显而易见，这个算法，可以把任务分摊到多台计算机上去独立运算，比如，奇数步转式与偶数步转式可分开独立运算，同类型的转式又可以拆分成多多个段独立运算,状态数据库也可以独立创建2个,分别对应奇数步转式与偶数步转式.对于有限的资源,可以分次分批逐步完成.

这个算法似乎只能找出最远状态长度，然而，改进一下第三步，则可以找出所有状态的最短生成转式(可能不止一个)，只须增加转式的优化,记录，对比，丢弃较长的。一但建立起状态及其对应的最短生成转式数据库，剩下的所有问题仅仅是查询数据库。

作者向来认为,寻找任意二个魔方状态之间的最短转式这类与魔方状态数迎头对决的游戏不好玩,也没有多少含金量,形同背交通地图.


推广
二，三阶只有二个扰动状态，状态数等分二类，转式分为偶数步与奇数步二类；四阶五阶有四个扰动状态，状态数等分为四类，转式也分为四类；N阶有2^init(n/2)扰动状态，状态数等分为2^init(n/2)类，转式也分为2^init(n/2)类，每类转式都能构造1/（2^init(n/2))种状态,虽然每类转式构造的状态数完全相同且无交集,但是,与二三阶单一性质的转层(等效之后,仅有表层)相比,四阶及四阶以上,转层的性质已多样化,转层由表转层及性质不同的内转层构成，因此导致分析变得复杂，而二三阶由于转式结构的单一性,转式长度的奇偶互斥性,及长转式以下的所有短转式是长转式的子集（如，长度为分别为1，3，5的转式是长度为7的转式的子集，长度为分别为2，4，6的转式是长度为8的转式的子集），使得二三阶问题的处理相对简单，不过，处理三阶的思路和原则，为处理三阶以提供了重要的线索，N定律为构造计算方法提供了极其重要指导性原则。四阶及以上，相对复杂，但仍然可以处理，至少，被处理时间以分钟计，而不是年，后面再做描述。

pengw

完全可以推广到N阶，进行一步分析发现，一楼的算法也不准确，更新中。。。

pengw

回2楼，不知道你的结论是不是有正式的证明，我的推导应该不会小于40(90度/1步 ），也不知道现在证明的最小步数是多少，有理由相信，一楼分析是有依据的。如n=24,12^24远小于魔方状态数的一半，应该是错误的。

由于没有很好的消同态算法，最远状态是42(90度/1步 ），应该是相对合理的判断。

pengw

一楼上我算错了，已更正为:17.91

pengw

五楼回复是错误的，N值算错了，一楼已更正

pengw

回十楼，你说的很对。  从12^n中清除同态是一楼最终走向精确的关键，很多同态单从转式结构上就很容易判断，如你举的例子。再比如，一个长度为7的转式，U U‘BB‘XYZ，其中XYZ是随意的，那么这个转式共有4！个等效转式，因此，关键是如何找出一种针对转式的算法，从12^n中清除所有同态，如果做到这点，即可精确找出最远状态的长度，一楼的计算值取整加3应该是一种合法的做法，离目前已证明结论仍然有3的差距，但处理方法相对简单。有一点是显而易见的，即，转式越长，同态越多。

pengw

一楼纯色魔方最远状态非优化的推导值19已非常接近20，有谁愿意去弄一个无效转式与等效转式过滤器？

pengw

四阶及以上也可以计算了，有谁愿意给个独立算法或思路?

pengw

只须把无效转式与等效转式过滤处法贴出来就行了,再不贴,我可是要发自已的,哈哈哈

pengw

回25楼，24楼是在开玩笑，只有初步设想，大致是，清除无效转式与等效转式(偶数步转试)，或只清除等效转式(奇数步转式),有些仅分析转式就能确定,而另外一些是从转式上无法分析出来,目前主要方向还放在构造N阶下界的计算方法上,经测算,四阶纯色的A‘B1‘(A簇与B1簇同为奇态簇)类状态的最远状态不小于22,另外三个扰动关系(,A‘B1,AB1‘,AB1)尚未计算