拼图游戏无解可还原性算法分析

拼图游戏无解可还原性算法分析

拼图游戏无解可还原性算法分析

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

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的判断可以保证游戏有意义,不会出现无解的情况。

转载至:http://blog.sina.com.cn/s/blog_5396eb5301017qv0.html