注：此游戏很有名，有同学问我其算法，我在网上找了一下，居然没多少中文资料，这里按照以前看过的一份答案回忆整理贴出。
游戏规则很简单，$ 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.
