كد:
//h_r_k_s@yahoo.com
//IDS code
#include <conio.h>
#include <iostream.h>
int g[10]={0,1,2,3,4,5,6,7,8,0};//goal
int s[10]={0,3,2,4,5,6,7,8,0,1};//initial state
void IDS(int,int,int);
void init(int [][5],int,int);
void succesor(int ,int );
int goalcheck();
int d=0;
int flag=0;
int arr[2][100];
int r=0;
int t;
void main()
{
clrscr();
int l=1;
while(d==0)
{
IDS(1,1,l);
if(flag==1)
{
d=1;
}
l++;
}
l--;
cout<<l;
for(int i=0;i<t;i++)
{
cout<<"\n"<<arr[0][i]<<" "<<arr[1][i];
}
getch();
}
void IDS(int i,int j,int l)
{
if(goalcheck()==1)
{
l=0;
flag=1;
t=r;
return;
}
else if(l>0)
{
int sucarray[2][5];
init(sucarray,j,i);
int k=0;
while(sucarray[0][k]!=-1 && flag!=1)
{
succesor(sucarray[0][k],sucarray[1][k]);
arr[0][r]=sucarray[0][k];
arr[1][r]=sucarray[1][k];
r++;
IDS(sucarray[0][k],sucarray[1][k],l-1);
succesor(sucarray[0][k],sucarray[1][k]);
k++;
r--;
}
return;
}
}
void init(int sucarray[][5],int a,int b)
{
int i=1;
while(s[i]!=0)
i++;
if(i==1)
{
sucarray[0][0]=i;
sucarray[1][0]=i+1;//1:2
sucarray[0][1]=i;
sucarray[1][1]=i+3;//1:4
sucarray[0][2]=-1;
}else if(i==2)
{
sucarray[0][0]=i;
sucarray[1][0]=i-1;//2:1
sucarray[0][1]=i;
sucarray[1][1]=i+1;//2:3
sucarray[0][2]=i;
sucarray[1][2]=i+3;//2:5
sucarray[0][3]=-1;
}else if(i==3)
{
sucarray[0][0]=i;
sucarray[1][0]=i-1;//3:2
sucarray[0][1]=i;
sucarray[1][1]=i+3;//3:6
sucarray[0][2]=-1;
}else if(i==4)
{
sucarray[0][0]=i;
sucarray[1][0]=i+1;//4:5
sucarray[0][1]=i;
sucarray[1][1]=i+3;//4:7
sucarray[0][2]=i;
sucarray[1][2]=i-3;//4:1
sucarray[0][3]=-1;
}else if(i==5)
{
sucarray[0][0]=i;
sucarray[1][0]=i+1;//5:6
sucarray[0][1]=i;
sucarray[1][1]=i-1;//5:4
sucarray[0][2]=i;
sucarray[1][2]=i-3;//5:2
sucarray[0][3]=i;
sucarray[1][3]=i+3;//5:8
sucarray[0][4]=-1;
}else if(i==6)
{
sucarray[0][0]=i;
sucarray[1][0]=i-3;//6:3
sucarray[0][1]=i;
sucarray[1][1]=i-1;//6:5
sucarray[0][2]=i;
sucarray[1][2]=i+3;//6:9
sucarray[0][3]=-1;
}else if(i==7)
{
sucarray[0][0]=i;
sucarray[1][0]=i+1;//7:8
sucarray[0][1]=i;
sucarray[1][1]=i-3;//7:4
sucarray[0][2]=-1;
}else if(i==8)
{
sucarray[0][0]=i;
sucarray[1][0]=i-1;//8:7
sucarray[0][1]=i;
sucarray[1][1]=i+1;//8:9
sucarray[0][2]=i;
sucarray[1][2]=i-3;//8:5
sucarray[0][3]=-1;
}else
{
sucarray[0][0]=i;
sucarray[1][0]=i-1;//9:8
sucarray[0][1]=i;
sucarray[1][1]=i-3;//9:6
sucarray[0][2]=-1;
}
int k=0;
while(sucarray[0][k]!=-1)
{
if(sucarray[1][k]==b)
{
for(int v=k;v<4;v++)
{
sucarray[0][v]=sucarray[0][v+1];
sucarray[1][v]=sucarray[1][v+1];
}
}
k++;
}
}
void succesor(int a,int b)
{
int temp;
temp=s[a];
s[a]=s[b];
s[b]=temp;
}
int goalcheck()
{
for(int i=1;i<=9;i++)
{
if(s[i]!=g[i])
return -1;
}
return 1;
}