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

黑白子

纯色魔方每步90度，最远状态不会大于24。

黑白子

这个思路到时很新颖，是否能推广到n阶魔方呢？

pengw

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

pengw

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

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

pengw

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

黑白子

pengw 发表于 2015-2-18 21:37
回2楼，不知道你的结论是不是有正式的证明，我的推导应该不会小于40(90度/1步 ），也不知道现在证明的最小步 ...

没有，我说的话不严谨。情况是这样的，我在使用软件计算五色棋盘最远状态时，发现用24步就足够了，更令人惊奇的是，除12棱块翻转外，我再也没找到用大于或等于24步的状态。于是，有了下面的猜想：三阶纯色魔方每步90度，最远状态不大于24步。

  
  
  

黑白子

详细可参考这个帖子
http://bbs.mf8-china.com/forum.p ... page%3D4&page=2

pengw

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

铯_猪哥恐鸣

纯色魔方，每步90度，其上帝之数已被证明为26。http://cube20.org/qtm/

最远状态如下：


  
  
  


这是迄今为止发现的唯一一个需要26步才能复原的状态。


另外，楼主的结论其实可以进一步加强，因为12^n这些转动中其实有很多是无效的，例如如果出现了“R' R”，那显然这个序列应该被去除，另外“R L”和“L R”是同一个转动，被计算了两次。将此类废步去掉后结果可以进一步被加强（因为给定转动数n，可以达到的状态会少很多）。

在国外，无上述废步的转动序列一般称为canonical move sequence。在 http://cubezzz.dyndns.org/drupal/?q=node/view/301 这个帖子中给出了n阶魔方转动k步后可能的canonical move sequence个数。再结合n阶魔方状态数，即可给出n阶魔方上帝之数的下界。部分结论可参考：http://cubezzz.dyndns.org/drupal/?q=node/view/236