>>拼图
先来玩一玩吧
html版(鼠标点一点吧,发现无解或其它bug截图发给作者)
flash版(鼠标点一点吧,发现无解或其它bug截图发给作者)
>>原理
关于游戏逻辑,不同的人实现起来不一样,这里不描述,需要的话可以下载源码参考,下面只说一下游戏实现中的难点。
拼图游戏的难点在于图片的打乱,因为图片随机打乱后,拼图不一定有解。
如:
无论你怎么尝试,都不可能拼成:
如何才能保证拼图有解呢?
最开始,作者是这么做的:既然拼图还原是通过空位和相邻的图块儿交换位置实现的,那么如果通过空位和旁边的图块儿交换来打乱,便可以保证拼图一定是有解的。这个方法是可行的,只是效果不是很好,打乱之后不够乱,打乱操作的步数比较多。
后来发现已经有很多人研究过拼图有解的理论,用到了逆序数,有兴趣可以自行百度。
下面是作者的总结:
- 拼图只有两种状态,有解或无解。
- 判断有解方法: 逆序数奇偶性。
- 逆序数:将二维数组按行展开(也可以按其它方法展开,显示的时候还要转成数组);形成的序列的逆序数(自行百度逆序数)。
- 定理:将空格从序列中移除,剩余序列的(逆序数+空格行号+空格列号)的奇偶性相同,则可以相互转换。
- 具体实现思路:先固定空格的位置,这样我们就只需要考虑展开序列的逆序数;由于:任意交换序列中的两个不相同的元素,序列逆序数的奇偶性改变;所以只要交换偶数次,奇偶性必定不变。
- 改变空格的位置:上面的思路实现了数组的打乱,然后可以随机生成一个位置,让空格通过和相邻元素交换位置,移动到目标位置。
-
礼成
>>举例说明
哈哈,表述起来太难了,写了半天,连我自己都看不明白,还是举个例子吧
如上面,一个3*3的拼图,打乱之前是这样的,总共有9个方块儿,方块儿9被拿掉了;方块9的位置不动,从其余8个方块儿中随机选出两个,交换位置,交换偶数次即可。
比如我们让方块儿1和方块儿2交换,然后让方块儿7和方块儿8交换,经过两次交换,按照上面的理论,拼图有解。如下图
再让方块儿1和方块儿4交换,然后让方块儿7和方块儿5交换,又经过两次交换,按照上面的理论,拼图有解。如下图
上面两个不能点着玩,如果不信,自己拿纸做几个小方块儿验证吧。
验证完了,继续往下看。经过任意偶数次交换之后,拼图都有解。而且随便交换几次之后就已经足够乱了。还有一个问题,这样无论交换多少次,方块儿9的位置都没动,如果我想让9的位置也随机,怎么办呢?哈哈,很简单,随便选一个位置,然后让9和旁边的方块儿交换位置,再交换位置...,怎么样,换过去了吧,而且肯定还是有解的。
就到这里了,如果有问题,请联系作者。