开发者社区> eclipse_xu> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

Android拼图游戏开发全纪录2

简介: 今天我们主要来讨论下拼图游戏的可行性解的问题,其实不要小看拼图游戏,他其实是人工智能算法中很著名的15puzzle问题,网上已经有很多关于这个问题的解释,我就做个搬运工好了。 随机生成的15puzzle大约有%50是无解的,本文将就随机生成的谜题的可解性加以讨论。
+关注继续查看

今天我们主要来讨论下拼图游戏的可行性解的问题,其实不要小看拼图游戏,他其实是人工智能算法中很著名的15puzzle问题,网上已经有很多关于这个问题的解释,我就做个搬运工好了。

随机生成的15puzzle大约有%50是无解的,本文将就随机生成的谜题的可解性加以讨论。

设有如下矩阵:

12 1 10 2

7 11 4 14

5 x 9 15

8 13 6 3

将其排成水平的,有:12,1,10,2,7,11,4,14,5,X,9,15,8,13,6,3。并记该序列为A

定义:”倒置变量值“ T,Ti表示序列A中位于第i位之后比Ai小的元素的个数

也就是说上面的序列的倒置变量值分别是:11,0,8,0,4,6,1,6,1,3,4,2,2,1。求和,得到总的Tsum = 49。

那么有如下几个原则来判断当前问题是否有解:

设:问题宽度为W。

设:问题的倒置变量和为T。

一、对于一个W为奇数的问题来说,任何合法的移动都不会改变其"倒置变量值"的奇偶性。

证明:>>水平移动式不会改变问题的T。

>>垂直移动,意味值blank跨越了(W-1)个方格,由于问题宽度W是奇数的,那么(W-1)必定为偶数,再设这W-1个数中有n个数大于当前移动数,则有(W-1-n)个数小于当前移动数,那么移动后,带来的T的改变是:(W-1-n)-n=W-1-2n,因为W-1是偶数,则W-1-2n也必为偶数,说明问题的T的奇偶性不变。

二、当W为偶数时,有以下公式:(T是偶数) == (空格位于从矩阵底部往上数的奇数行中)

证明:>>水平移动式不会改变问题的T。

>>垂直移动,意味值blank跨越了(W-1)个方格,由于问题宽度W是偶数的,那么(W-1)必定为奇数,再设这W-1个数中有n个数大于当前移动数,则有(W-1-n)个数小于当前移动数,那么移动后,带来的T的改变是:(W-1-n)-n=W-1-2n,因为W-1是奇数,则W-1-2n也必为奇数,说明问题的T的奇偶性会交替变化,但是空格位置也在交替变化,这种变化也符合上面定义的公式。

OK,有了上面两个定理,我们可以推论出一下可行解原则:

1、如果问题宽度是奇数的,那么每个可解的问题所定义的T必须是偶数的。

2、如果问题宽度是偶数的,那么当空格位于从下往上数的奇数行中时,问题的T必须是偶数的;当空格位于从下往上数的偶数行中时,问题的T必须是奇数的。


---------------------------------------------------------------------------好 了---------------------------------------------------------------------------

我们需要的就是这2个结论:下面我们就要开始根据这个算法生成可解的拼图游戏了。


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
《Android开发秘籍(第2版)》——导读
本节书摘来自异步社区《Android开发秘籍(第2版)》一书中的目录,作者 【美】Ronan Schwarz , Phil Dutson , James Steele , Nelson To,更多章节内容可以访问云栖社区“异步社区”公众号查看
1323 0
+关注
eclipse_xu
《Android群英传》作者
262
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载