a******e
发帖数: 95 | 1 发信人: glider (sui sui), 信区: Algorithm
标 题: 小小总结一把 Re: 再来一题
发信站: 南京大学小百合站 (Thu Aug 9 07:52:45 2001), 站内信件
100多年前有一位同学不知怎么想的就发明了15-puzzle，但是这个游戏得到风靡
的一个原因是这位给出了1000元的奖金，悬赏第一个成功将一个状态移到目标状态
的智者。结果没有人能够拿到这笔巨款，因为这个问题无解，除非耍赖。
后来呢，就有人发现15-puzzle的状态可以均分为两个状态集：同一状态集中的
任意两个状态可以相互转换，非同一状态集的则不能。证明后一半不难，先从8-puzzle
开始，目标状态是：
1 2
3 4 5
7 8 9
对任意一个状态，如果按照从左到右，从上到下的顺序列出，去掉空白，就是
一个8个数的排列了。如果空白左右移动，排列不变。如果空白上下移（如果可以的话，
相当于排列中的某一数向前或向后移2个位置，不难证明新的排列逆序数齐偶性不变。
所以无论空白如何移，其产生的 |
|
