注:此游戏很有名,有同学问我其算法,我在网上找了一下,居然没多少中文资料,这里按照以前看过的一份答案回忆整理贴出。
游戏规则很简单,$ 4\times4$ 的方格里有 15 个方格块,标记为 1 , 2 到 15 ,有个位置是空的。每次方块可以滑动到旁边的空格中(与华容道类似)。问是否可以变成左下图这种状态?
一个明确的问题是从左下图这种状态变到右下图的标准状态。听说有人靠卖这个积木游戏赚了大钱,并且设定了一个高额奖金。
1 2 3 4 -> 1 2 3 4
5 6 7 8 -> 5 6 7 8
9 10 11 12 -> 9 10 11 12
13 15 14 -> 13 14 15
定理:记空格为 16。初始状态为$ 1,2,\cdots, 16$ 的一个排列$ \pi$ 。方格黑白相隔染色。当且仅当$ \pi$ 为偶排列且空格位于白色格 或者 $ \pi$ 为奇排列且空格位于黑色格,可以移动到标准状态。
必要性:每次移动,$ \pi$ 的奇偶性都改变,空格所在格子颜色亦发生改变。
充分性:按照1,2,3,4,5,9,13,6,7,8,10,14,11,12,15
的顺序把格子移到正确的位置上即可。
推论:故从右上图是不可能变成左上图的。没有人能拿到奖金。
注 1 :一个排列$ \pi_1, \pi_2, \cdots, \pi_n$ 的奇偶性定义为$ \prod_{i>j}(\pi_i-\pi_j)$ 的符号。正为偶排列,负为奇排列。任意调换两个数的位置都会改变其奇偶性。
注 2 :此结论和证明对$ n\times n, n\geq 2$ 的情形都有效
附录
- 15 puzzle@wikipedia
- play online
Q. E. D.