询问这个局面的20步解法

f4f4f4

看了魔方与上帝之数
了解到还原任何状态只需要20步
有一个全部棱方块都反转的局面
用Cube Explorer计算需要21步
R L F U2 R2 U' D' F2 R' F B U L2 B2 D2 R2 D' L2 D B2 D  (21f)
问20步怎么解决？

kexin_xiao

我对各位研究者佩服之至,努力学习

gozichen

对进行理论研究的同志致于最高的敬意。

但对我来说，看到这种贴我想起了郑板桥最著名的那四个字。

sokoban

穷举法找最小步数，如果算法逻辑上没有错，编程过程也没有错，计算机硬件也没有问题的话，那么算出来的最小步数是值得信赖的。 我们都没有检查过上述过程，所以也不能保证程序的计算一定是对的。另外，穷举法的计算速度还是有很大改进的地方。

据该程序作者说，他已经对成千上万（其实可能是数十万，数百万）的状态用穷举算法找最小步数，没有找到过需要20步以上的。

所谓“上帝之数”，的确是理论意义更大一些，是所有状态复原的最小步数的最大值。

乌木

噢，那么，6楼的结果恰好证明该打乱态的最少复原步数没超过20。或许可以这么说，凡是用穷举法获得的复原步数，应该不超过20（当然，“20”本身还有待最后敲定），否则就说明方法还有待改进。对吗？至于寻找“上帝之数”课题的目的，倒不在于开解哪个具体的打乱态，而是从理论上探究魔方复原最少步数的极值。这课题当然对有关的种种具体小课题会有莫大的指导意义。对吧？

sokoban

你对“上帝之数”的理解是对的。

对于楼主所提及的软件 Cube Explorer，有两种计算模式。一种是所谓“二阶段搜索法”，这个方法只是找到一个步数较少的还原公式，但软件用时很短。

另外还有一种计算模式，可以计算任何一个状态的最小还原步数。这是一种本质上是穷举的计算方法，软件计算时间比较长(6楼的结果计算了一个多小时)，但是算出来的还原公式一定步数最小（在180度算一步意义上）。在此种模式下计算的步数一定是最小步数。

乌木

谢谢指点。17楼介绍的“原文”中的讨论部分中卢昌海的话也说明了“20步”的一步包含180度也算一步的，卢说：“网友： 卢昌海 发表时间： 2008-12-01, 09:14:17
是的。也有人讨论只用90度转动的情形，这时180度就得算两次转动，不过在讨论“上帝之数”时人们不用那种约定（如果用的话“上帝之数”将不会是20，比如有些组合需要24次90度转动才能复原）。”

我还有一个问题请教各位。那些数学家探讨的“上帝之数”并不是针对哪个具体打乱态求复原的具体步骤，而是总体上探讨魔方复原的最少步数的极值－－任一打乱态有其最少复原步数，有的少，有的多；各种打乱态的种种最少步数，总起来看，数学家们认为不会多于20步。我这样理解对吗？

而本帖是这么回事－－提出一个状态，用有关软件获得具体的复原步骤，再加以讨论一番。诸如此类，我总觉得和“上帝之数”并非一回事。那开解软件所用的方法是否保证得到的是最少步？即使针对某一打乱态所得的复原步数小于20，比如19步，是否不能再少？这19步能说明什么问题呢？最多表明了没超过“上帝之数20”罢了。但是，这19步是不是该打乱态所对应的“上帝之数”（我是指该打乱态的最少复原步数）呢？

我没什么数学基础，也许问题本身就不对，望各位指正。

[ 本帖最后由 乌木 于 2008-12-30 16:00 编辑 ]

sokoban

再给出一个最原始的文献中对步数的定义：

Each move on the cube consists of grabbing the
nine cubies that form a full face of the larger cube,
and rotating them as a group 90 or 180 degrees
around a central axis shared by the main cube and
the nine cubies.

摘自《Twenty-Five Moves Suffice for Rubik’s Cube》一文。就是此文
作者通过计算证明22步足矣。(注：文章是老文章，只证明到25步。但基本方法
一样，所以作者虽然证明到22步了，但文章没有更新。可以看他的主页：
http://63.197.151.31/)

从中可以看出，180度算是一步的。

[ 本帖最后由 sokoban 于 2008-12-30 12:11 编辑 ]

sokoban

五楼的

为了使这一问题有意义， 当然首先要定义什么是转动。 在对魔方的数学研究中， 转动是指将魔方的任意一个 (包含 9 个小方块的) 面沿顺时针或逆时针方向转动 90° 或 180°， 对每个面来说， 这样的转动共有 3 种 (请读者想一想， 为什么不是 4 种？)。 由于魔方有 6 个面， 因此它的基本转动方式共有 18 种。

是一个注释，解释了什么是一次转动。这是对正文中的

那么， 最少需要多少次转动， 才能确保无论什么样的颜色组合都能被复原呢[注四]？

的一个注释。也就说定义了什么是一次转动。无论转180，还是转90，都算成一次。

转帖时，注释关系看不清楚，可查看原文：http://www.changhai.org/articles/science/mathematics/rubikcube.php

乌木

原帖由 sokoban 于 2008-12-29 16:27 发表
老外所说的20步，也是180度算一步的。可参加
http://bbs.mf8-china.com/viewthread.php?tid=19096
的5楼的说明。

那5楼的说明只是讲魔方表层转动方式的种类，他说：“为了使这一问题有意义， 当然首先要定义什么是转动。 在对魔方的数学研究中， 转动是指将魔方的任意一个 (包含 9 个小方块的) 面沿顺时针或逆时针方向转动 90° 或 180°， 对每个面来说， 这样的转动共有 3 种 (请读者想一想， 为什么不是 4 种？)。 由于魔方有 6 个面， 因此它的基本转动方式共有 18 种。”

我想想，或许老外在那种计算（有人叫“两阶段搜索法”，是吗？）中，还是把180度转当作两步的。上面那注释中把180度转当作转动方式之一，不见得在两阶段搜索时，也一定把180度转动当作一步来统计。转动方式和步数统计法不一定要一致的吧？

我的意思是想问问，楼主获得的21步解法是不是和数学家们猜想的“20步”仅差一步？会不会还差得多呢？