Let's talk about Backtracking

[globi]

Hello.

Can anyone tell me some about backtracking.
There's a lot of such problems. For ex. 524 - "Prime Ring Problem".
There are very interesting, so I want to learn some about
this algorimic method. Please help.

Thanks.

Yo

[kfree]

Backtracking is a basis algorithm for solve UVA problem.
It have algorithm framework,you could refer to some books.for example,《The Algorithm Design Manual》
URL http://www.darkridge.com/~jpr5/archive/alg/node1.html

Code: Select all

[c]#include <stdio.h>
int n;
int nLoop[21];
int beUsed[21];
int isPrime[40]={0,0,2,3,0,5,0,7,0,0,0,11,
                  0,13,0,0,0,17,0,19,0,0,
                  0,23,0,0,0,0,0,29,0,31,0,
                  0,0,0,0,37,0,0};

int testprime(int p)
{
return isPrime[p];
}

void search(int step)
{
		int i;
		if(step==n)
		{
				if(testprime(nLoop[0]+nLoop[n-1]))
				{
						for(i=0;i<n-1;i++)
						printf("%d ",nLoop[i]);
						printf("%d",nLoop[n-1]);
						printf("\n");
				}
				return;
		}
		for(i=1;i<=n;i++)
		{
		if(!beUsed[i] && (testprime(i+nLoop[step-1]))){
				beUsed[i]=1;
				nLoop[step]=i;
				search(step+1);
				beUsed[i]=0;
				}
		}
}

int main()
{
int i=1;
while(scanf("%d",&n)!=EOF){
    printf("Case %d:\n",i);
    i++;
    if(n%2==0){
        beUsed[1]=1;
        nLoop[0]=1;
        search(1);
        }
    printf("\n");
}
return 0;
}[/c]