八数码问题:
Problem Description
The 15-puzzle has been around for over 100 years; even if you don't know it by that name, you've seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing. Let's call the
missing tile 'x'; the object of the puzzle is to arrange the tiles so that they are ordered as:
missing tile 'x'; the object of the puzzle is to arrange the tiles so that they are ordered as:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 x
where the only legal operation is to exchange 'x' with one of the tiles with which it shares an edge. As an example, the following sequence of moves solves a slightly scrambled puzzle:
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8
9 x 10 12 9 10 x 12 9 10 11 12 9 10 11 12
13 14 11 15 13 14 11 15 13 14 x 15 13 14 15 x
r-> d-> r->
The letters in the previous row indicate which neighbor of the 'x' tile is swapped with the 'x' tile at each step; legal values are 'r','l','u' and 'd', for right, left, up, and down, respectively.
Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and
frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing 'x' tile, of course).
In this problem, you will write a program for solving the less well-known 8-puzzle, composed of tiles on a three by three
arrangement.
Input
You will receive, several descriptions of configuration of the 8 puzzle. One description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are
represented by numbers 1 to 8, plus 'x'. For example, this puzzle
represented by numbers 1 to 8, plus 'x'. For example, this puzzle
1 2 3
x 4 6
7 5 8
is described by this list:
1 2 3 x 4 6 7 5 8
Output
You will print to standard output either the word ``unsolvable'', if the puzzle has no solution, or a string consisting entirely of the letters 'r', 'l', 'u' and 'd' that describes a series of moves that produce a solution. The string should include no spaces
and start at the beginning of the line. Do not print a blank line between cases.
and start at the beginning of the line. Do not print a blank line between cases.
Sample Input
2 3 4 1 5 x 7 6 8
Sample Output
ullddrurdllurdruldr
本题有多种答案，采用special judge
我设置两个队列，采用双向广搜的方法，可是没有AC；不知那组数据出问题了。
下面附代码：
#include <iostream>
#include <map>
#include <cstdio>
using namespace std;
#define M 500000
struct state
{
int father,code;
char dir;
};
state que[M],reque[M];
char path[M];// 答案数组
void codes(int code)
{
char s[10];
sprintf(s,"%d",code);
for(int i=0;i<9;i++)
{
if(i!=0&& i%3==0)
printf("\n");
printf("%c ",s[i]);
}
printf("\n\n");
}
int main()
{
int dir[4][2]= {{-1,0},{0,1},{1,0},{0,-1}}; //方向数组
char str[4]={'u','r','d','l'};//{'u','r','d','l'};
char str1[4]={'d','l','u','r'};
int base[9]= {100000000,10000000,1000000,100000,10000,1000,100,10,1};
map<int,int> a;
char w[3][3],w1[9];
int i,j,counter,qhead,qrear,re_qhead,re_qrear,ji,ji1,x,y,k;
int newx,newy;
while(cin>>w[0][0])
{
cin>>w[0][1]>>w[0][2];
w1[0]=w[0][0];
w1[1]=w[0][1];
w1[2]=w[0][2];
for(i=1;i<3;i++)
for(j=0;j<3;j++)
{
cin>>w[i][j];
w1[i*3+j]=w[i][j];// convert to one array
}
//求逆序对数
counter=0;
for(i=0; i<8; ++i)
for(j=i+1; j<9; ++j)
if(w1[i]!='x'&&w1[j]!='x'&&w1[i]>w1[j])
counter++;
//如果逆序对数是 奇数，那么无法转化为目标状态
if(counter&1)
{
printf("unsolveble!\n");
}
else
{
int e,s;
s=0;
e=123456789;//反向搜索的起始状态
//将八数码转换为一个整数s;
for(i=0; i<9; i++)
{
if(w1[i]=='x')
s=s*10+9;
else
s=s*10+(w1[i]-'0');
}
//init
qhead=qrear=re_qhead=re_qrear=1;
que[qrear].code=s; //队列1
reque[re_qrear].code=e;//队列2
a[s]=1;//正向搜索 已访问 标记为1
a[e]=2;//反向搜索 已访问 标记为2
bool flag=0;
if(s==e)//特殊情况处理
flag=1;
while(!flag)
{
for(ji=0; ji<9; ji++) //提取正着搜时x所在的位置
if((que[qhead].code/base[ji])%10==9)
break;
for(ji1=0; ji1<9; ji1++) //提取反着搜时x所在的位置
if((reque[re_qhead].code/base[ji1])%10==9)
break;
for(i=0; i<4; i++) //双向广搜
{
x=ji/3;
y=ji%3;
newx=x+dir[i][0];
newy=y+dir[i][1];
if(newx<3&&newx>=0&&newy<3&&newy>=0&&flag==0)
{
s=que[qhead].code;//s为当前的code
//求新的code
int d1=9;//d1=(s/base[ji])%10;//可以直接赋值为9
int d2=(s/base[newx*3+newy])%10;//与之交换的数放在d2中
s=s-d1*base[ji] - d2*base[newx*3+newy];
s=s+d1*base[newx*3 + newy]+d2*base[ji];
if(a[s]!=1)
{
if(a[s]==2)
flag=1;//搜到了
a[s]=1;//标记
qrear++;
que[qrear].code=s;
que[qrear].father=qhead;//记录该节点是由哪个节点扩展来的
que[qrear].dir=str[i];//标记方向
}
}
x=ji1/3;
y=ji1%3;
newx=x+dir[i][0];
newy=y+dir[i][1];
if(newx<3&&newx>=0&&newy<3&&newy>=0&&flag==0)
{
s=reque[re_qhead].code;//找到新的S
//求新的code
int d1=9;//d1=(s/base[ji1])%10;//可以直接赋值为9
int d2=(s/base[newx*3+newy])%10;//与之交换的数放在d2中
s=s-d1*base[ji1] - d2*base[newx*3+newy];
s=s+d1*base[newx*3 + newy]+d2*base[ji1];
if(a[s]==0)
{
a[s]=2;//标记
re_qrear++;
reque[re_qrear].code=s;
reque[re_qrear].father=re_qhead;//记录该节点是由哪个节点扩展来的
reque[re_qrear].dir=str1[i];//标记方向
}
}
}
qhead++;//从队列1中取下一个节点
re_qhead++;//从队列2 中取下一个节点
}//end while
//下面提取路径
counter=0;
k=qrear;
//printf("%d\n",que[qrear].code);
//codes(que[qrear].code);
while(k!=1)
{
path[counter++]=que[k].dir;
k=que[k].father;
}
for(i=counter-1;i>=0;i--)
printf("%c",path[i]);
// printf("\nup is first\n");
k=1;counter=0;
while(k<=re_qrear&&reque[k].code!=que[qrear].code)
{
k++;
}
//printf("%d\n",reque[reque[k].father].code);
while(k!=1)
{
path[counter++]=reque[k].dir;
k=reque[k].father;
// codes(reque[k].code);
}
for(i=0;i<counter;i++)
printf("%c",path[i]);
printf("\n");
a.clear();
}
}
return 0;
}
/**
2 3 4
1 5 x
7 6 8
1 2 3
4 5 6
7 8 x
*/