鸿利在线|北京Thinkpad水货|IBM水货|Thinkpad笔记本|Thinkpad全球购|Thinkpad美行|Thinkpad水货笔记本|Thinkpad港行笔记本|Thinkpad T14|X13|P15|P17|P1隐士| X1 Carbon 9代 |T14S|2021款X1 Carbon|X1 隐士|Thinkpad非官方论坛|Thinkpad工作站|Thinkpad笔记本论坛|Thinkpad水货

标题: 寻找天才有奖竞猜 [结束获奖会员MIKE_IBM ] [打印本页]

作者: dv2d4admin 时间: 2007-9-13 10:30 标题: 寻找天才有奖竞猜 [结束获奖会员MIKE_IBM ]

题目：本周题目易于上周，提醒大家虽然比上周容易但是也有一定难度大家不要投机取巧作弊，否则会给你大大的红叉！

细则：请点链接http://www.supuzzle.com/supuzzle2.swf

然后点
的未命名.jpg

将右边的扑克牌摆放成左边的样子然后截取图片发到论坛即可！如下图所示！
898未命名.jpg

时间：不限，第一个给出正确图片的将获得以下奖品！

奖品：由博扬新思提供

棒球帽￥30
订购

------------------------------------

折叠生活701桌￥90订购
------------------------------------------

获奖会员：MIKE_IBM

因为在79楼给出答案

是先出现you win的画面，然后是play again.

图片如下~

并且在：81楼给出证明

关于这题的无解的证明如下：

有人发现15-puzzle的状态可以均分为两个状态集：同一状态集中的
任意两个状态可以相互转换，非同一状态集的则不能。证明后一半不难，先从8-puzzle
开始，目标状态是：

1 2
3 4 5
7 8 9

对任意一个状态，如果按照从左到右，从上到下的顺序列出，去掉空白，就是
一个8个数的排列了。如果空白左右移动，排列不变。如果空白上下移（如果可以的话，
相当于排列中的某一数向前或向后移2个位置，不难证明新的排列逆序数齐偶性不变。
所以无论空白如何移，其产生的排列逆序数齐偶性恒定。

下一步看15-puzzle了，其目标状态是

1 2  3 4
5 6  7 8
9  10 11 12
13 14 15

空白左移右移，排列不变。空白上移或下移一次，排列逆序数齐偶性倒转。要构造
出一个恒定的measurement，我们可以用逆序数与空白所在行的行数之和的齐偶性。根据这
种齐偶性很容易判断出一个状态是否有解。

不过一些研究者却发现这种sliding-tile puzzles是一个很好的搜索算法的试验场，
于是许多search enhancements陆陆续续被提出，在人工智能很多领域都得到了应用。不
过他们更关心一个instance的最优解，即用最小的步数移到目标状态。下面是一些介绍
了：

1. 8-puzzle: 已经全部解决。所以有解状态都被解出。最难的状态需要31步
2. 15-puzzle: 能够比较快得解出随机生成的instances
3. 24-puzzle: 能够解出随机生成的instnaces，但是需要很多时间(比如1个月以上）。
一般最优解的长度在100以上，

对于n*m puzzle (m,n>1) 且n为齐数，逆序数齐偶性相同的状态可以相互转化。
(n为列数，m为行数).偶就不严密证了，点点就行了：

首先，注意以下转换：

1 2 -> 1 2
3 4 5 5 3 4

要不熟的话，排一排也就出来了，大概要十来步。这个转换告诉我们一行中
任意元素可以跳到与其相距为二的同一行位置，且有一相邻行有空格。（在
例子中，5插到3的位置）。

接下来我们又可以得到以下转换：

1 2 -> 3 1 2 -> 1 2 3
3 4 5 4 5 4 5

这步直接用到了上面的结论。　　　
　　　　　　　　　　　
所以我们可以得到以下结论：排列相同的状态都可以相互转化。
下一个引论就是：如果一个排列可以通过移动某一排列中的一个元素向前或者
向后两个位置得到，那么这两个排列所对应的状态都可以相互转化。这个引论
可以通过以上两个结论证出。
举个例子：

排列A: (1,2,3,4,5,6,7,8)
排列B: (1,4,2,3,5,6,7,8)
排列A 中将4 向前移动两位就可以得到排列B

所以状态
1 2 3 1 4 2
4 5 可以转化到 3 5 6
6 7 8 7 8

下面只需证明所有逆序数为偶数的排列都可以通过若干次两位移动从排列
(1,2,3,...,n-1,n)中得到，而逆序数为齐数的排列都可以通过若干次两位移动
从排列(1,2,3,...,n)中得到。这个可以用数学归纳法证明，比较简单。

n为偶数的情况:
定理一：如果相邻行有空格，经过有限次移动，一行中任意元素可以跳到与其相距为
二的同一行位置。

这个定理在前面已经证明了。一个推论就是该元素可以向前或向后移动偶数个位置。

下面观察一个2*4的转换：

1 2 3 4 1 2 3 4 3 1 2 3 1 4 2 1 4 2
4 5 6 7 -> 5 6 7 -> 5 6 7 -> 5 6 7 -> 3 5 6 7
4 up 3 jump ahead 4 jump back 3 down

于是我们可以得到以下结论：

对于2*4-puzzle，如果一个排列可以通过移动某一排列中的一个元素向前或者
向后两个位置得到，且在这两个排列所对应的状态中空白在第一行，这些状态
可以相互转化.

这个结论可以先推广到2*n-puzzle(n为偶数):
假设n=2k

1 2 ... 2k-1 2k 1 2 ... 2k-1
2k 2k+1 2k+2 ... 4k-1 -> 2k+1 2k+2 ... 4k-1
(2k up)

2k 2k-1 1 2 ... 2k-2 2k-1 1 2 ... 2k 2k-2
-> 2k+1 2k+2 2k+3 ... 4k-1 -> 2k+1 2k+2 ... 4k-2 4k-1
(2k-1 move 2k-2 steps ahead ) (2k move 2k-2 steps back)

1 2 ... 2k 2k-2
-> 2k-1 2k+1 2k+2 ... 4k-2 4k-1
(2k-1 down)

这个结论可以继续推广到m*n-puzzle(n为偶数):

定理二：对于m*n-puzzle(n为偶数,m>1), 如果一个排列可以通过移动某一排列中
的一个元素向前或者向后两个位置得到，且在这两个排列所对应的状态中空白
在第一行，这些状态可以相互转化.

这个定理比较好证，先把空格移下来，用完以后再移回去。

前面已经提了：所有逆序数为偶数的排列都可以通过若干次两位移动从排列
(1,2,3,...,n-1,n)中得到，而逆序数为齐数的排列都可以通过若干次两位移动
从排列(1,2,3,...,n)中得到。

于是我们又得到了以下引理：
对于m*n-puzzle(n为偶数,m>1)，空白在第一行且逆序数齐偶性相同的状态可以
相互转化。

实际上，空白在同一行的状态都有此种性质，所以我们得到下一个定理：

定理三：对于对于m*n-puzzle(n为偶数,m>1)，空白在同一行且逆序数齐偶性相同的
状态可以相互转化。

下面就是结论了，由定理三引出：

结论：对于对于m*n-puzzle(n为偶数,m>1)，逆序数与空白行数之和齐偶性相同的状态
可以相互转化。即：逆序数与空白行数之和为齐数的状态形成一个集合；逆序数
与空白行数之和为偶数的状态形成另一个集合。两个集合的状态数相等。任一
状态可以通过有限次移动达到同一集合的任一状态。不同集合的状态不能相互转化。

图片附件: 的未命名.jpg (2007-9-13 23:50, 6.42 KB) / 下载次数 820
http://nb591.com:8989/attachment.php?aid=17004&k=37ac2b4d7640c21594211484b64f1589&t=1731233510&sid=HAFNw4

图片附件: 898未命名.jpg (2007-9-13 23:50, 76.55 KB) / 下载次数 856
http://nb591.com:8989/attachment.php?aid=17005&k=25e45daa60ab3db5adf3162b24c06321&t=1731233510&sid=HAFNw4

作者: d-x-s 时间: 2007-9-13 10:30

沙发,顶了再看

作者: linkun1982 时间: 2007-9-13 10:38

不要又搞个无解的题逗我们啦

作者: sccsccscc 时间: 2007-9-13 12:40

期待一下~~~~
希望不要像水电气那个一样变态~~~~

作者: ad8888 时间: 2007-9-13 12:59

夜猫子

作者: zzwtae 时间: 2007-9-13 13:39

为什么要12点呢？都睡觉了

作者: frankrein 时间: 2007-9-13 13:44

呵呵，等明天看看啥题目，啥答案吧

作者: porlarbear 时间: 2007-9-13 14:26

咋就不盖楼了捏，俺们都是民工啊，盖楼最猛
非得给俺整智力题，俺字都认不全捏

作者: NBA 时间: 2007-9-13 16:20

我参加！！！！！！！！！！！！！！！！！！！！！！！

作者: weizifu 时间: 2007-9-13 17:21

占个位置，晚上来看。。。。。。。

作者: I小B黑M 时间: 2007-9-13 17:34

老吴又玩西的，12点才发布～！

天啊～！

作者: hydric 时间: 2007-9-13 18:38

为啥晚上12点啊？都睡觉了
9点不行吗，人还多一些

作者: zhangeddie_07 时间: 2007-9-13 18:43

呵呵又来了………………

作者: danny0798 时间: 2007-9-13 18:56

志在必得。。。。。。。。。。。。。。。。

作者: 博扬新思 时间: 2007-9-13 19:12

原帖由 danny0798 于 2007-9-13 18:56 发表
志在必得。。。。。。。。。。。。。。。。

我也是

作者: 黑粉 时间: 2007-9-13 19:18

先打块地盘占着再说

作者: qdna 时间: 2007-9-13 19:34

占个位置，晚上来看。。。。。。。

作者: redpark 时间: 2007-9-13 22:38

等待公布~~

作者: 电火 时间: 2007-9-13 23:39

还有２０分钟就到了，等待中～～～～～～
啊呀呀～～～
眼睛都看花了～～～～～
天才眼花了～～～
先回去睡觉了，明天再来发表答案

[ 本帖最后由电火于 2007-9-14 00:45 编辑 ]

附件: 1.jpeg (2007-9-14 00:45, 156.87 KB) / 下载次数 730
http://nb591.com:8989/attachment.php?aid=17008&k=2b6c3bd4147069ede27b7bdab0afd9a7&t=1731233510&sid=HAFNw4

作者: dv2d4admin 时间: 2007-9-13 23:43

原帖由 porlarbear 于 2007-9-13 14:26 发表
咋就不盖楼了捏，俺们都是民工啊，盖楼最猛
非得给俺整智力题，俺字都认不全捏

乱盖一通

没一点技术含量

作者: zhangeddie_07 时间: 2007-9-14 00:21

解不开啊～～～～～～～～～～～～～～～～～～～～～

作者: dv2d4admin 时间: 2007-9-14 00:22

原帖由 zhangeddie_07 于 2007-9-14 00:21 发表
解不开啊～～～～～～～～～～～～～～～～～～～～～

那你就不是天才喽

作者: stefsx 时间: 2007-9-14 00:31

坚定的怀疑又是一个无解的游戏
哪里是寻找天才嘛分明是整蛊游戏

....

作者: dv2d4admin 时间: 2007-9-14 00:35

原帖由 stefsx 于 2007-9-14 00:31 发表
坚定的怀疑又是一个无解的游戏
哪里是寻找天才嘛分明是整蛊游戏....

晕 ..................

上次的题有人给于答案了啊

这次的绝对不会啦唉

作者: 黑粉 时间: 2007-9-14 00:39 标题: 娃哈哈

娃哈哈，这是不是答案？

图片附件: [这是答案] 答案.JPG (2007-9-14 00:39, 107.25 KB) / 下载次数 644
http://nb591.com:8989/attachment.php?aid=17006&k=e51d257fe433f4041308eb7ef3d1ad3b&t=1731233510&sid=HAFNw4

作者: dv2d4admin 时间: 2007-9-14 00:40

原帖由黑粉于 2007-9-14 00:39 发表
娃哈哈，这是不是答案？

错解

看你3 4位置颠倒了

图片附件: 错未命名.jpg (2007-9-14 00:40, 114.11 KB) / 下载次数 634
http://nb591.com:8989/attachment.php?aid=17007&k=bde99d4f096699277bbdb3c60b7efa7c&t=1731233510&sid=HAFNw4

作者: zhangeddie_07 时间: 2007-9-14 01:06

……
LW作出来了？？？

作者: zhangeddie_07 时间: 2007-9-14 01:11

作不出了网上也没有解答除了PS不知还能怎样做出来睡去了大家继续努力吧

作者: MIKE_IBM 时间: 2007-9-14 01:14

终于搞出来了~

图片附件: snapshot001.JPG (2007-9-14 01:14, 108.3 KB) / 下载次数 699
http://nb591.com:8989/attachment.php?aid=17009&k=c893cae14072784248a4d2aad3dd2dce&t=1731233510&sid=HAFNw4

作者: yzy8971 时间: 2007-9-14 01:17

哎这种活动没劲了.......这么早就被猜到了..........哎.........睡觉了不费劲了........

作者: NBA 时间: 2007-9-14 01:18

最后两张。。。。弄不出来，LW给个帽子鼓励一下吧。

图片附件: NBA.JPG (2007-9-14 01:18, 119.16 KB) / 下载次数 647
http://nb591.com:8989/attachment.php?aid=17010&k=f9b87b4e99c8d4e035ad35d39ca783db&t=1731233510&sid=HAFNw4

作者: Along_99 时间: 2007-9-14 07:27

貌似有人做出来了，我就不跟着折腾了，还有，lw，你给的链接校园网看不到……下次给个国内的链接，或者放到服务器上吧，反正就是一个flash。

作者: dv2d4admin 时间: 2007-9-14 09:22

原帖由 NBA 于 2007-9-14 01:18 发表
17010

最后两张。。。。弄不出来，LW给个帽子鼓励一下吧。

大小王位置不对

图片附件: 20070914_b219a928b38e58c982db3S3m54QwdRTT.jpg (2007-9-14 09:22, 125.1 KB) / 下载次数 662
http://nb591.com:8989/attachment.php?aid=17011&k=e71c15ba2d0cf0855988562d437e6e63&t=1731233510&sid=HAFNw4

作者: mytzhf 时间: 2007-9-14 09:26 标题: 回复 #6 zzwtae 的帖子

希望不要像水电气那个一样无解,上次有点被忽悠的感觉!

作者: mytzhf 时间: 2007-9-14 09:28 标题: 回复 #1 dv2d4admin 的帖子

希望不要像水电气那个一样无解,上次有点被忽悠的感觉!

作者: 涩胆 时间: 2007-9-14 10:51

解不出来，我不是天才

作者: 涩胆 时间: 2007-9-14 11:09

总是差一对牌位置颠倒

作者: porlarbear 时间: 2007-9-14 11:19

是啊，总是差一对啊，无奈了

作者: I小B黑M 时间: 2007-9-14 11:23

呵呵，没准这次又像上次一样

作者: porlarbear 时间: 2007-9-14 11:26

原帖由 I小B黑M 于 2007-9-14 11:23 发表
呵呵，没准这次又像上次一样

不是吧，那可真吐血了......

作者: dv2d4admin 时间: 2007-9-14 11:46

原帖由 MIKE_IBM 于 2007-9-14 01:14 发表
终于搞出来了~

17009

你图片是PS的

图片附件: 20070914_0a87ebb26c2e3a93a64316ztcnPlhpJp.jpg (2007-9-14 13:57, 108.33 KB) / 下载次数 617
http://nb591.com:8989/attachment.php?aid=17017&k=5d814243b8f769a52d389cd0a392999e&t=1731233510&sid=HAFNw4

作者: weizifu 时间: 2007-9-14 12:12

PS的，你怎么知道？

作者: NBA 时间: 2007-9-14 12:19

能看出来的。。。。。。。。。。。。。。

作者: sccsccscc 时间: 2007-9-14 12:30

这个有解无解在于出题时的排列~~~~~
出题时注定了最后差一对，怎样排列都是差一对~~~~~~~
所以，虽然刚出题时的排列看似是随机的，但最后总是差一对~~~~~~~~

作者: luxoven 时间: 2007-9-14 12:44

怎么才能证明做出来了啊？

作者: luxoven 时间: 2007-9-14 12:45

哈哈，竟然有人PS。。。

作者: 黑粉 时间: 2007-9-14 12:57

基本上，这个游戏有问题，应该是左边的答案图有问题，大小王顺序变下就有解了。

作者: weizifu 时间: 2007-9-14 13:12

我点了N次。。。

作者: bao 时间: 2007-9-14 13:18

......怎么看出来ps的？

作者: 蓝色快车 时间: 2007-9-14 13:20

因为本身就是无解的，你解出来了，那就是PS得

作者: weizifu 时间: 2007-9-14 13:29

原帖由 蓝色快车 于 2007-9-14 13:20 发表
因为本身就是无解的，你解出来了，那就是PS得

刚去了外国网站看了。。。无解

作者: MIKE_IBM 时间: 2007-9-14 13:37

原帖由 dv2d4admin 于 2007-9-14 11:46 发表

你图片是PS的

这题明显是无解的，因为平到最后都会只有一对牌位置颠倒，如果有双数对的牌位置颠倒才可以最终解出

不过这样的游戏都是有Bug的，就看你会不会挖掘了~

所以不要动不动就说别人是PS的哦~

作者: weizifu 时间: 2007-9-14 13:44

如果是成功的话，会出现YOU WIN，而不是....

作者: tim5858 时间: 2007-9-14 13:46

高定了
[localimg=400,300]1[/localimg]

作者: tim5858 时间: 2007-9-14 13:47

高定了

图片附件: 11.gif (2007-9-14 13:47, 163.56 KB) / 下载次数 551
http://nb591.com:8989/attachment.php?aid=17015&k=dc3b8c786114c2f0a1de1f4a9add60ea&t=1731233510&sid=HAFNw4

作者: tim5858 时间: 2007-9-14 13:48

[localimg=400,300]1[/localimg]
高定了

作者: weizifu 时间: 2007-9-14 13:49

hehe ......hehe ..........

作者: dv2d4admin 时间: 2007-9-14 13:53

原帖由 tim5858 于 2007-9-14 13:47 发表
高定了
17015

作图水平太差

图片附件: 20070914_743f2a9a27a1fd9a5973XyMURHa8BGAb.gif (2007-9-14 13:53, 163.75 KB) / 下载次数 661
http://nb591.com:8989/attachment.php?aid=17016&k=75d81ef001ca6c94e38e648a0e5330cd&t=1731233510&sid=HAFNw4

作者: sccsccscc 时间: 2007-9-14 13:54

原帖由 tim5858 于 2007-9-14 13:47 发表
高定了
17015

完成后没有提示字样？

作者: weizifu 时间: 2007-9-14 14:04

有，WIN。。。。。。。

作者: dv2d4admin 时间: 2007-9-14 14:04

原帖由 sccsccscc 于 2007-9-14 13:54 发表

完成后没有提示字样？

因为他是PS的所以没有提示

作者: NBA 时间: 2007-9-14 14:57

此题的答案：无解
LW奖品归我！

作者: dv2d4admin 时间: 2007-9-14 15:04

原帖由 NBA 于 2007-9-14 14:57 发表
此题的答案：无解
LW奖品归我！

有解de
即便无解也需要证明

作者: weizifu 时间: 2007-9-14 15:24

原帖由 NBA 于 2007-9-14 14:57 发表
此题的答案：无解
LW奖品归我！

....这个答案早有了。。。。。

图片附件: 1.JPG (2007-9-14 15:24, 15.3 KB) / 下载次数 615
http://nb591.com:8989/attachment.php?aid=17018&k=1a8383864ef86da45b6e391602c79d49&t=1731233510&sid=HAFNw4

作者: dv2d4admin 时间: 2007-9-14 15:26

原帖由 weizifu 于 2007-9-14 15:24 发表

....这个答案早有了。。。。。

有解的

即便无解也并非给个无解的答案就获奖

得需要证明

证明论证为什么无解

作者: victor_1001 时间: 2007-9-14 15:36

原帖由 dv2d4admin 于 2007-9-14 00:35 发表

晕 ..................

上次的题有人给于答案了啊

这次的绝对不会啦唉

希望老吴不要忽悠人啊，你说的每一句话都将影响我们做题。也做为将来成堂正供！

作者: 涩胆 时间: 2007-9-14 15:54

竟搞些无解的，太无聊了

作者: dv2d4admin 时间: 2007-9-14 16:05

原帖由涩胆于 2007-9-14 15:54 发表
竟搞些无解的，太无聊了

那那么多没解的啊？

作者: andrewy 时间: 2007-9-14 16:44

老吴最近跨进更年期老搞这些无聊的事情。

此题无解！！！！！！！！

作者: segaxb 时间: 2007-9-14 16:45 标题: LW

老吴不要搞那么多无解的浪费脑细胞好不好。。。最后总有一个位置是和左边颠倒的所以绝对无解

图片附件: 1142406573422.jpg (2007-9-14 16:45, 58.29 KB) / 下载次数 587
http://nb591.com:8989/attachment.php?aid=17019&k=1ab3325c86ff07359cfcf8d085ec096c&t=1731233510&sid=HAFNw4

作者: I小B黑M 时间: 2007-9-14 17:02

这还得归到数学上来，如果是3的倍数就行，如9，15，而且要是单数，这样能移动的牌是双数，想想过去玩的拼图差不多都是。
以上纯属个人见解～
我不是天才～

作者: andrewy 时间: 2007-9-14 17:07

楼上的有点道理

作者: Iphone 时间: 2007-9-14 17:30

大家看看上周的水，电，气
再看看现在纸牌，都是这里的怪题，整点有意思的行不？

图片附件: 未命名.JPG (2007-9-14 17:30, 110.6 KB) / 下载次数 530
http://nb591.com:8989/attachment.php?aid=17020&k=4bba0c7848532ac6fd338f7e15f48ff3&t=1731233510&sid=HAFNw4

作者: sccsccscc 时间: 2007-9-14 17:38

看来LW要的是此题无解的证明~~~~~

谁能完整的，有逻辑的证明无解就能获得奖品~~~~~

作者: chhui2001 时间: 2007-9-14 19:47

应该有解的

图片附件: 未命名2.jpg (2007-9-14 19:47, 156.02 KB) / 下载次数 538
http://nb591.com:8989/attachment.php?aid=17021&k=ad54000ca66f57a6240fa0719945c5c6&t=1731233510&sid=HAFNw4

图片附件: 未命名.jpg (2007-9-14 19:47, 155.23 KB) / 下载次数 581
http://nb591.com:8989/attachment.php?aid=17022&k=430fa6131670f43bd4a00fed99f9e698&t=1731233510&sid=HAFNw4

作者: redpark 时间: 2007-9-14 20:38

是不是真的可以解到的.......玩了好久都不行............

作者: I小B黑M 时间: 2007-9-14 22:01

现在就是等着出最终答案了

作者: yzy8971 时间: 2007-9-14 22:09

恩相信有解.....如LW所说.....任何论证都需要证明......无解也要证明出来.....所以既然LW出了就肯定有解的办法......做不出来只是咱自己思维没绕出来......这时候考验思维的时候....加油......

作者: MIKE_IBM 时间: 2007-9-14 22:15

原帖由 weizifu 于 2007-9-14 13:44 发表
如果是成功的话，会出现YOU WIN，而不是....

是先出现you win的画面，然后是play again.

图片如下~

图片附件: snapshot000.JPG (2007-9-14 22:15, 108.58 KB) / 下载次数 659
http://nb591.com:8989/attachment.php?aid=17023&k=5c5c6a8ed40690c9ae2524f53aac0195&t=1731233510&sid=HAFNw4

图片附件: snapshot001.JPG (2007-9-14 22:15, 108.3 KB) / 下载次数 662
http://nb591.com:8989/attachment.php?aid=17024&k=a2980a02b3edac6707c04d52eda24e3d&t=1731233510&sid=HAFNw4

作者: yzy8971 时间: 2007-9-14 22:22

汗.....这就解开了 ?

作者: MIKE_IBM 时间: 2007-9-14 23:08

关于这题的无解的证明如下：

有人发现15-puzzle的状态可以均分为两个状态集：同一状态集中的
任意两个状态可以相互转换，非同一状态集的则不能。证明后一半不难，先从8-puzzle
开始，目标状态是：

1 2
3 4 5
7 8 9

对任意一个状态，如果按照从左到右，从上到下的顺序列出，去掉空白，就是
一个8个数的排列了。如果空白左右移动，排列不变。如果空白上下移（如果可以的话，
相当于排列中的某一数向前或向后移2个位置，不难证明新的排列逆序数齐偶性不变。
所以无论空白如何移，其产生的排列逆序数齐偶性恒定。

下一步看15-puzzle了，其目标状态是

1 2  3 4
5 6  7 8
9  10 11 12
13 14 15

空白左移右移，排列不变。空白上移或下移一次，排列逆序数齐偶性倒转。要构造
出一个恒定的measurement，我们可以用逆序数与空白所在行的行数之和的齐偶性。根据这
种齐偶性很容易判断出一个状态是否有解。

不过一些研究者却发现这种sliding-tile puzzles是一个很好的搜索算法的试验场，
于是许多search enhancements陆陆续续被提出，在人工智能很多领域都得到了应用。不
过他们更关心一个instance的最优解，即用最小的步数移到目标状态。下面是一些介绍
了：

1. 8-puzzle: 已经全部解决。所以有解状态都被解出。最难的状态需要31步
2. 15-puzzle: 能够比较快得解出随机生成的instances
3. 24-puzzle: 能够解出随机生成的instnaces，但是需要很多时间(比如1个月以上）。
一般最优解的长度在100以上，

对于n*m puzzle (m,n>1) 且n为齐数，逆序数齐偶性相同的状态可以相互转化。
(n为列数，m为行数).偶就不严密证了，点点就行了：

首先，注意以下转换：

1 2 -> 1 2
3 4 5 5 3 4

要不熟的话，排一排也就出来了，大概要十来步。这个转换告诉我们一行中
任意元素可以跳到与其相距为二的同一行位置，且有一相邻行有空格。（在
例子中，5插到3的位置）。

接下来我们又可以得到以下转换：

1 2 -> 3 1 2 -> 1 2 3
3 4 5 4 5 4 5

这步直接用到了上面的结论。　　　
　　　　　　　　　　　
所以我们可以得到以下结论：排列相同的状态都可以相互转化。
下一个引论就是：如果一个排列可以通过移动某一排列中的一个元素向前或者
向后两个位置得到，那么这两个排列所对应的状态都可以相互转化。这个引论
可以通过以上两个结论证出。
举个例子：

排列A: (1,2,3,4,5,6,7,8)
排列B: (1,4,2,3,5,6,7,8)
排列A 中将4 向前移动两位就可以得到排列B

所以状态
1 2 3 1 4 2
4 5 可以转化到 3 5 6
6 7 8 7 8

下面只需证明所有逆序数为偶数的排列都可以通过若干次两位移动从排列
(1,2,3,...,n-1,n)中得到，而逆序数为齐数的排列都可以通过若干次两位移动
从排列(1,2,3,...,n)中得到。这个可以用数学归纳法证明，比较简单。

n为偶数的情况:
定理一：如果相邻行有空格，经过有限次移动，一行中任意元素可以跳到与其相距为
二的同一行位置。

这个定理在前面已经证明了。一个推论就是该元素可以向前或向后移动偶数个位置。

下面观察一个2*4的转换：

1 2 3 4 1 2 3 4 3 1 2 3 1 4 2 1 4 2
4 5 6 7 -> 5 6 7 -> 5 6 7 -> 5 6 7 -> 3 5 6 7
4 up 3 jump ahead 4 jump back 3 down

于是我们可以得到以下结论：

对于2*4-puzzle，如果一个排列可以通过移动某一排列中的一个元素向前或者
向后两个位置得到，且在这两个排列所对应的状态中空白在第一行，这些状态
可以相互转化.

这个结论可以先推广到2*n-puzzle(n为偶数):
假设n=2k

1 2 ... 2k-1 2k 1 2 ... 2k-1
2k 2k+1 2k+2 ... 4k-1 -> 2k+1 2k+2 ... 4k-1
(2k up)

2k 2k-1 1 2 ... 2k-2 2k-1 1 2 ... 2k 2k-2
-> 2k+1 2k+2 2k+3 ... 4k-1 -> 2k+1 2k+2 ... 4k-2 4k-1
(2k-1 move 2k-2 steps ahead ) (2k move 2k-2 steps back)

1 2 ... 2k 2k-2
-> 2k-1 2k+1 2k+2 ... 4k-2 4k-1
(2k-1 down)

这个结论可以继续推广到m*n-puzzle(n为偶数):

定理二：对于m*n-puzzle(n为偶数,m>1), 如果一个排列可以通过移动某一排列中
的一个元素向前或者向后两个位置得到，且在这两个排列所对应的状态中空白
在第一行，这些状态可以相互转化.

这个定理比较好证，先把空格移下来，用完以后再移回去。

前面已经提了：所有逆序数为偶数的排列都可以通过若干次两位移动从排列
(1,2,3,...,n-1,n)中得到，而逆序数为齐数的排列都可以通过若干次两位移动
从排列(1,2,3,...,n)中得到。

于是我们又得到了以下引理：
对于m*n-puzzle(n为偶数,m>1)，空白在第一行且逆序数齐偶性相同的状态可以
相互转化。

实际上，空白在同一行的状态都有此种性质，所以我们得到下一个定理：

定理三：对于对于m*n-puzzle(n为偶数,m>1)，空白在同一行且逆序数齐偶性相同的
状态可以相互转化。

下面就是结论了，由定理三引出：

结论：对于对于m*n-puzzle(n为偶数,m>1)，逆序数与空白行数之和齐偶性相同的状态
可以相互转化。即：逆序数与空白行数之和为齐数的状态形成一个集合；逆序数
与空白行数之和为偶数的状态形成另一个集合。两个集合的状态数相等。任一
状态可以通过有限次移动达到同一集合的任一状态。不同集合的状态不能相互转化。

作者: 黑粉 时间: 2007-9-14 23:46

楼上受小弟一拜~再拜~三拜~~

送入洞房~

作者: yzy8971 时间: 2007-9-15 00:38

晕.....脑袋炸了.....数学超级差....别吓我

作者: I小B黑M 时间: 2007-9-15 08:45

真是天才～！

作者: d-x-s 时间: 2007-9-15 09:38

原帖由 MIKE_IBM 于 2007-9-14 23:08 发表
关于这题的无解的证明如下：

有人发现15-puzzle的状态可以均分为两个状态集：同一状态集中的
任意两个状态可以相互转换，非同一状态集的则不能。证明后一半不难，先从8-puzzle
开始，目标状态是：

1 2
...

看的头都大了

作者: yzy8971 时间: 2007-9-15 13:21

XD...."希尔伯特"当年没碰上你算他命好呀.....哎