Algorithm 版 (精华区)

发信人: Darcy (麦克思韦妖), 信区: Algorithm
标  题: 关于八数码
发信站: 哈工大紫丁香 (2001年12月05日13:23:58 星期三), 站内信件

八数码的问题
大家（包括我）在玩八数码游戏是都感觉有些问题无解。
所有的八数码问题均可转化为以下两种形式
12345678＊
12345687＊
（＊表空格,整个棋盘用一行表示。下同）
而它们之间不能转化。
直觉是对的。证明如下
用一个数列表示八数码棋盘的一个状态。每个数列（不记＊的位置）的逆序数或奇或偶，
下证每一次变换不改变逆序数的奇偶性。
（注意下面只证明逆序数不同的不能相互转换，而未证明逆序数相同的可转换！！！！！
！）
左右移动显然不改变逆序数的奇偶性（＊略过）。上（下）移动某个棋子相当于将这个棋
子和其后面的棋子交换，在和后面的交换。（如 12345678＊ 变为12345786＊
相当于67交换，再68交换）两次交换后逆序数奇偶不变。
推广：维数为奇数的都可分为两个空间（如8数码，24数码，48数码等）
也不知是否说清楚了，大家指正。

--

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: biometrics.hit.edu.c]