移动数字的问题

Vicki

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

tonylmd

（二）拼图的分类　　现在很多手机、电子词典上都有这款游戏，不知到大家在玩的时候有没有发现有的拼图怎么都还原不到完整的图片或数字顺序，出现有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 编辑 ]

骰迷

鍵進了網頁，發現上下兩個部份講的是兩回事，上面講的是拼砌而不講智力的玩具，下面講的是這個數學遊戲
把這兩種分類簡單化，一種是能搞定的，一種是不能的
另外，簡化了檢測狀態為能/不能搞定的方法：
不用移動的塊＋循環數量＝雙數＝能解
不用移動的塊＋循環數量＝單數＝不能解

tonylmd

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

tonylmd

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

骰迷

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

tonylmd

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

wpb93

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

骰迷

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

骰迷

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