 wumi0212（五迷）
|
|
|
10 楼：
lonelyboy寄来的答案
|
02年11月20日17点56分 |
下面的解答都来自水木清华BBS，我就懒得敲字啦，呵呵。
1，八数码问题
发信人: ontario (toronto), 信区: AI
标 题: 八数码问题
发信站: BBS 水木清华站 (Mon Jul 5 15:57:33 1999)
八数码问题,有两类互相不可以到达的状态,我用群论的方法给以证明.
同时给出判断的方法,不知算不算新鲜?
有书上给出同样的东东嘛?
--
※ 来源:·BBS 水木清华站 bbs.net.tsinghua.edu.cn·[FROM: 166.111.72.37]
发信人: Leonardo (流星*蝴蝶*剑), 信区: AI
标 题: Re: 八数码问题
发信站: BBS 水木清华站 (Mon Jul 5 16:48:00 1999)
【 在 ontario (toronto) 的大作中提到: 】
: 八数码问题,有两类互相不可以到达的状态,我用群论的方法给以证明.
: 同时给出判断的方法,不知算不算新鲜?
: 有书上给出同样的东东嘛?
好象ncic的walt在数学版有论述。
--
充分享受信息时代高科技,我每天使用联想厕所
※ 来源:·BBS 水木清华站 bbs.net.tsinghua.edu.cn·[FROM: 162.105.138.50]
发信人: ontario (toronto), 信区: AI
标 题: Re: 八数码问题
发信站: BBS 水木清华站 (Mon Jul 5 19:45:23 1999)
【 在 Leonardo (流星*蝴蝶*剑) 的大作中提到: 】
: 好象ncic的walt在数学版有论述。
是水母的数学工具版?吗我怎么没找到呢？
他是怎么说的，是用置换群来解吗？
--
※ 来源:·BBS 水木清华站 bbs.net.tsinghua.edu.cn·[FROM: 166.111.72.37]
发信人: Leonardo (流星*蝴蝶*剑), 信区: AI
标 题: Re: 八数码问题
发信站: BBS 水木清华站 (Mon Jul 5 20:44:00 1999)
发信人: walt (瓦尔特), 信区: mathematics
标 题: Re: 一定有解吗?
发信站: BBS 曙光站 (Mon May 17 20:58:30 1999)
【 在 lst (BigLazyCat) 的大作中提到: 】
: 在一个3*3的大方格的9个1*1的位置里放着8个1*1的小方格,标号分别是1至8,
: 以随机的顺序摆放这8个小方格,请问它能被移成以下的顺序吗?
: 第一排 : 1 2 3
: 第二排 : 4 5 6
: 第三排 : 7 8
按初始格局为各个位置编号（空格的编号为9）。则任何格局相当于一个排列。
容易证明：
1 初始格局对应于一个偶排列；
2 从初始格局出发，不断用9和别的元素交换位置，当9最后回到原来位置的时候，
一定是进行了偶数次对换，根据排列理论，最后形成的排列必定是偶排列；
3 第一排 ： 1 2 3
第二排 ： 4 5 6
第三排 ： 8 7
对应的是一个奇排列；
4 因此，合法的移动不能把初始格局变成3那样的格局，反过来也一样。
【 在 ontario (toronto) 的大作中提到: 】
: 是水母的数学工具版?吗我怎么没找到呢？
: 他是怎么说的，是用置换群来解吗？
--
充分享受信息时代高科技,我每天使用联想厕所
※ 来源:·BBS 水木清华站 bbs.net.tsinghua.edu.cn·[FROM: 162.105.138.50]
发信人: softmagic (魔术师), 信区: AI
标 题: Re: 八数码问题
发信站: BBS 水木清华站 (Tue Jul 6 09:34:47 1999)
【 在 ontario (toronto) 的大作中提到: 】
: 标 题: 八数码问题
: 发信站: BBS 水木清华站 (Mon Jul 5 15:57:33 1999)
:
: 八数码问题,有两类互相不可以到达的状态,我用群论的方法给以证明.
: 同时给出判断的方法,不知算不算新鲜?
: 有书上给出同样的东东嘛?
不就是个逆序数为奇为偶的两类嘛，不是什么新东西，
最多做个考试题罢了。
:
: --
: ※ 来源:·BBS 水木清华站 bbs.net.tsinghua.edu.cn·[FROM: 166.111.72.37]
--
你背得越多，你忘得越多；你忘得越多，你记得越少；
你学得越少，你忘得越少；你忘得越少，你记得越多。
所以，呵呵。。。
※ 来源:·BBS 水木清华站 bbs.net.tsinghua.edu.cn·[FROM: 166.111.68.179]
发信人: gr (高登·里弗), 信区: AI
标 题: 八数码问题
发信站: BBS 水木清华站 (Thu Mar 15 11:11:34 2001)
描述：
8数字在九宫格内的随机排列经过有限步形成以下目标排列：
|-------|
| 1 2 3 |
| 4 5 6 |
| 7 8 |
|-------|
问题：
1.对于所有可能排列而言，是不是有且只有两类不连通的子集？
2.如果用广度优先搜索策略，我怎样才能为每个排列和某个整数
之间建立一个一一对应的关系，以便查找？
--
“不知拿你怎么办才好”
※ 来源:·BBS 水木清华站 smth.org·[FROM: 202.38.86.176]
发信人: trivita (neutral), 信区: AI
标 题: Re: 八数码问题
发信站: BBS 水木清华站 (Thu Mar 15 13:03:28 2001)
是的，数论可以证明之。
至于映射关系很简单，比如下图对应整数123456780（也可以考虑字符串）
【 在 gr (高登·里弗) 的大作中提到: 】
: 描述：
: 8数字在九宫格内的随机排列经过有限步形成以下目标排列：
: |-------|
: | 1 2 3 |
: | 4 5 6 |
: | 7 8 |
: |-------|
: 问题：
: 1.对于所有可能排列而言，是不是有且只有两类不连通的子集？
: 2.如果用广度优先搜索策略，我怎样才能为每个排列和某个整数
: 之间建立一个一一对应的关系，以便查找？
: ...................
--
※ 来源:·BBS 水木清华站 smth.org·[FROM: 166.111.167.88]
发信人: princy (我要刷刷~~~~), 信区: AI
标 题: Re: 八数码问题
发信站: BBS 水木清华站 (Thu Mar 15 13:15:40 2001)
还有一种映射方法也可以
你把数字按一个固定顺序排好，如 1 2 3 4 5 6 7 8 0 (对应你这个例子）
然后算每个数字右边有几个数字比自己大
得到 a9 a8 a7 a6 a5 a4 a3 a2 a1 9个数，这里是 7 6 5 4 3 2 1 0 0
这样可以一一映射到整数
P = a9 * 8! + a8 * 7! + ... + a2 * 1!
这个映射是实质就是一个不等进制的Hash()函数
如a9是9进制的，a2是2进制的
这种映射的好处是稠密的
【 在 gr (高登·里弗) 的大作中提到: 】
: 描述：
: 8数字在九宫格内的随机排列经过有限步形成以下目标排列：
: |-------|
: | 1 2 3 |
: | 4 5 6 |
: | 7 8 |
: |-------|
: 问题：
: 1.对于所有可能排列而言，是不是有且只有两类不连通的子集？
: 2.如果用广度优先搜索策略，我怎样才能为每个排列和某个整数
: 之间建立一个一一对应的关系，以便查找？
: ...................
--
※ 来源:·BBS 水木清华站 smth.org·[FROM: 166.111.137.27]
发信人: gr (高登·里弗), 信区: AI
标 题: Re: 八数码问题
发信站: BBS 水木清华站 (Thu Mar 15 16:33:41 2001)
忘了说一下了，我之前就用这种方法，但如果我要对所有排列进行某种
标记的话，照下面的方法至少需要876543210 bit，内存够不够另说，光
分配就得半天。我寻找的是下文的“稠密”的方法，呵呵，anyway, thanks!
【 在 trivita (neutral) 的大作中提到: 】
: 是的，数论可以证明之。
: 至于映射关系很简单，比如下图对应整数123456780（也可以考虑字符串）
--
“不知拿你怎么办才好”
※ 来源:·BBS 水木清华站 smth.org·[FROM: 202.38.86.176]
发信人: Centerwise (比谁更疯狂!), 信区: AI
标 题: Re: 八数码问题
发信站: BBS 水木清华站 (Thu Mar 15 16:38:50 2001)
还有，好像八数码有解状态集合=9!/2，所以是不是可以有一种更好的
编码方法，使得码的最大值=9!/2
【 在 gr (高登·里弗) 的大作中提到: 】
: 如果确定没错的话，我就去编程了，呵呵，多谢多谢
--
※ 来源:·BBS 水木清华站 smth.org·[FROM: 166.111.137.228]
发信人: gr (高登·里弗), 信区: AI
标 题: Re: 八数码问题
发信站: BBS 水木清华站 (Thu Mar 15 17:21:01 2001)
已编程验证，稠密，而且我发现是和我迭代产生的排列的次序相同，即是已排序的，
呵呵。又一个问题：如何反演？
【 在 princy (我要刷刷~~~~) 的大作中提到: 】
: 还有一种映射方法也可以
: 你把数字按一个固定顺序排好，如 1 2 3 4 5 6 7 8 0 (对应你这个例子）
: 然后算每个数字右边有几个数字比自己大
: 得到 a9 a8 a7 a6 a5 a4 a3 a2 a1 9个数，这里是 7 6 5 4 3 2 1 0 0
: 这样可以一一映射到整数
: P = a9 * 8! + a8 * 7! + ... + a2 * 1!
: 这个映射是实质就是一个不等进制的Hash()函数
: 如a9是9进制的，a2是2进制的
: 这种映射的好处是稠密的
--
“不知拿你怎么办才好”
※ 来源:·BBS 水木清华站 smth.org·[FROM: 202.38.86.176]
发信人: princy (我要刷刷~~~~), 信区: AI
标 题: Re: 八数码问题
发信站: BBS 水木清华站 (Thu Mar 15 17:29:46 2001)
刚才的a9..a1与 整数 之间只是数的进制转换问题，
是一个 9/8/7/6/5/4/3/2/1 不定进制数和一个 10进制数的转换
这种转换和 2进制-10进制数 的转换方法几乎是一样的
把 2进制-＞10进制 转换中的2作为变量就可以了
有了a9..a1那从左可以直接推出状态了
【 在 gr (高登·里弗) 的大作中提到: 】
: 已编程验证，稠密，而且我发现是和我迭代产生的排列的次序相同，即是已排序的，
: 呵呵。又一个问题：如何反演？
--
※ 来源:·BBS 水木清华站 smth.org·[FROM: 166.111.137.27]
发信人: glass (海豚), 信区: AI
标 题: Re: 八数码问题
发信站: BBS 水木清华站 (Thu Mar 15 18:29:05 2001)
【 在 gr (高登·里弗) 的大作中提到: 】
: 已编程验证，稠密，而且我发现是和我迭代产生的排列的次序相同，即是已排序的，
: 呵呵。又一个问题：如何反演？
全排列＜---＞中介数。组合数学课讲过好几种不同的方法。
--
※ 修改:·glass 於 Mar 15 18:29:34 修改本文·[FROM: 166.111.184.66]
※ 来源:·BBS 水木清华站 smth.org·[FROM: 166.111.184.66]
发信人: grsucc (豆豆), 信区: AI
标 题: Re: 八数码问题
发信站: BBS 水木清华站 (Fri Mar 16 10:10:13 2001)
【 在 gr (高登·里弗) 的大作中提到: 】
: 忘了说一下了，我之前就用这种方法，但如果我要对所有排列进行某种
: 标记的话，照下面的方法至少需要876543210 bit，内存够不够另说，光
: 分配就得半天。我寻找的是下文的“稠密”的方法，呵呵，anyway, thanks!
这好像可以用置换群讨论吧。有两种等价的置换。
--
※ 修改:·grsucc 於 Mar 16 10:11:02 修改本文·[FROM: 166.111.68.178]
※ 来源:·BBS 水木清华站 smth.org·[FROM: 166.111.68.178]
发信人: trivita (neutral), 信区: AI
标 题: Re: 八数码问题
发信站: BBS 水木清华站 (Fri Mar 16 21:53:17 2001)
正解！
【 在 grsucc (豆豆) 的大作中提到: 】
: 这好像可以用置换群讨论吧。有两种等价的置换。
--
※ 来源:·BBS 水木清华站 smth.org·[FROM: 166.111.167.95]
2，关于八码数问题有解与无解的证明(zz)
发信人: YourMajesty (花痴~~~~小魔男), 信区: AI
标 题: 关于八码数问题有解与无解的证明(zz)
发信站: BBS 水木清华站 (Fri Nov 23 22:26:49 2001)
8数码难题搜索时，有时候是无解的，8数码问题总共有9!种状态，如果用计算机一
个一个去搜索去判断哪些有解哪些误解，无疑要花费很长的时间，也没必要。作为一种
智力游戏，玩之余，我在想，能否通过事先的分析来判断哪些问题有解，哪些问题无解
呢？对于有解的问题，是否能通过一种固定的步骤来得到解？经过昨天晚上和今天的仔
细分析，我觉得我已经得到了这个问题的初步解答，下面我公布一下我得到的结果和证
明，抛砖引玉，如果大家发现其中有什么问题，欢迎来我宿舍一起讨论或者给我发Emai
l。
我的证明分好几个步骤，恳请大家能够耐心的看下去，我会尽量说得简洁一点。
一、我的结论
我们将九宫格按行排成一行共九个数(空格也占一个位置，在本文种，我用@表示空
格)。比如： 1 2 3 4 @ 5 ＝＞ 1 2 3 4 @ 5 6 7 8 6 7 8 这样
，九宫格的每一种状态和上图的行之间是一一对应的。在代数上册我们学过逆序的概念
，也就是对于任意一对数，如果前面的数比后面的数大，则为一对逆序。对于一个序列
，我们定义其逆序奇偶性如下： 如果其中有奇数对逆序，称之逆序奇；如果其中有
偶数对逆序，称之为逆序偶。这样，对于1，2，...，n这n个数，其所有的排列可以分为
两类，逆序奇类和逆序偶类。相对应的，九宫图(除去空格)也有它的奇偶性，我们的定
理是：
所有的奇九宫图之间是可达的，所有的偶九宫图之间也是可达的，但奇九宫图和偶
九宫图之间互不可达。
二、问题的转化
为了证明上述定理，我想先对问题进行一下转化。我定义两种行序列的变换：一种
是空格@和相邻的数对换，一种是空格@和前后隔两个数的数之间的对换，前者对应着空
格在九宫图中的左右移动，后者对应着空格在九宫图中的上下移动。
引理一：在上述的两种对换下，序列的奇偶性不改变。 这个引理很容易证明。
首先，相邻的对换肯定不改变奇偶性；其次，隔两格的对换也不改变奇偶性，它相当于
三个数的轮换，我们可以自己列举一下几种情况验证一下。这就说明了奇九宫图和偶九
宫图之间是互不可达的。
引理二：转化后行序列在上面定义的两种对换下的任意操作，可以转换成九宫图中
空格的合法变化。 这个引理也是比较容易证明的。我们只要证明如下的几种状态之
间是互达的： a b c a b @ a b c a b c @ d e ＜=＞
c d e d e f ＜=＞ d e @ f g h f g h @ g h f
g h 通过计算机搜索，可以发现上面两对状态之间的确是互达的。从而，我们可以
假定上面两种状态之间的转换可以用行序列中的两种邻对换来代替。
想提一点的是，九宫图之间的变换是可逆的。下面，到了问题的核心部分了。
引理三：所有的奇状态可以转换为 @ 1 2 3 4 5 6 7 8, 所有的偶状态
可以转换为 @ 2 1 3 4 5 6 7 8. 要证明这个引理，得分几个步骤。我的想法是先设
法把8移到最后一个，然后8保持不动(注意，我们这里的不动只是形式上不动，但不管怎
样，我们的每一个变换后，8还是保持在最后一个，余类似)，再将7移到8之前，然后，
保持7和8不动，依次移动6，5，4，3，得到 * * * 3 4 5 6 7 8这里 * * *是 @ 1 2 的
一个排列。到这里，我想要得到前面的两种状态之一是显然的了。下面，我说明，上面
的想法是可以实现的。如下： 1. 对于 a b c @ ，我们可以将其中的任意一个移到
最后，并且对变换仅限于这四个位置上。显然，对于a，c是一步就可以做到的。对于b，
步骤如下： a b c @ -＞ @ b c a -＞ b @ c a -＞ b c @ a -＞ b c a @ -＞ @ c a b
2. 先把要移到最后位置的那个数移到最后四个位置之一，然后再将空格移到最后一
个位置，用1的方法将待移动的数变换到最后一个位置。循环这样做即可。 引理三证
毕。
证完了这三个引理，定理的成立就是显然的了。首先，将奇偶性相同的两种状态都
变换到上述两种标准状态之一，然后对其一去逆变换即可。以上是我的所有证明，有些
地方在计算机上写起来不是太清楚。
--
--
女人是最不要自由的灵魂
男人却为她游荡在每一夜
|
|
|
推 ,_ _ _,
门 \o-o/ ─┬─┬─ ┌─┬─┐ ╲─┼┼─ ┬─┐
四 ,(.-.), ╲│ │╱ ┼─┼─┼ ─┬┬─ │__└┐
大 _/ |) (| \_ │ │ └─┴─┘ ╲┌┼┼┐ │╳ │
恶 /\=-=/\ ─┴─┴─ ┌───┐ ││││ ╯ ┘
人 ,| \=/ |, ˊ│ˋ│ˋ │ │ │ │/\/\│ ┌┬┬┐
_/ \ | / \_ ╰─┘ ╱╲ ╱│ │ ┴┴┴┴
之 \_!_/
|
※来源: 【 推理之门 Tuili.Com 】.
|
|
您当前的位置：
推理之门 > 谜题解析 > 谜题大全
【版主】：tl,艾米,popodian
沪公网安备31011502006128号 推理之门 版权所有 2000-2026
