[原创]基于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定律为构造计算方法提供了极其重要指导性原则。四阶及以上，相对复杂，但仍然可以处理，至少，被处理时间以分钟计，而不是年，后面再做描述。

黑白子

铯_猪哥恐鸣 发表于 2015-3-9 11:58
我认为猜想有很大的可能不成立。一些参考数据：
对于三阶纯色魔方，如果只允许转动R和U，则上帝之数为25 ...

第二条是否意味着唯棱魔方的最远状态是15步?

pengw

正确

黑白子

pengw 发表于 2015-3-17 14:40
c(n,a)=c(n,n-a) ok?ok!

这就对了

这样证明的

pengw

显然,最远状态要么是奇数步,要么是偶数步,如果能确认,则可以减少一半的搜索量

pengw

c(n,a)=c(n,n-a) ok?ok!

这就对了

黑白子

pengw 发表于 2015-3-17 11:54
回楼上，三阶是这样的。四阶及以上，要看看扰动方程的数量和结构。

四阶:

这个容易，利用二项式定理，立刻可以证明。

pengw

回楼上，三阶是这样的。四阶及以上，要看看扰动方程的数量和结构。

四阶:
扰动方程1:S=A+C1,奇数步
扰动方程21=B1，奇数步
扰动方程3:S+L1=A+C1+B1，偶数步
扰动方程4:无奇态簇，偶数步

六阶:
奇数步状态种类:C(3,1)+C(3,3)=4
偶数步状态种类:C(3,2)+1=4

八阶:
奇数步状态种类:C(4,1),C(4,3)=8
偶数步状态种类:C(4,2)+C(4,4)+1=8

十阶:
奇数步状态种类:C(5,1)+C(5,3)+C(5,5)=5+10+1=16
偶数步状态种类:C(5,2)+C(5,4)+1=10+5+1=16

-----------------

经上面初略枚举，N貌似偶数步状态数与奇数步状态数相等

-----------------

你可证明以下算式:

n>=5

mod(n/2)=1, c(n,1)+c(n,3)..+c(n,n)=c(n,2)+c(n,4)..+c(n,n-1)+1
mod(n/2)=0,c(n,1)+c(n,3)..+c(n,n-1)=c(n,2)+c(n,4)..+c(n,n)+1


注:C(a,b),表示以a为底b的组合数
-------------------

如果算式成立,则N阶偶数步状态数与奇数步状态数必相等

黑白子

对于n阶魔方，奇数步状态的个数与偶数步状态的个数永远相等吧？

pengw

最后再强调一次个人观点，面对天文单位都嫌小的状态数，基于转式数的各类下界计算方法，误差也不会很大，差不多也就一步，所以粗糙算法与做了转式优化及加入了扰动约束后的算法算出的结论相差无几，反而，粗糙算法计算更为简单，不会因为扰动约束转式结构(例如,四阶某扰动下,同一转式中,各类转层转量必须是奇数)及转式优化而被迫面对复杂计算.