在前面,有说用各种搜索方法(后面还将给出网友整理的八数码问题的十重境界) 来解决8 PUZZLE和15 PUZZLE问题。实际上,由于拼图游戏的种类繁多,我们可以延拓到两种比较特殊的类型:(1)M*N PUZZLE(2)N PUZZLE,(1)中的M*N当然是任意的正整数,而(2)中的N,这里指代的是一个正整数的平方和减一所得到的值。
如图所示,这是一个8*5数码的问题,当然,用之前的范式就不好办了。但是,之前也有说明十五数码的唯一解定理,由此,我们可以提出N数码问题的唯一解。
N数码问题的唯一解
逆序对?空白(blank)起始时所在的点的行距距离目标点的欧几里得距离(dis)?这是在N*N-1数码问题中当N为偶数的时候能成立,当N为奇数的 时候,条件需要更弱一些,也就是说,当N为奇数的时候,在逆序和保持奇偶性相同的情况下,就能保证问题是唯一可解的。基于这一点(定理的证明可以详见相关 资料,或者按照15数码解的存在性定理的证明方法给出证明),这里给出判定N数码问题是否有唯一解的判定程序(HDOJ 3600):
1 #include<iostream>
2 3 #include<algorithm>
4 5 // 利用string库来读入一个谜题 6 7 #include<
string>
8 9 using namespace std;
10 11 12 13 // 假设问题的规模(N的最大值不超过300) 14 15 const int N=
300+
10;
16 17 18 19 int s[N*N],g[N*N];
20 21 22 23 // 利用宏定义一个函数 24 25 #define _cp(a,b) ((a)<=(b))
26 27 28 29 int _tmp[N*N];
30 31 32 33 // 考察这个问题对应的所有状态的逆序数之和 34 35 int solve(
int n,
int *a)
36 37 {
38 39 int l=n>>
1;
40 41 int i,j,r=n-
1;
42 43 // 如下是求两个状态逆序对的差值,不过,这段代码确实有些乱,暂时没有弄明白 44 45 int ret=(r>
1 ? (solve(l,a)+solve(r,a+l)):
0);
46 47 for(i=j=
0;i<=l;_tmp[i+j]=a[i],i++)
48 49 {
50 51 for(ret+=j;j<r&&(i==l||!_cp(a[i],a[l+j]));_tmp[i+j]=a[l+j],j++);
52 53 }
54 55 memcpy(a,_tmp,
sizeof(
int)*n);
56 57 return ret;
58 59 }
60 61 62 63 int main()
64 65 {
66 67 int n;
68 69 // 每次读入一个问题前,先读入问题的规模 70 71 while(scanf(
" %d ",&n)==
1&&n)
72 73 {
74 75 int num=
0;
76 77 bool flag=
true;
78 79 // 读入整个问题 80 81 for(
int i=
0;i<n*n;i++)
82 83 {
84 85 scanf(
" %d ",&g[i]);
86 87 // 这里可以找到那个空白方块的位置 88 89 if(flag&&g[i]!=
0) num++;
90 91 if(g[i]==
0) flag=
false;
92 93 }
94 95 int temp=solve(n*n,g);
96 97 // 不考虑空白位置的逆序数 98 99 temp-=num;
100 101 // 如果n为偶数的话,需要加上空格所在的行距离目标空格的行的dis距离 102 103 if(!(n&
1))
104 105 {
106 107 temp+=(n-
1-(num/n));
108 109 }
110 111 // 如果奇偶相异,则不可达,否则,为可达 112 113 if(temp&
1) puts(
" NO ");
114 115 else puts(
" YES ");
116 117 }
118 119 return 0;
120 121 }
N*M问题的唯一解
在POJ的2893中,原问题被更进一步地扩展,但是,原理还是相同的,而且,我们可以得到更为本质化的结论:当N为完全平方模型的时候,似乎是由N来决 定原理的,而实际上,如果问题被延拓为N*M,我们可以发现,一个更为本质的结论,原问题的可解性实际上是由列数M来判定的,这样,由特殊推广到了一般, 证明如下(这里我们可以看出,行和列都起到了一定的作用,列的作用确定了空白方块是否要考虑,而在空白方块的位置需要考虑的情况下,行的作用又让它必须了解到底要增加多少(也就是行增量,欧几里得距离)):
假设这个矩阵有3列,且逆序对总数设为N(这里不失一般性地假设a1<a2)
(1)首先,对于可左右移动的数字,它左右移动是不会对逆序对总数产生影响;
(2)若数字a0上下移动的话会移到它之前或之后的两个数字的位置,假设是向上移动,且这两个数字为a1,a2:(3个数字肯定是不同数字)
若a0 < a1 < a2,则新的逆序对总数为N-2,
若a1 < a0 < a2, 则新的逆序对总数为N - 1 + 1 = N,
若a1 < a2 < a0, 则新的逆序对总数为N+2,
由此可见,数字的移动是不影响矩阵逆序对总数的奇偶性的,推广到列数为奇数的情况也是一样。那么若判定初始矩阵与目标矩阵的逆序对总数是否相同,即可判定问题是否可解,若同则可解,否则不可解。
若列数为偶数的话,数字左右移动同理不影响,但是上下移动一次会改变一次逆序对总数的奇偶性,所以对于这种情况,我们可以计算初始矩阵0的位置到目标矩阵 0的位置的差值 S ,这样可以判定奇偶性被如何改变了。由于0最终是要到目标位置的,所以无论0在工程中如何移动,逆序对的奇偶性只和S有关。那有些人可能会想,我们怎么只 考虑0的上下移动,不考虑其他数字的上下移动,我们可以这样想,无论那个数字要移动都是要和0交换位置,也就是说无论那个数字的移动都是0的移动,所以在 这里我们就只分析0的上下移动即可。
这里可以采用归并排序来解决逆序对的问题,代码如下(这里换一种方法,利用归并排序来求逆序对的总数之和):
1 #include<iostream>
2 3 4 5 using namespace std;
6 7 8 9 #define MAXN 1000005
10 11 12 13 int cnt;
14 15 int a[MAXN],c[MAXN];
16 17 18 19 // 利用归并排序来求逆序数 20 21 void MergeSort(
int l,
int r)
22 23 {
24 25 int mid,i,j,tmp;
26 27 // 直到左右缝合为止 28 29 if(r>l+
1)
30 31 {
32 33 mid=(l+r)/
2;
34 35 MergeSort(l,mid);
36 37 MergeSort(mid,r);
38 39 tmp=l;
40 41 // 找到所有的逆序对,这一段也暂时不是很明白 42 43 for(i=l,j=mid;i<mid&&j<r;)
44 45 {
46 47 if(a[i]>a[j])
48 49 {
50 51 c[tmp++]=a[j++];
52 53 cnt+=mid-i;
54 55 }
56 57 else c[tmp++]=a[i++];
58 59 }
60 61 while(j<r) c[tmp++]=a[j++];
62 63 while(i<mid) c[tmp++]=a[i++];
64 65 for(i=l;i<r;++i) a[i]=c[i];
66 67 }
68 69 }
70 71 72 73 int main()
74 75 {
76 77 int n,m,pl;
78 79 // 读入问题的规模,以(0,0)结尾 80 81 while(scanf(
" %d%d ",&n,&m)!=EOF)
82 83 {
84 85 if(n ==
0 || m ==
0)
break;
86 87 // 这个用来标记逆序对的和 88 89 cnt =
0;
90 91 // 这个用来标明当前处理的方块的位置 92 93 pl =
0;
94 95 int x,loc0;
96 97 for(
int i =
0; i < n*m; i++)
98 99 {
100 101 scanf(
" %d ",&a[pl]);
102 103 if(a[pl] ==
0)
104 105 {
106 107 x = pl/m;
108 109 loc0 = pl;
110 111 }
112 113 pl++;
114 115 }
116 117 MergeSort(
0,pl);
118 119 // 扣除0的逆序数 120 121 cnt -= loc0;
122 123 int step =
0;
124 125 // 若列数为奇数,则数字的上下左右移动都不影响最终逆序对的总数 126 127 if(m%
2 ==
1)
128 129 step =
0;
130 131 // 若列数为偶数,左右移动不影响,但上下移动一次,会改变一次逆序对总数的奇偶性 132 133 else 134 135 step = n -
1 - x;
136 137 // 初始,结束状态的逆序对总数奇偶性一致,则问题可解 138 139 if(step%
2 == cnt %
2)
140 141 printf(
" YES\n ");
142 143 else 144 145 printf(
" NO\n ");
146 147 }
148 149 return 0;
150 151 }
进一步推广,魔方,七巧板,华容道……
如图,这是一个魔方,是由N*N*N个小立方体组成的。我们这里随意拿走一个小立方体,并假设整个结构没有被破坏。那么,这是一次更普遍的飞跃,由二维空间上升到了三维空间。但是,其解的唯一性定律还适用嘛?答案是肯定的,证明如下:
魔方数码问题的解的唯一性定理
考虑左右移动空格,逆序不变;同一层上下移动空格,跨过N-1个格子;上下层移动空格,跨过N^2-1个格子。
当N为奇数时,N-1和N^2-1均为偶数,也就是任意移动空格逆序奇偶性不变。那么逆序奇偶性相同的两个状态可相互到达。
当N为偶数时,N-1和N^2-1均为奇数,也就是令空格位置到目标状态空格位置的y z方向的距离之和,称为空格距离。若空格距离为偶数,两个逆序奇偶性相同的状态可相互到达;若空格距离为奇数,两个逆序奇偶性不同的状态可相互到达。
七巧板
更为一般性的拓展,我们可以考虑到其图形不一定是正方形或者是正方体,比如,我们国家民间的七巧板游戏,这些方块的形状都不是正方形,甚至彼此都不一定相 同,但是,经过一定的组合之后,却构成了一个比较好玩的游戏。但是,这个游戏并不是通过方块的滑动来实现的,而是放置,所以,在这一点上看,软件的实现比 较简单。
其实现并不复杂,只要给出固定的解,每一次比对是否将图形安装到固定的位置就可以了,如图所示,这是其中的一款游戏:
华容道
更复杂的游戏,比如华容道的AI,就要考虑很多因素,因为,不同的方块形状是不一样的,不过,索性还有一定的规则可以追寻,其实现目前很多,我用的是一个中学老师的AI版本(他写成了一篇论文)。我之后会单独以一个Round来放送的。
---恢复内容结束---