询问这个局面的20步解法

kexin_xiao

乌木老师的问题，我也想问。还有，在“CROSS8步内完成”，180度算几步？

sokoban

楼主这里所说的20步, 180度是算一步的.

乌木

原帖由 sokoban 于 2008-12-29 12:52 发表
楼主这里所说的20步, 180度是算一步的.

这是明摆着的。我是问老外说的“20步”的一步是怎么样的“一步”？会不会人家把180度算作两步？如果是的，那楼主获得的步数和20步就不是差一步的问题了。

sokoban

老外所说的20步，也是180度算一步的。可参加
http://bbs.mf8-china.com/viewthread.php?tid=19096
的5楼的说明。

[ 本帖最后由 sokoban 于 2008-12-29 16:28 编辑 ]

f4f4f4

非常感谢大家。因为机器只有256内存，算个最少13步的就要1个多小时，所以才在这里询问了。我猜想，或许再过4年，上帝之数为20就可以被机器证明了，或许，这就是玛雅人选20进制为基本进制的根本原因。

乌木

原帖由 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步”仅差一步？会不会还差得多呢？

sokoban

五楼的

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

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

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

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

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

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 编辑 ]

乌木

谢谢指点。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

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

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

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