1. Erste Version: C, Evgeni Pavlidis


/**
* ACM programming Contest WS 08/09
* UVa Status: accepted
* Run Time: 0.640
* @author Evgeni Pavlidis evgenipavlidis@yahoo.de
*/
#include <stdio.h>
#include <math.h>

#define CIRCLE_MAX 20

int circle[CIRCLE_MAX] = {1};
int pool[CIRCLE_MAX+1] = {};
int n;

int isPrime[41] = { 0, 0, 1, 1, 0, 1, 0, 1, 0,0,0, 1, 0, 1, 0,0,0, 1, 0, 1,
0,0,0, 1, 0,0,0,0,0, 1,0,1,0,0,0,0,0,1,0,0,0};

int main()
{
int counter = 1;
while(1)
{
scanf("%d\n", &n);
printf("Case %d:\n", counter++);

int i;
for(i = 1; i <= n; i++)
pool[i] = 1;

circle[0] = 1;
backtrack(1);

if(feof(stdin))
return 0;
printf("\n");
}
}
void printCircle()
{
int i;
for(i = 0; i < n-1; i++)
printf("%d ", circle[i]);

printf("%d\n", circle[i]);
}

void backtrack(int pos)
{
int i;
if(pos == n)
{
if(isPrime[circle[pos-1] + 1])
printCircle();
return;
}
for(i = 2; i <= n; i++)
if( pool[i] == 1 && isPrime[ circle[pos-1] + i ])
{
pool[i] = 0;
circle[pos] = i;
backtrack(pos+1);

pool[i] = 1;
}
}