魔方吧·中文魔方俱乐部

标题: 移动数字的问题 [打印本页]

作者: jx215 时间: 2009-2-6 20:20:48 标题: 移动数字的问题

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

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

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

作者: tonylmd 时间: 2009-2-6 20:23:26

让我想到拼版拼图证明不会坐下观望

作者: aben306 时间: 2009-2-6 21:23:50

呵呵,不知道,没用过呵.

作者: 骰迷 时间: 2009-2-6 21:24:17

這個遊戲可難玩了...
該有點像魔方的菱/角，感覺上不能只換兩個。三個互換是可以的。那麼兩兩互換也是可以的。（像P03，做兩次就變成了兩兩互換）
倒是找最遠狀態要多少步有點興味，像魔方最少步還原。

作者: kexin_xiao 时间: 2009-2-6 21:37:00

过去,小的时候,玩过一种4*4的拼板游戏,和这个一样

作者: tonylmd 时间: 2009-2-6 21:38:30

我的解法是用循环的办法借助那个空格把方块按序归位在最后剩下的2×3的6格里做交叉换序调整此法可解任意大小规格的此类拼图随便说说词都没定义有更多了解的朋友推荐个系统教程吧

作者: 骰迷 时间: 2009-2-6 21:53:24

教程啊教程，叫人又愛又恨，愛自不說，恨卻是因為它經常連累到我不費心思，只會依賴，還是不發教程的為妙
有網站玩這個嗎？那可有趣得很了

作者: 骰迷 时间: 2009-2-6 23:28:15

剛才找不到網頁，自己剪了紙塊，玩過這個遊戲的3X3-1，4X4-1及5X5-1，感覺是全破解了。這得感謝一下LSS的Tony兄。
大家也來試玩一下啊，其實只要能破解3X3-1的遊戲，往上的全部都能一氣呵成，手到拿來，毫無難度。
流程：先做123，再做47，最後568
需要小小思考一下的是3和7兩個位置，此關一解，無關可絆！
若然隨意編排數字位置，十居其五能解。

作者: 骰迷 时间: 2009-2-6 23:35:33

不動手而判斷能否復原的方法：將打亂的方陣像背盲解一般歸納成幾個循環，若循環的數字總數為單數，則不需考慮；如總數為雙數，則記下＂一＂。若最後加起來的數字為雙數，此方陣能解。
這是一個很笨的法子，哪位高手能給出簡潔的答案？

作者: Vicki 时间: 2009-2-6 23:56:18

我记得我也发过类似的问题~
比如拿扑克牌来放那8个数字吧~
水平移动这样打乱的话是绝对可以还原的~
要是把两张或者几张扑克牌拿起来然后随意放的话就有可能还原不了~
就好像魔方随意装上是有可能还原不了的~

作者: Vicki 时间: 2009-2-6 23:58:52

我在手机文曲星PSP甚至扑克牌都玩过~
3*3 4*4 5*5都玩过了~
小时候那些塑料的也研究过~
只是有图案的比较难一点~
图案的话我也是先把它编号再玩的~
不过现在很难找了~
对了~顺便问问这种智力玩具叫什么？

作者: tonylmd 时间: 2009-2-7 00:03:52

（二）拼图的分类　　现在很多手机、电子词典上都有这款游戏，不知到大家在玩的时候有没有发现有的拼图怎么都还原不到完整的图片或数字顺序，出现有1对板块（两个）是对调的，这个时候你可以停下来了，这不是你水平的问题，是游戏设计者的过错！以3*3的九格为例，如下图：
| 1 2 3 | | 1 2 3 |
| 4 5 6 | | 4 5 6 |
| 7 8 | | 8 7 |
　a图 b图
假设图中的a是标准的结果，则图b是不可能变换成a的。证明起来需要用到高等代数里逆序数的概念，具体的说是用到了一个简单的定理：交换一个排列中的两个数，则排列的奇偶性发生变化。
我们将空格看成数字9，按正常顺序看a图，9个数字排列是123456789，其逆序数是0，是偶排列；b图是123456879，逆序数是1，是奇排列。我们知道，我们能够移动的只有9，这里的移动相当于一种特殊的对换。现在假设从b图经过一系列的平移变到了a图，则空格块9必然移动（对换）了偶数次（向左一次必然要再向右一次回来，向上一次必然要向下再回来），根据上面的定理最终变成的排列必然是奇排列（和b图相同），然而a图是偶排列，因而产生矛盾，因此b图不可能通过平移空格块变成最终的a图。
进一步考虑，a图可以平移变成一些其他的状态，我们把这些归为一类，b图也代表一类，现在要问“拼图总共有几类？”，答案是大于等于2*2的拼图都有且只有这2类。这里只介绍证明思想：
1. 根据上面的定理，所有的拼图至少分两类；
2. 2*2的拼图只有有两类；
3. 拼图在增大之后，分类数不增。
根据这3条就可得出结论：拼图有且只有两类。我们可以得出一些其他有趣的结果，两类拼图的差异是他们之间相差奇数次的对换，也就是说任意交换一个拼图非空板块奇数次，则它就变到另外一类里了。　　分为两类的本质原因是因为平面有两个面，正如顺时针和逆时针之分。
来自百度百科
http://baike.baidu.com/view/156489.html?wtp=tt

[ 本帖最后由 tonylmd 于 2009-2-7 18:24 编辑 ]

作者: 骰迷 时间: 2009-2-7 12:18:05

鍵進了網頁，發現上下兩個部份講的是兩回事，上面講的是拼砌而不講智力的玩具，下面講的是這個數學遊戲
把這兩種分類簡單化，一種是能搞定的，一種是不能的

另外，簡化了檢測狀態為能/不能搞定的方法：
不用移動的塊＋循環數量＝雙數＝能解
不用移動的塊＋循環數量＝單數＝不能解

作者: tonylmd 时间: 2009-2-7 12:31:51

循环数量是要像前面说的一个一个的推算吗…？
百度百科就是这样围绕一个主题自由添加条目都是wiki模式

作者: tonylmd 时间: 2009-2-7 12:35:07

也跟这两种拼图名字分类不清有关
貌似这种叫九宫格…？那还有16宫格25宫格…？

作者: 骰迷 时间: 2009-2-7 12:55:53

趕著吃飯，前面沒打清楚
312
845
76
那麼現在先看哪些是不用移的：7一個
循環節有：（132）（4865）兩個
1+2=3=奇數=不能解

作者: tonylmd 时间: 2009-2-7 13:13:12

在16宫格…或者256宫格里这种判断会不会………

作者: wpb93 时间: 2009-2-7 13:15:48

就是和拼图一样的嘛，肯定能回去，证明的话……是不是因为每个数字都可以通过移动来达到3x3方阵中的任意位置？

作者: 骰迷 时间: 2009-2-7 13:48:40

肯定能回去，證明的話......只要把SCRAMBLE倒轉來一次即可
不用移動的塊＋循環數量＋方格總數平方根＝單數＝能解
不用移動的塊＋循環數量＋方格總數平方根＝雙數＝不能解
上面對不對？

作者: 骰迷 时间: 2009-2-7 18:14:36

N階總狀態數（空格在右下）：（N^2-1）!/2
再加一問：3階最少步數還原為多少步？（假設必須遂步遂步移，如空格在右下，不能在3位置上往下推）

作者: lulijie 时间: 2009-2-8 21:29:12

9个数字分布在9个格子总状态数为9的阶乘=362880种
  其中右下角为空格的总状态数为8的阶乘=40320种。
用(123456789) 表示以下状态             9代表空格。
      1 2 3
      4 5 6
      7 8 9
经过电脑计算，经过移动能够成为目标状态（123456789）的总数为181217（包括该目标状态）。其中每种状态都有一个最少移动步数N,经过移动N步可以达成目标状态。
（123456789）的最少步数N=0
（123459786）和（123456798）  的最少步数N=1
   最远的状态为29步，（654321897）就是其中之一。逆序状态（987654321）为28步。
   右下角为空格的最远状态为28步，（564231879）是其中之一。
   右下角为空格的各种状态最少步数都是偶数。
----------------------------------------------------------------------------------------------------------------------
      最少步数N       总状态数    右下角为空格的总状态数
         0                         1                      1
         1                         2                      0
         2                         4                      0
         3                         8                      0
         4                         16                      2
         5                         20                      0
         6                         39                      8
         7                         62                      0
         8                      116                   26
         9                      152                      0
      10                      286                   48
      11                      396                      0
      12                      748                138
      13                   1024                      0
      14                   1893                364
      15                   2512                      0
      16                   4485                834
      17                   5638                      0
      18                   9529                1852
      19                   10878                      0
      20                   16993                3337
      21                   17110                      0
      22                   23952                4738
      23                   20224                      0
      24                   24047                4904
      25                   15578                      0
      26                   14560                3009
      27                   6274                      0
      28                   3910                854
      29                      760                      0
      总计             181217             20115

作者: lulijie 时间: 2009-2-8 21:37:34

右下角为空格的总状态数为8的阶乘=40320种。
其中经过移动最终可以变成目标状态的总数为20115种，比不能变成目标状态的总数20205稍少些，并不是各占一半。

作者: 骰迷 时间: 2009-2-8 22:16:58

這...這怎麼可能？為什麼不是均等？難道魔方（不算色向）隨機裝回，能擰完的機會不是二分一？怎麼可能數量不一樣？
另外，順逆序的最遠狀態步數理應一樣的啊。123456789、987654321只是符號，無論用什麼符號代表該塊的原本位置，本質上也沒有分別。逆序的456789213需要多少步？理論上是29步的。

[ 本帖最后由骰迷于 2009-2-8 22:30 编辑 ]

作者: lulijie 时间: 2009-2-8 22:23:41

相信事实吧，大多数情况下直觉都是错的。

作者: 骰迷 时间: 2009-2-8 22:36:13

建基"只是符號，無論用什麼符號代表該塊的原本位置，本質上也沒有分別"的理論，目標狀態跟非目標狀態的數量理應一樣。例如7、8是倒轉的，那麼所謂的＂目標狀態＂也相對的有一個＂反目標狀態＂，就是把它的78倒轉，形成反目標狀態。

作者: lulijie 时间: 2009-2-8 22:47:08

（456789213）21步

作者: lulijie 时间: 2009-2-9 11:59:57

右下角为空格的总状态数为8的阶乘=40320种。
其中电脑计算出的经过移动最终可以变成目标状态的总数为20115种，距一半还差45种。
我也觉得应该是一半的可能性大，我再仔细审查一下程序设计上是否有不当之处。

作者: oboe 时间: 2009-2-9 12:00:22

允许正反不一样吧。

在大量测试的时候，出现不均等的机会确实会狠大。

作者: lulijie 时间: 2009-2-9 12:23:03

设计上不是采取随机状态，而是从目标状态经过移动，得到新的状态，再从新的状态，移动得到再新的状态，一步步进行下去，每次得到新的状态后要检查它们，是否之前已经出现过的，已经出现过的不再计算进去，直到不出现以前没有出现过的状态为止。最后记录下运行中算出的所有状态，进行统计。
所以不存在大样本，概率的问题。

作者: 骰迷 时间: 2009-2-9 16:25:47

那麼，即是說：目標狀態＋反目標狀態（注意，這不是非目標狀態，反目標狀態即是將87倒轉）＜所有狀態數
有一些狀態雖然奇偶性一樣，但不能還原？

作者: 骰迷 时间: 2009-2-9 16:27:06

798123456要多少步?

作者: jx215 时间: 2009-2-9 19:34:08

原帖由 lulijie 于 2009-2-8 21:29 发表
9个数字分布在9个格子总状态数为9的阶乘=362880种
  其中右下角为空格的总状态数为8的阶乘=40320种。
用(123456789) 表示以下状态             9代表空格。
      1 2 3
      4 5 6
      7 8 9
经过电 ...

这位老师用的是什么软件或者用什么语言编程的？

作者: 骰迷 时间: 2009-2-9 20:42:40

還想請教一下：既然TONY說只有兩種類別的狀態，那麼大概可以分成12345678(9)與12345687(9)兩種原始狀態。請問12345678(9)的狀態數跟12345687(9)的狀態數是不是一樣？若是一樣，它們的總狀態數又是否等於　8!　？若是小於，那剩下來的幾種呢？它們兩個組別都不算了？還有第三種原始狀態麼？

作者: lulijie 时间: 2009-2-10 11:35:09

(798123456) 21步。
我用的是VB 6.0编程。
我昨天使用另一种编码，算出的结果还是一样。
现在使用第三种编码再算，如果还是一样，我就接受这个结果了。

作者: tonylmd 时间: 2009-2-10 12:06:52

tony只是引用哈
两位也可将最终结论编辑入百度百科中呀

作者: 骰迷 时间: 2009-2-10 18:02:21

我搞不懂了。
123
456
789
你旋轉看看，就變成這樣了：
987
654
321
所以說呢，這兩種次序基本是沒有分別的嘛。把順序的最遠狀態
654
321
897
旋轉過來：
798
123
456
移動的步數也是一樣的吧。請lulijie搞出798123456的二十一步，和654321897的二十九步中每一步弄出來，比對參照一下。

作者: lulijie 时间: 2009-2-10 19:56:25

原因找到了，范了一个很简单的错误，不是程序设计的问题，而是没把最后两步的结果记录下来。
程序设计的思想是：用3个变量保存数据。
JieGuo1 保存N步的已经扩展过的所有状态，
JieGuo0  保存N-1步的所有状态，
JieGuo 保存N步的未经扩展的所有状态和新增加的N+1步的状态。
处理N步的状态时，新增加的状态根据9在位置上的不同，可增加的新状态数为2 、3、 4个。
检查增加的新状态是否已经出现过，只要检查在JieGuo0 和 JieGuo中是否已经出现即可。（增加的N+1步新状态，前面出现过的只能出现在N-1步的状态中）
当N增加时，把JieGuo0  记到文件中，JieGuo1移到JieGuo0中。
程序结束时，却忘记把最后的JieGuo0  和JieGuo1，记录下来。
-------------------------------------------------------------------------------------
最终结果如下：
最少步数N       总状态数    右下角为空格的总状态数
         0                         1                      1
         1                         2                      0
         2                         4                      0
         3                         8                      0
         4                         16                      2
         5                         20                      0
         6                         39                      8
         7                         62                      0
         8                      116                   26
         9                      152                      0
      10                      286                   48
      11                      396                      0
      12                      748                138
      13                   1024                      0
      14                   1893                364
      15                   2512                      0
      16                   4485                834
      17                   5638                      0
      18                   9529                1852
      19                   10878                      0
      20                   16993                3337
      21                   17110                      0
      22                   23952                4738
      23                   20224                      0
      24                   24047                4904
      25                   15578                      0
      26                   14560                3009
      27                   6274                      0
      28                   3910                854
      29                      760                      0
      30                      221                   45
      31                         2                      0
      总计             181440             20160
-----------------------------------------------------------------------
最远的状态为31步，只有2个，（647859321）和（867254391）。
右下角为空格的最远状态为30步，（347682519）是其中之一。

作者: lulijie 时间: 2009-2-10 21:52:05

798123456最少移动步数21，具体如下：
7  8
123
456
  ↓
728
1  3
456
  ↓
728
153
4  6
  ↓
728
153
  46
  ↓
728
  53
146
  ↓
  28
753
146
  ↓
2  8
753
146
  ↓
28
753
146
  ↓
283
75
146
  ↓
283
7  5
146
  ↓
283
  75
146
  ↓
283
175
  46
  ↓
283
175
4  6
  ↓
283
1  5
476
  ↓
2  3
185
476
  ↓
  23
185
476
  ↓
123
  85
476
  ↓
123
485
  76
  ↓
123
485
7  6
  ↓
123
4  5
786
  ↓
123
45
786
  ↓
123
456
78
-----------------------------------------------------------
654321897最少移动步数29，具体如下：
654
321
8  7
  ↓
654
3  1
827
  ↓
6  4
351
827
  ↓
  64
351
827
  ↓
364
  51
827
  ↓
364
5  1
827
  ↓
364
51
827
  ↓
364
517
82
  ↓
364
517
8  2
  ↓
364
517
  82
  ↓
364
  17
582
  ↓
364
1  7
582
  ↓
364
17
582
  ↓
36
174
582
  ↓
3  6
174
582
  ↓
  36
174
582
  ↓
136
  74
582
  ↓
136
7  4
582
  ↓
136
74
582
  ↓
136
742
58
  ↓
136
742
5  8
  ↓
136
742
  58
  ↓
136
  42
758
  ↓
136
4  2
758
  ↓
136
42
758
  ↓
13
426
758
  ↓
1  3
426
758
  ↓
123
4  6
758
  ↓
123
456
7  8
  ↓
123
456
78
------------------------
最远状态647859321，最少移动步数31，具体如下：
647
85
321
  ↓
64
857
321
  ↓
6  4
857
321
  ↓
654
8  7
321
  ↓
654
  87
321
  ↓
654
387
  21
  ↓
654
387
2  1
  ↓
654
3  7
281
  ↓
654
37
281
  ↓
654
371
28
  ↓
654
371
2  8
  ↓
654
3  1
278
  ↓
6  4
351
278
  ↓
  64
351
278
  ↓
364
  51
278
  ↓
364
251
  78
  ↓
364
251
7  8
  ↓
364
2  1
758
  ↓
364
21
758
  ↓
36
214
758
  ↓
3  6
214
758
  ↓
  36
214
758
  ↓
236
  14
758
  ↓
236
1  4
758
  ↓
236
14
758
  ↓
23
146
758
  ↓
2  3
146
758
  ↓
  23
146
758
  ↓
123
  46
758
  ↓
123
4  6
758
  ↓
123
456
7  8
  ↓
123
456
78
---------------------------------------------------
最远状态之二867254391，最少移动步数31，具体如下：
867
254
3  1
  ↓
867
2  4
351
  ↓
8  7
264
351
  ↓
  87
264
351
  ↓
287
  64
351
  ↓
287
364
  51
  ↓
287
364
5  1
  ↓
287
364
51
  ↓
287
36
514
  ↓
28
367
514
  ↓
2  8
367
514
  ↓
268
3  7
514
  ↓
268
  37
514
  ↓
268
537
  14
  ↓
268
537
1  4
  ↓
268
537
14
  ↓
268
53
147
  ↓
26
538
147
  ↓
2  6
538
147
  ↓
236
5  8
147
  ↓
236
  58
147
  ↓
236
158
  47
  ↓
236
158
4  7
  ↓
236
158
47
  ↓
236
15
478
  ↓
23
156
478
  ↓
2  3
156
478
  ↓
  23
156
478
  ↓
123
  56
478
  ↓
123
456
  78
  ↓
123
456
7  8
  ↓
123
456
78

作者: lulijie 时间: 2009-2-10 22:23:12

下面是九宫数字的解答程序，输入任何一种状态，空格用9代替，运行后就会给出具体移动步骤。若程序不能运行，可能与缺少VB运行环境有关。

九宫移动解法.part01.rar (250 KB, 下载次数: 0)

九宫移动解法.part02.rar (250 KB, 下载次数: 0)

九宫移动解法.part03.rar (246.31 KB, 下载次数: 0)

附件: [九宫移动解法part01] 九宫移动解法.part01.rar (2009-2-10 22:23:12, 250 KB) / 下载次数 0
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MzgzMjZ8MWRjNWRlMDF8MTc2MTM4MjQ2MnwwfDA%3D

附件: [九宫移动解法part02] 九宫移动解法.part02.rar (2009-2-10 22:23:12, 250 KB) / 下载次数 0
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MzgzMjd8NTIzMDJjMDB8MTc2MTM4MjQ2MnwwfDA%3D

附件: [九宫移动解法part03] 九宫移动解法.part03.rar (2009-2-10 22:23:12, 246.31 KB) / 下载次数 0
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MzgzMjh8NDU5NGU4YzV8MTc2MTM4MjQ2MnwwfDA%3D

作者: lulijie 时间: 2009-2-10 22:38:57

若程序不能运行，可能与组件没有注册有关，试试以下程序。不适用于win98系统。

组件注册.rar (186 Bytes, 下载次数: 0)

附件: 组件注册.rar (2009-2-10 22:38:57, 186 Bytes) / 下载次数 0
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MzgzMjl8MDE3NWIxZGF8MTc2MTM4MjQ2MnwwfDA%3D

作者: 骰迷 时间: 2009-2-10 22:57:58

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

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

作者: lulijie 时间: 2009-2-10 23:16:29

随便设置个目标状态，比如：
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 编辑 ]

作者: 骰迷 时间: 2009-2-11 17:46:41

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

作者: lulijie 时间: 2009-2-11 18:56:13

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

作者: 知Shmily足 时间: 2009-2-13 09:18:14

这个是拼图吗？？？

作者: Xwam 时间: 2009-2-19 15:43:02

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

作者: 骰迷 时间: 2009-2-19 19:45:33

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

作者: Cielo 时间: 2012-2-23 22:40:42

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

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

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

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)