Android拼图游戏开发全纪录2
今天我们主要来讨论下拼图游戏的可行性解的问题，其实不要小看拼图游戏，他其实是人工智能算法中很著名的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个结论：下面我们就要开始根据这个算法生成可解的拼图游戏了。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
