随笔 - 51, 文章 - 1, 评论 - 41, 引用 - 0
数据加载中……

拼图游戏

 

      本文讨论如何判断拼图游戏中图形是否可以还原。

1是一个3X3的数字拼图

1

3

2

6


5

4

7

8

1

要还原成图2

1

2

3

4

5

6

7

8


2

      将问题一般化,在M*N的方格里有M*N-1个不同元素和一个空元素,只有空元素可以与上下左右相邻的元素交换位置。M*N方格中M*N-1个元素和一个空元素的位置确定一个图形。拼图游戏的问题是:一个图形经过一连串的交换能否得到另一个图形,如何得到。从交换方式的可逆性看出这种关系满足等价三性质,如果图形A通过交换变成图形B我们则称它们是等价的。把M*N-1个元素用1M*N-1编号,空元素编号0。然后展成一个排列。每个图形对应一个排列。确定了展开方式,图形和排列是一一对应的。这里用到的展开方式是行优先的顺序(其他方式展开也能到相应的结果)。将例1的两个图形展开有:图1对应1 3 2 6 0 5 4 7 8,图2对应1 2 3 4 5 6 7 8 0

      定理1图形A与图形B等价的充要条件图形A的排列的逆序数加上0元素行号和列号的奇偶性等于图形B的排列的逆序数加上0元素行号和列号的奇偶性。为方便表述,把图形排列的逆序数加上0元素行号和列号的奇偶性称为图形的奇偶性。

      先看定理1如何起作用,图1:展开的排列 1 3 2 6 0 5 4 7 8,它的逆序数为80元素行号为2,列号为2。逆序数加行号,列号的奇偶性为偶。图2:展开的排列 1 2 3 4 5 6 7 8 0,它的逆序数为80元素行号为3,列号为3。逆序数加行号,列号的奇偶性为偶。两个图形的奇偶性相同,根据定理1判断它们等价。

      首先证明必要性,即如果图形A图形B等价,则图形A的奇偶性等于图形B奇偶性。

              0元素和某个元素交换位置,则排列的逆序数的奇偶性就改变一次。交换后0元素的行号或者列号会加1或减1,即行号,列号之和的奇偶性也改变一次。这说明拼图的交换方式不改变图形的奇偶性,也说明拼图中至少有两组等价类,奇偶性不同的图形不等价。

      下面证明充分性,如果图形A的奇偶性等于图形B的奇偶性,则图形AB等价

      如果证明了拼图只有两组等价类,从必要性的证明过程可知,奇性图形是一组等价类,偶性是一组。从而证明了充分性。

      先考虑一般的排列1 2 3 ... N。某个元素连续与后面M相邻的元素交换位置,称为向后M步移动。如排列:1 2 3 4 5 6。元素2向后3步移动,排列变成1 3 4 5 2 6。同样的方式定义向前M步移动。如果排列A能够通过有限向前M步移动和向后M步移动变成排列B,称排列A与排列B M步等价。容易看出这也是等价关系。

      引理1任何一个1N的排列M步等价于1 2 ... N-M...)。括号里是N-M+1N某个排列

证明:如果N=M,这显然成立。

假设N=k时成立,下面证明k+1的情况。

1元素的位置记为i

情况1:假设i=1,显然,余下的元素减1,就变成N=k的境况,得证。

情况2:如果1<i<=M,则元素1前面的元素向后M移动,变为情况1

情况3如果i>M,则元素1有限次向前M步移动,使i1<=i<=M,可变成情况12

从而得证。
M=2时,只有两组等价类。由于移动不改变排列的奇偶性,从而奇排列是一组等价类,偶排列是一组等价类。


考虑N*M拼图
N=M=2,穷举法可证明只有两组等价类。

NM不同时为2时,设N不等于2(如果N等于2M不等于2可颠倒行列讨论)。

只考虑第二行最后一个元素是空元素的情形,因为空元素在其他位置总可以等价某个空元素在第二行最后一个元素的图形。不考虑空元素以之字形方式展开图形,即第一行最后一个数字和第二行倒数第二个数字相连。如:

1

2

4

3

5


3

展开成12453

下面证明两行拼图的交换方式可以实现排列的向前2向后2移动。

要实现元素a向前2步移动,则可顺着展开的方式循环移动拼图,使a在第一行第二列的位置,使空元素在第二行第二列的位置,此时可把元素i可与空元素对换。然后再沿着展开的顺序还原拼图。

例如:3的元素4向前2步移动。可以如下操作,

2

4

5

1


3

4

2


5

1

4

3

5

4

1

2

3

5


6

展开41253。实现了向前2步移动。

使i在第二行第二列的位置,使空元素在第一行第二列的位置可以实现向后2步移动。根据引理1及,两行拼图可以分成两组等价类。

假设M=k图形可以分成两组等价类,下面证明M=k+1

只需要证明任何M=k+1图形总等价于第一行元素为1 2 ... N的某图形即可。

如果这N个元素都在第一行,把空元素移到第二行,从上面的证明可知,交换两个不同的非空元素,图形的奇偶性改变,属于不同的等价类。N大于2,第二行就有两个非空元素可供交换。所以两行图形可以等价与第一行为1 2 ... N的某个图形。

如果1N的某个a元素不在第一行,设它在第i行。把空元素移动到i行,这样第i行和第i-1行可以看成M=2的图形。可以把a移动到第i-1行,并保证第i行和i-1行中1N的元素的行号不增加。有限步移动可以使1N元素全部在第一行。

显然M=k+1图形的等价类数目为2

充分性得证。

      拼图游戏的随机离散中加入定理1的判断可以保证游戏有意义,不会出现无解的情况。

附:     windows控制台下的数字拼图游戏,用dev c++编译通过。


posted on 2007-10-04 12:34 lemene 阅读(2675) 评论(6)  编辑 收藏 引用

评论

# re: 拼图游戏  回复  更多评论   

123456780与123450786显然可以互变,它们的逆序数,0元素行号和列号分别是如何计算的?
2009-03-16 12:01 | 11

# re: 拼图游戏  回复  更多评论   

123456780的逆序数是8,0元素行号、列号分别是3,加起来和是14。
123450786的逆序数是6,0元素行号是2、列号是3,加起来和是15。
这样算对不对?如果不对,应怎样计算?

2009-03-16 12:04 | 11

# re: 拼图游戏  回复  更多评论   

刚才算错了一个地方,123450786的逆序数是6,0元素行号是2、列号是3,加起来和是11。
2009-03-16 12:05 | 11

# re: 拼图游戏[未登录]  回复  更多评论   

123456780 的逆序数8,行号3 列号3 相加 14
123450786 的逆序数7,行号2 列号3 相加 14

123450786的逆序数为5+2,即0和6的逆序数。
2009-03-18 14:31 | lemene

# re: 拼图游戏  回复  更多评论   

为什么N=M就显然成立呢?
12345和12354好像并不2步等价啊。

我复制粘贴了你的文章到我的博客,当然说明了出处。

你这篇文章写的很好,受益匪浅。

看这最后一次评论都是09年的,我这个评论也不知道你能不能看得到
2011-09-05 21:25 | godcupid

# re: 拼图游戏[未登录]  回复  更多评论   

N=M是一种平凡情况,这时N-M=0,所以N-M+1..N就是1..N,显然它们等价.@godcupid
2011-09-21 21:23 | lemene

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理