N numbers into 2N places

Question:

Place N number from 1 to N, in 2N positions in such a way so that there are Exactly n number of cells between two placed locations of number n.

Sample:

One of the possible placement for 7 numbers in 14 positions is :

5 7 2 3 6 2 5 3 4 7 1 6 1 4

Solution:

We will try backtracking approach,  we move from index 0 to 2N-1, at each index, we try to place a number that hasn’t been used, and then move to next index and repeat the process, if in between we find there is no number possible at some index, that means we were incorrect, and we need to backtrack. If we reach to last index, and place a number safely there, that means its possible to have such arrangement.

#include<iostream>
#include<climits>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#include<cstring>
using namespace std;

#define FOR(i,a,b)      for(__typeof(b) i=(a);i<(b);++i)
#define REP(i,n)        for(__typeof(n) i=0;i<(n);i++)
#define FILL(a,b)       memset(a,b,sizeof(a))

#define SIZE 100
int N,len;
int arr[SIZE];
bool numbers[SIZE];

bool permute(int pos){
/*if pos>=len , that means we have placed all the numbers
from 1 to N , so we can print the array, and return
*/
if(pos>=len){
//nothing fancy, just printing the array
printf("POSSIBLE for N = %d ----> ",N);
REP(i,len){
cout<<arr[i]<<" ";
}
cout<<endl;
return true;
}
//if that position is already filled, that means move on 😛
if(arr[pos]!=0){
return permute(pos+1);
}

//go through all numbers
FOR(i,1,N+1){
//if number is not used
if(!numbers[i]){
//if second place is in bound
if(pos+i+1<len&&!arr[pos]&&!arr[pos+i+1]){
arr[pos]=i;//place the number i at index pos
arr[pos+i+1]=i;//place the number i at index pos+i+1
numbers[i]=true;//number i used now
//check if this will lead us to end
if(permute(pos+1)){
return true;
}
//BACKTRACK
arr[pos]=0;//free the index pos
arr[pos+i+1]=0;//free the index pos+i+1
numbers[i]=false;//number not used now
}
}
}
return false;
}

void doThis(){
//N number
scanf("%d",&N);
// 2N places
len = 2*N;
//initialise array with 0
FILL(arr,0);
FILL(numbers,false);//all numbers are free to be used

//here we go
if(permute(0)){
//if possible then no need to do anything 🙂
}else{
printf("NOT POSSIBLE for N = %d\n",N);
}
}

int main(){
#ifdef amy
freopen("C:\\A\\in.txt","r",stdin);freopen("C:\\A\\out.txt","w",stdout);
#endif
int t;
scanf("%d",&t);//number of test cases
while(t--){doThis();}
#ifdef amy
fprintf(stdout,"\nTIME: %.3lf sec\n",(double)clock()/(CLOCKS_PER_SEC));
#endif
return 0;
}

/*
INPUT

12
1
2
3
4
5
6
7
8
9
10
11
12

OUTPUT

NOT POSSIBLE for N = 1
NOT POSSIBLE for N = 2
POSSIBLE for N = 3 ----> 2 3 1 2 1 3
POSSIBLE for N = 4 ----> 2 3 4 2 1 3 1 4
NOT POSSIBLE for N = 5
NOT POSSIBLE for N = 6
POSSIBLE for N = 7 ----> 1 4 1 5 6 7 4 2 3 5 2 6 3 7
POSSIBLE for N = 8 ----> 1 3 1 6 7 3 8 5 2 4 6 2 7 5 4 8
NOT POSSIBLE for N = 9
NOT POSSIBLE for N = 10
POSSIBLE for N = 11 ----> 1 2 1 4 2 8 9 10 4 11 6 3 7 5 8 3 9 6 10 5 7 11
POSSIBLE for N = 12 ----> 1 2 1 3 2 8 9 3 10 11 12 5 7 4 8 6 9 5 4 10 7 11 6 12

TIME: 0.069 sec
*/