http://topic.csdn.net/t/20010508/19/115126.html

一个简单的游戏算法？谁知道？

比如拼图游戏：
给出一个随机的布局（例如）
|06|14|03|13|
|05|01|08|15|
|11|10|09|12|
|04|02| |07|
空的一个是可以移动的地方，相邻的方格
可以移动到空格，每次移动记作一步，试
问对于任何随机布局，一定能够得到下面
的布局吗？怎样才能用最少的步数完成？
|01|02|03|04|
|05|06|07|08|
|09|10|11|12|
|13|14|15| |
我想了几天也没有头绪，诸位大虾帮帮忙，
一起解决这个问题吧！100分送上。 问题点数：100、回复次数：21Top

1 楼NowCan（城市浪人） 回复于 2001-05-08 20:32:00 得分 0

有一点，对任何随机布局，不一定都有解，下图就不可能。
|01|02|03|04|
|05|06|07|08|
|09|10|11|12|
|13|15|14| |
Top

2 楼NowCan（城市浪人） 回复于 2001-05-08 20:33:00 得分 0

算法我好像看过，在《电脑爱好者》上的“擂台赛”。Top

3 楼fish_autumn（Autumn） 回复于 2001-05-08 20:40:00 得分 0

按广度优先，可推出结果（可能无解)Top

4 楼redbit（） 回复于 2001-05-08 21:10:00 得分 10

对有解的情况,可以以3*2六个格子为单位(其中包含空格),
这样通过一定的步骤可以转换到希望的状态:
如:
¦02¦03¦04¦
¦05¦01¦ ¦
可以到
¦01¦02¦03¦
¦04¦05¦ ¦
当然竖着的2*3的单位也可以。这样通过一定步骤，应该能求得一个解，不过十有八九不是最优。Top

5 楼g9yuayon（渡渡鸟） 回复于 2001-05-08 22:57:00 得分 10

http://www.csdn.net/expert/topic/101/101042.shtmTop

6 楼Robin_Hood_POT（令狐冲） 回复于 2001-05-09 12:19:00 得分 0

最有解难道没有办法获得吗？
另外，大家既然说了随机的布局可能是无解的情况，那么怎样判断是否有解？怎样让随机布局避免无解的情况？
多谢大家的参与，虽然大家给出了一些解法和思路，但是这一方面有没有系统的理论研究呢？Top

7 楼fish_autumn（Autumn） 回复于 2001-05-09 15:49:00 得分 0

最后正好有两个板位置相反即为无解Top

8 楼NowCan（城市浪人） 回复于 2001-05-09 16:08:00 得分 0

要避免随机布局无解可以从最终的布局倒回去，随机移动。Top

9 楼Robin_Hood_POT（令狐冲） 回复于 2001-05-09 18:00:00 得分 0

多谢NowCan、fish_autumn
不过我希望从理论上本质上搞懂，这些解法我也想到过，总觉得不是最好的。Top

10 楼duz（） 回复于 2001-05-09 22:53:00 得分 10

要从理论是搞懂，你需要学一下群论。这其实是一个置换群中所有偶置换形成的子群。Top

11 楼hyqryq（不知道叫什么好） 回复于 2001-05-10 13:01:00 得分 0

典型的A*算法Top

12 楼NowCan（城市浪人） 回复于 2001-05-10 17:35:00 得分 0

找到了，在《电脑爱好者》2000年第4期。用的是A*算法。Top

13 楼Robin_Hood_POT（令狐冲） 回复于 2001-05-10 18:20:00 得分 0

to duz:
是离散数学中的内容吗？

to hyqryq, NowCan：
拜托能不能把A*算法的原理贴出来，或者告诉我什么书上找得到？
一向以为《电脑爱好者》都很弱智的，怎么会讨论这个问题？Top

14 楼Robin_Hood_POT（令狐冲） 回复于 2001-05-11 18:42:00 得分 0

大家怎么没有热情了？Top

15 楼xhy（morph） 回复于 2001-05-11 20:43:00 得分 10

《人工智能》中关于搜索的。
A*,在里面有很详细的讲解。Top

16 楼yuangege（yuange） 回复于 2001-05-14 12:57:00 得分 50

用数论简单的就可以解决。上面的说了以3*2为单位，你可以证明最终要解决最后一个3*2的方格的问题。显然3*2的方格随机分布的可以很简单移动一个方格到自己位置，所以就剩下后面两个，所以就两种情况。下面的证明也说明了这两种情况是不能用这种移动方法互换的。
上面也有人说了群论的办法，但群论毕竟大多人不能理解。用一些简单的数论知识大家一看就能明白的。这个就是数论的反序，什么是反序呢？简单说来就是一个数列，大的数在小的数前面的个数。比如数列1、2、3显然没有大的数在小的数前面，这就是说这个数列的反序是0，数列3、2、1的反序就是3（3在2前面、3在1前面、2在1前面）。我们用反序来证明，主要是反序有个好的奇偶特性。这个很简单的就能证明任意交换一个数列的两个数的位置，那么他们的反序的奇偶交换了。这个数学证明方法就不用在这证明了，证明也很简单。这种评图游戏我们把空白也标上数字，是不是就是一个数列？没回移动是不是就是交换了两个数的位置？这个在数学上就是叫转化成数学问题或者叫建模什么的。为了方便也为了好计算，我们把初始的情况空白固定在它自己的位置。我们来考虑如果成功，那么最终空白移动的次数呢？是不是一定是偶数？这不用再证明了吧？而空白移动的次数就是我们这种拼图游戏交换两个数位置的次数。这是不是就简单的就证明了要能移动到另一种情况，那么必须是它们的反序同奇偶。（必要条件）
奇偶有两种情况，也就是说明了一定至少有两种情况，上面根据3*2也证明了最多两种情况，那么也就证明了一定是两种情况。也证明了只要两种情况的反序同奇偶就一定能移动成功。（充分条件）。

下面就是我98年在海信电视上实现的拼图游戏的相关代码，此图是4*5的，编译后代码只有1K多点。我的俄罗斯方块编译代码也只有2.2K。



/*------------------------------;
; GAME START ;
;------------------------------*/
void p_game_start(){
game2_begin=0;
game_begin = 1;
game_success = 0;
rand1+=g_time_base;
for(i = 0;i <= 18;++i){
get_rand();
/* 获得随机数，返回在BC */
B=0;
C=BC%19;
g_game_num[i]=C+1 ;
for(j=0;j<i;++j){
if(g_game_num[i]==g_game_num[j]){
/* 数不要相同 */
C=g_game_num[i];
B=0;
C=BC%19;
C+=1;
g_game_num[i]=C;
j=-1;
}
}
}
g_game_num[19] = 20;
/* 这是空白，位置固定 */
/* 上面为随机布局代码 */

g_game_blank = 19;
/* 空白位置变量 */


/* 下面是求反序代码 */
game_odd=0;
/* 反序初始化0 */
for(i=0;i<20;++i){
for(j=i+1;j<20;++j){
if(g_game_num[i]>g_game_num[j]) CPL(game_odd);
/* 大树在前不？ CPL是求反的代码，game_odd是布尔变量 */
}
}
if (game_odd==1) {
/* 反序不同 */
B=g_game_num[0];
g_game_num[0]=g_game_num[1];
g_game_num[1]=B;
/* 不用重新布局 */
/* 由前面的证明，我们只需要任意交换两个数的位置就可以了 */
}
osd_req = C_OSD_GAME;
g_dsp_timer = C_TIMER_STOP;
A=cDISPLAY;
CALLV(STA_TSK);
/* 任务调度 */
return;
}
Top

17 楼yuangege（yuange） 回复于 2001-05-14 13:11:00 得分 0

有点小失误。：（
用数论简单的就可以解决。上面的说了以3*2为单位，你可以证明最终要解决最后一个3*2的方格的问题。3*2的方格可以轻易证明可以移动顶上1*2的位置对，那就剩2*2。显然2*2的方格随机分布的可以很简单移动一个方格到自己位置，再空格能到自己位置，所以就剩下后面两个，所以就两种情况。下面的证明也说明了这两种情况是不能用这种移动方法互换的。

Top

18 楼seedundersnow（想当英雄的懦夫） 回复于 2001-05-14 17:39:00 得分 0

yuangege(yuange):

小心老板k你!Top

19 楼IceWall（谁敢打我） 回复于 2001-05-15 12:15:00 得分 10

我有一个简单的类拟的拼图游戏，谁有兴趣可随源码一同赠上。faqiangzhang@china.comTop

20 楼Robin_Hood_POT（令狐冲） 回复于 2001-05-16 12:18:00 得分 0

to IceWall:
你的拼图游戏有电脑自己完成游戏的功能没有？
如果有我想要一个。Top

21 楼pet（pet） 回复于 2001-05-16 13:22:00 得分 0

To IceWall(fq):我有兴趣，能否给我一份(拼图游戏的源码)，谢谢啦！
lang12@netease.com