/*
八数码问题
有一个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;
}
