移动数字的问题

jx215

手机上一个移动数字的游戏：
1    2    3
4    5    6
7    8  空格

每次将上面数字顺序打乱，然后经过若干次的移动之后，得到上面的排列顺序。 现在的问题是，将8个数字顺序无论怎么打乱，是否移动n次后总能得到上面正确的顺序？这个结论成立或不成立能否用数学方法证明？

上面是一个3×3的方阵，假如推广到4×4、5×5......n×n能否证明这个结论？

Cielo

原帖由 lulijie 于 2009-2-8 21:37 发表
右下角为空格的总状态数为8的阶乘=40320种。
其中经过移动最终可以变成目标状态的总数为20115种，比不能变成目标状态的总数20205稍少些，并不是各占一半。

对于任意一个“可以变为……”的状态，交换7、8，则成为“不能……”的状态；反过来也一样。所以两种应该各占一半才对，奇怪……
——————————————————————————————————————————————————————————
哦看到后面说了是一半了……

[ 本帖最后由 Cielo 于 2012-2-23 22:43 编辑 ]

骰迷

非也非也，那只能是遊戲設計者的錯。他不懂玩，他不懂數學。
拼圖的最少置換為三塊互換，兩塊互換的情況是做不出來的。

Xwam

这八个数无论怎样打乱都可以恢复上述顺序，因为我玩的时候出现过只有78位置不对，这就是说这8个数字的位置可以随便互换，所以应该是可以的，实践证明，但具体方法还不知道

知Shmily足

这个是拼图吗？？？

lulijie

最远的状态不是29步，是31步

骰迷

有理。也可推論出任何目標狀態的最遠狀態都是同一步數。那麼最遠步數還是二十九嗎？

lulijie

随便设置个目标状态，比如：
456
789
123
求 以下状态到前面目标状态的最少步数
654
123
987
------------------------------------
可以这样解：
先进行目标状态的转换
4→1
5→2
6→3
7→4
8→5
9→6
1→7
2→8
3→9
----------------------
按照同样的转换，将所求的状态转换
654          321
123     → 789
987          654
--------------------------
将321789654代入程序，解出具体步骤后，再转换回去就可。
解出为25步。具体步骤省略。
你要求的Case，也可这样求出。


上述解答有错误，9只能转换为9，否则会出错。
可以这么说，任何状态，求移动成 右下角为空格的目标状态所需的最少步骤，可以用上述转换法解答。

[ 本帖最后由 lulijie 于 2009-2-11 00:13 编辑 ]

骰迷

喔，仁兄，我知道我們之間產生了什麼分歧。
我針對的問題是：原始狀態無論是順序和逆序，最遠狀態必為相同步數。
可是你處理我提出的CASE時，原始狀態卻是順序的。而我的原意是這個CASE同樣也需要二十九步來回到逆序的原始狀態。希望也能編個程來證明一下。

最終的結果果然是：目標狀態=總狀態/2
那我對嘍～呵呵

lulijie

若程序不能运行，可能与组件没有注册有关，试试以下程序。不适用于win98系统。
       组件注册.rar (186 Bytes, 下载次数: 0)

2009-2-10 22:38:57 上传

下载次数: 0