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个结论:下面我们就要开始根据这个算法生成可解的拼图游戏了。


目录
相关文章
|
7天前
|
编解码 数据库 Android开发
安卓应用开发:打造高效用户界面的五大技巧
【5月更文挑战第18天】在竞争激烈的应用市场中,一个流畅且直观的用户界面(UI)对于安卓应用的成功至关重要。本文将探讨五种提升安卓应用用户界面性能的技巧,包括合理布局设计、优化资源使用、利用硬件加速、内存管理以及响应式编程。通过这些方法,开发者可以创建出既美观又高效的应用体验,从而吸引和保留用户。
|
23小时前
|
数据处理 API Android开发
安卓应用开发:构建一个高效的通知管理系统
【5月更文挑战第25天】在移动操作系统中,通知管理是用户体验的核心组成部分。特别是对于安卓设备,由于其开放性和多样性,有效的通知管理系统显得尤为重要。本文将详细介绍如何在安卓平台上构建一个高效、用户友好的通知管理系统。我们将从通知渠道的管理、用户自定义设置以及后台数据处理等方面展开讨论,并提供实用的代码示例和最佳实践建议。
|
2天前
|
缓存 监控 Java
安卓应用开发中的内存优化策略
【5月更文挑战第24天】 在移动设备上,资源的有限性要求开发者对应用程序进行细致入微的性能优化。特别是对于安卓平台,由于设备的多样性和碎片化问题,内存管理成为提升应用性能、用户体验和电池寿命的关键因素。本文将探讨针对安卓开发的内存优化技巧,从避免内存溢出、减少内存占用到提高内存回收效率等方面展开讨论,旨在为开发者提供实用的内存优化策略,以改善应用的运行效率和稳定性。
|
6天前
|
搜索推荐 API Android开发
安卓应用开发:打造高效通知管理系统
【5月更文挑战第20天】在移动设备中,通知管理是用户体验的关键部分。一个高效的通知系统不仅能够及时传达重要信息,还能避免用户感到不必要的干扰。本文将深入探讨如何在安卓平台上开发一个高效的通知管理系统,包括通知的设计、发送策略以及用户的个性化设置。通过分析安卓系统的通知机制和最新的API特性,我们将提供一个实用的开发指南,帮助开发者创建更加智能和用户友好的通知体验。
|
9天前
|
JSON Android开发 数据格式
Android框架-Google官方Gson解析,android开发实验报告总结
Android框架-Google官方Gson解析,android开发实验报告总结
|
9天前
|
前端开发 Android开发
Android架构组件JetPack之DataBinding玩转MVVM开发实战(四)
Android架构组件JetPack之DataBinding玩转MVVM开发实战(四)
Android架构组件JetPack之DataBinding玩转MVVM开发实战(四)
|
9天前
|
安全 Linux Android开发
Android最强保活黑科技的最强技术实现,2024年最新阿里资深Android开发带你搞懂Framework
Android最强保活黑科技的最强技术实现,2024年最新阿里资深Android开发带你搞懂Framework
Android最强保活黑科技的最强技术实现,2024年最新阿里资深Android开发带你搞懂Framework
|
9天前
|
算法 前端开发 Android开发
Android文字基线Baseline算法的使用讲解,Android开发面试题
Android文字基线Baseline算法的使用讲解,Android开发面试题
Android文字基线Baseline算法的使用讲解,Android开发面试题
|
9天前
|
缓存 Android开发
Android插件化——高手必备的Hook技术,零基础开发android
Android插件化——高手必备的Hook技术,零基础开发android
|
9天前
|
Android开发
Android高级开发面试题以及笞案整理,实战解析
Android高级开发面试题以及笞案整理,实战解析