分享
 
 
 

八数码问题完全版-是否可解判断及求解

王朝other·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

/*

八数码问题

有一个3*3的棋盘,其中有0-8 9个数字,0表示空格,其他的数字可以和0交换位置。求由初始状态

1 2 3

4 5 6

7 8 0

到达目标状态步数最少的解。

其典型算法是广度优先搜索,具体算法是:

struct 类名 m_ar[可能结点数];

int h,r

main()

{

h=0;r=1;

while ((h<r)&&(r<可能结点数))

{

if (判断每一种可能性,如果某一种操作符合要求)

{

将m_ar[h]操作后记录于m_ar[r];

如果和目标一样,输出结果并中止程序;

r=r+1;

}

h=h+1;

}

表示没有结果。

}

***********************************

是否可解的判断

我知道什么样的情况有解,什么情况没解.

函数f(s)表示s前比s小的数字的数目.

例如:

|1 3 4|

|2 8 6|

|5 7 |

表示成:

|1 3 4|2 8 6|5 7 X| 则f(7)=6, f(5)=4,f(6)=4,f(8)=4,f(2)=1,

f(4)=2,f(3)=1,f(1)=0

当f(a8)+f(a7)+……+f(a1)为偶数时才能重排成

所以嘛,上面那个有解的.

下面我就来证明一下.

设任意一种情况:

|a1 a2 a3|

|a4 a5 a6|

|a7 a8 X | (X表示空格)

将之放在一行上: |a1 a2 a3|a4 a5 a6|a7 a8 X |

数字的上下移动可以相对于是空格的上下移动.

所以我们只要讨论X的移动了:

假设函数f(s)表示s前比s小的数字的数目.

例如:|1 3 4|2 8 6|5 7 X| 则f(7)=6, f(5)=4, f(8)=4,……

对于X在同一行中的移动,f(a8)+f(a7)+……+f(a1)大小不变(*1)

如:|a1 a2 a3|a4 a5 a6|a7 a8 X |=>|a1 a2 a3|a4 a5 a6|a7 X a8|

对于X在列中移动是,我们不妨设X与a6对换(即a6下移一格)

则数列变为|a1 a2 a3|a4 a5 X|a7 a8 a6|,可能引起变化的f(s)只有f(a6),f(a7),f(a8)

讨论:有4种情况1) a6<a7, a6<a8

f(a8) 减小1

f(a7) 减小1

f(a6) 不变

所以f(a8)+f(a7)+……+f(a1)奇偶性不变.

2) a6<a7, a6>a8

f(a8) 不变

f(a7) 减小1

f(a6) 增大1

所以f(a8)+f(a7)+……+f(a1)奇偶性不变.

3) a6>a7, a6>a8

f(a8) 不变

f(a7) 不变

f(a6) 增大2

所以f(a8)+f(a7)+……+f(a1)奇偶性不变.

3) a6>a7, a6<a8

f(a8) 减小1

f(a7) 不变

f(a6) 增大1

所以f(a8)+f(a7)+……+f(a1)奇偶性不变.

这样,再将a3下移一格则|a1 a2 a3|a4 a5 X|a7 a8 a6|=>|a1 a2 X|a4 a5 a3|a7 a8 a6|

则同样,对可能变化的f(a3),f(a4),f(a5)讨论,情况一上面完全一样。

其它情况都如此:

如:|a1 X a3|a4 a5 a6|a7 a8 a2|=>|a1 a5 a3|a4 X a6|a7 a8 a2|

就f(a3),f(a4),f(a5)变化.

结论:因为对于|1 2 3|4 5 6| 7 8 X|, f(8)+f(7)+……+f(1)=28, 是偶数,

所以当f(a8)+f(a7)+……+f(a1)为偶数时才能重排成|1 2 3|4 5 6| 7 8 X|成功.

*/

#include <stdio.h>

#include <conio.h>

#include <string.h>

typedef unsigned long long UINT64;

typedef struct

{

char x; //位置x和位置y上的数字换位

char y; //其中x是0所在的位置

} EP_MOVE;

#define SIZE 3 //8数码问题,理论上本程序也可解决15数码问题,

#define NUM SIZE * SIZE //但move_gen需要做很多修改,输入初始和结束状态的部分和check_input也要修改

#define MAX_NODE 1000000

#define MAX_DEP 100

#define XCHG(a, b) { a=a + b; b=a - b; a=a - b; }

#define TRANS(a, b) { long iii; (b)=0; for(iii=0; iii < NUM; iii++) (b)=((b) << 4) + a[iii]; } //将数组a转换为一个64位的整数b

#define RTRANS(a, b) { long iii; UINT64 ttt=(a); for(iii=NUM - 1; iii >= 0; iii--) { b[iii]=ttt & 0xf; ttt>>=4; } } //将一个64位整数a转换为数组b

//

typedef struct EP_NODE_Tag

{

UINT64 v; //保存状态,每个数字占4个二进制位,可解决16数码问题

struct EP_NODE_Tag *prev; //父节点

struct EP_NODE_Tag *small, *big;

} EP_NODE;

EP_NODE m_ar[MAX_NODE];

EP_NODE *m_root;

long m_depth; //搜索深度

EP_NODE m_out[MAX_DEP]; //输出路径

//

long move_gen(EP_NODE *node, EP_MOVE *move)

{

long pz; //0的位置

UINT64 t=0xf;

for(pz=NUM - 1; pz >= 0; pz--)

{

if((node->v & t) == 0)

{

break; //找到0的位置

}

t<<=4;

}

switch(pz)

{

case 0:

move[0].x=0;

move[0].y=1;

move[1].x=0;

move[1].y=3;

return 2;

case 1:

move[0].x=1;

move[0].y=0;

move[1].x=1;

move[1].y=2;

move[2].x=1;

move[2].y=4;

return 3;

case 2:

move[0].x=2;

move[0].y=1;

move[1].x=2;

move[1].y=5;

return 2;

case 3:

move[0].x=3;

move[0].y=0;

move[1].x=3;

move[1].y=6;

move[2].x=3;

move[2].y=4;

return 3;

case 4:

move[0].x=4;

move[0].y=1;

move[1].x=4;

move[1].y=3;

move[2].x=4;

move[2].y=5;

move[3].x=4;

move[3].y=7;

return 4;

case 5:

move[0].x=5;

move[0].y=2;

move[1].x=5;

move[1].y=4;

move[2].x=5;

move[2].y=8;

return 3;

case 6:

move[0].x=6;

move[0].y=3;

move[1].x=6;

move[1].y=7;

return 2;

case 7:

move[0].x=7;

move[0].y=6;

move[1].x=7;

move[1].y=4;

move[2].x=7;

move[2].y=8;

return 3;

case 8:

move[0].x=8;

move[0].y=5;

move[1].x=8;

move[1].y=7;

return 2;

}

return 0;

}

/* */

long move(EP_NODE *n1, EP_MOVE *mv, EP_NODE *n2) //走一步,返回走一步后的结果

{

char ss[NUM];

RTRANS(n1->v, ss);

XCHG(ss[mv->x], ss[mv->y]);

TRANS(ss, n2->v);

return 0;

}

/* */

long add_node(EP_NODE *node, long r)

{

EP_NODE *p=m_root;

EP_NODE *q;

while(p)

{

q=p;

if(p->v == node->v)

return 0;

else if(node->v > p->v)

p=p->big;

else if(node->v < p->v)

p=p->small;

}

m_ar[r].v=node->v;

m_ar[r].prev=node->prev;

m_ar[r].small=NULL;

m_ar[r].big=NULL;

if(node->v > q->v)

{

q->big= &m_ar[r];

}

else if(node->v < q->v)

{

q->small= &m_ar[r];

}

return 1;

}

/*

得到节点所在深度

*/

long get_node_depth(EP_NODE *node)

{

long d=0;

while(node->prev)

{

d++;

node=node->prev;

}

return d;

}

/*

返回值:成功-返回搜索节点数,节点数不够-(-1),无解-(-2)

*/

long bfs_search(char *begin, char *end)

{

long h=0, r=1, c, i, j;

EP_NODE l_end, node, *pnode;

EP_MOVE mv[4]; //每个局面最多4种走法

TRANS(begin, m_ar[0].v);

TRANS(end, l_end.v);

m_ar[0].prev=NULL;

m_root=m_ar;

m_root->small=NULL;

m_root->big=NULL;

while((h < r) && (r < MAX_NODE - 4))

{

c=move_gen(&m_ar[h], mv);

for(i=0; i < c; i++)

{

move(&m_ar[h], &mv[i], &node);

node.prev= &m_ar[h];

if(node.v == l_end.v)

{

pnode= &node;

j=0;

while(pnode->prev)

{

m_out[j]=*pnode;

j++;

pnode=pnode->prev;

}

m_depth=j;

return r;

}

if(add_node(&node, r)) r++; //只能对历史节点中没有的新节点搜索,否则会出现环

}

h++;

printf("\rSearch...%9d/%d @ %d", h, r, get_node_depth(&m_ar[h]));

}

if(h == r)

{

return -2;

}

else

{

return -1;

}

}

/* */

long check_input(char *s, char a, long r)

{

long i;

for(i=0; i < r; i++)

{

if(s[i] == a - 0x30) return 0;

}

return 1;

}

/* */

long check_possible(char *begin, char *end)

{

char fs;

long f1=0, f2=0;

long i, j;

for(i=0; i < NUM; i++)

{

fs=0;

for(j=0; j < i; j++)

{

if((begin[i] != 0) && (begin[j] != 0) && (begin[j] < begin[i])) fs++;

}

f1+=fs;

fs=0;

for(j=0; j < i; j++)

{

if((end[i] != 0) && (end[j] != 0) && (end[j] < end[i])) fs++;

}

f2+=fs;

}

if((f1 & 1) == (f2 & 1))

return 1;

else

return 0;

}

/* */

void output(void)

{

long i, j, k;

char ss[NUM];

for(i=m_depth - 1; i >= 0; i--)

{

RTRANS(m_out[i].v, ss);

for(j=0; j < SIZE; j++)

{

for(k=0; k < SIZE; k++)

{

printf("%2d", ss[SIZE * j + k]);

}

printf("\n");

}

printf("\n");

}

}

/* */

int main(void)

{

char s1[NUM];

char s2[NUM];

long r;

char a;

printf("Input begin status:");

r=0;

while(r < NUM)

{

a=getch();

if(a >= 0x30 && a < 0x39 && check_input(s1, a, r))

{

s1[r++]=a - 0x30;

printf("%c", a);

}

}

printf("\nInput end status:");

r=0;

while(r < NUM)

{

a=getch();

if(a >= 0x30 && a < 0x39 && check_input(s2, a, r))

{

s2[r++]=a - 0x30;

printf("%c", a);

}

}

printf("\n");

if(check_possible(s1, s2))

{

r=bfs_search(s1, s2);

printf("\n");

if(r >= 0)

{

printf("search depth=%d, nodes=%ld\n", m_depth, r);

output();

}

else if(r == -1)

{

printf("Not enouph nodes searched.\n");

}

else if(r == -2)

{

printf("No way to do that.\n");

}

else

{

printf("Unknown error.\n");

}

}

else

{

printf("Mission impossible!\n");

}

return 0;

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有