PLEASE give me some algorithmic idea about peg games.

recently i have problems about peg games and i've already submitted a source on poj.org (pku 2805 -> and there is the problem 'pegs')

I used back tracking strategy because i cannot recall any solution but that algorithm.

and here, i submit a source which i made for solve the problem.

#include<stdio.h>
char origin[5][5];
int mini=99999;
int cal(int peg[5][5]);
int main()
{
int i, j, set, carrier[5][5];
scanf("%d",&set);
while(set>0)
{
set--;
for(i=0;i<5;i++)
{
scanf("%s",origin[i]);
for(j=0;j<5;j++)
{
if(origin[i][j]=='o')
{
carrier[i][j]=1;
}
else if(origin[i][j]=='.')
{
carrier[i][j]=0;
}
else if(origin[i][j]=='#')
{
carrier[i][j]=2;
}
}
}
cal(carrier);
printf("The best case ends with %d pegs\n",mini);
mini=99999;
}
return 0;
}
int cal(int peg[5][5])
{
int i, j, token=0, s=0;
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
if(peg[i][j]==1)
{
s++;
if((j-1)>=0)
{
if(peg[i][j-1]==1 && (j-2) >=0)
{
if(peg[i][j-2]==0)
{
peg[i][j]=0;
peg[i][j-1]=0;
peg[i][j-2]=1;
token = 1;
cal(peg);
peg[i][j]=1;
peg[i][j-1]=1;
peg[i][j-2]=0;
}
}
}
if((j+1)<5)
{
if(peg[i][j+1]==1 && (j+2)<5)
{
if(peg[i][j+2]==0)
{
peg[i][j]=0;
peg[i][j+1]=0;
peg[i][j+2]=1;
token=1;
cal(peg);
peg[i][j]=1;
peg[i][j+1]=1;
peg[i][j+2]=0;
}
}
}
if((i-1)>=0)
{
if(peg[i-1][j]==1 && (i-2) >=0)
{
if(peg[i-2][j]==0)
{
peg[i][j]=0;
peg[i-1][j]=0;
peg[i-2][j]=1;
token = 1;
cal(peg);
peg[i][j]=1;
peg[i-1][j]=1;
peg[i-2][j]=0;
}
}
}
if((i+1)<5)
{
if(peg[i+1][j]==1 && (i+2)<5)
{
if(peg[i+2][j]==0)
{
peg[i][j]=0;
peg[i+1][j]=0;
peg[i+2][j]=1;
token = 1;
cal(peg);
peg[i][j]=1;
peg[i+1][j]=1;
peg[i+2][j]=0;
}
}
}
}
}
}
if(token == 0)
{
if(mini>s)
{
mini=s;
}
}
return 0;
}

and judge submitted this source as "time limit exceed"
what i want to know is which strategy i should use. and the mistake that i missed. please give me some help.

p.s, please use simple english. because i'm from a country where english is not mothertongue..
Last edited on
back tracking is similar to brute-forcing, which is pretty slow. Try to come up with a REAL algorithm!
but,, i cannot remind any algorithm however hard i tried... please give me some idea..
(that's why i choosed back tracking for last solution(which is time-consuming))
That is part of being a programmer. You have to learn to make your own algorithms for problems. You don't necessarily have to use existing ones. Hobbyist or professional, you have to learn to do it yourself or you will keep doing this with every project you do.
Topic archived. No new replies allowed.