15 puzzle

zhiqiangMarch 7, 2008 科学

注：此游戏很有名，有同学问我其算法，我在网上找了一下，居然没多少中文资料，这里按照以前看过的一份答案回忆整理贴出。

游戏规则很简单，4*4的方格里有15个方格块，标记为1，2到15，有个位置是空的。每次方块可以滑动到旁边的空格中（与华容道类似）。问是否可以变成左下图这种状态？

一个明确的问题是从右下图这种状态变到左下图的标准状态。听说有人靠卖这个积木游戏赚了大钱，并且设定了一个高额奖金。

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15

1	2	3	4
5	6	7	8
9	10	11	12
13	15	14

定理：记空格为16。初始状态为 $1,2,\cdots, 16$ 的一个排列 $\pi$ 。方格黑白相隔染色。当且仅当 $\pi$ 为偶排列且空格位于白色格或者 $\pi$ 为奇排列且空格位于黑色格，可以移动到标准状态。

必要性：每次移动， $\pi$ 的奇偶性都改变，空格所在格子颜色亦发生改变。

充分性：按照1,2,3,4,5,9,13,6,7,8,10,14的顺序把格子移到正确的位置上即可。

推论：故从右上图是不可能变成左上图的。没有人能拿到奖金。

注1：一个排列 $\pi_1, \pi_2, \cdots, \pi_n$ 的奇偶性定义为 $\prod_{i>j}(\pi_i-\pi_j)$ 的符号。正为偶排列，负为奇排列。任意调换两个数的位置都会改变其奇偶性。

注2：此结论和证明对 $n\times n, n\geq 2$ 的情形都有效

附录

15 puzzle 游戏

你可能感兴趣的

At 2008.03.07 11:22, amao said:

陈景润有本关于组合数学的书，是否有关于这个问题的详细的讨论。还给出了一个求解的通用算法。

[Reply]
At 2008.03.07 13:28, 中文赚钱博客 said:

在这里 http://www.holotronix.com/samlloyd15.php 玩这个游戏，移动了 314 此，成功！

[Reply]
- At 2008.03.08 10:06, erany said:
  
  231次
  
  [Reply]
At 2008.03.07 21:18, You Xu said:

另一个方法是标记空格的时候用蛇型，即
1 2 3 4
8 7 6 5
9 10 11 12
16 15 14 13
再使用同样的排列的奇偶性，就不需要染色了，移动的时候奇偶性是不变量

[Reply]
- At 2008.03.07 23:55, zhiqiang said:
  
  嗯, 你这种标记法更简单, 而且也可以推广到一般的情形.
  
  不过要说明的一点是你这个方法和文中的排列不同的一点是空格代表的16不在排列里面，也就说只管 $1,2,\cdots, 15$ 的排列的奇偶性．
  
  [Reply]
At 2008.03.08 06:49, GooMoo said:

那个点击文章等待的GOOGLE LAB的图标怎么出来的？加在代码的哪里啊?

[Reply]
- At 2008.03.09 00:58, zhiqiang said:
  
  你想做什么？
  
  我用的方法是在footer最后添加代码，然后positio n:fixed; top:200px; display:none;background-image:google.gif。需要的时候通过用javascript设定display='block'调出。这样在IE6下没有效果，但也不会产生页面错乱。IE7和Firefox下正常。
  
  [Reply]
At 2008.03.08 21:45, Hartmanis said:

http://acm.pku.edu.cn/JudgeOnline/problem?id=2893
就是这道题
从前你也玩过这个吧，我记得你是集训队成员之一

[Reply]
- At 2008.03.08 22:26, zhiqiang said:
  
  对啊。你是哪位？
  
  [Reply]
At 2008.03.09 01:15, GooMoo said:

我也想添加一个那样的程序，你点击文章等待的时候出现一像你现在这样的图标。昨天上网找一半天，找不到，有的找到了，看懂了，就是不知道怎么加代码。

[Reply]

« Google更懂阅微堂

上海老师到穷村 »

15 puzzle

15 puzzle游戏

10条留言

阅微堂

15 puzzle 游戏