You are given a 3x3 array of numbers from 1-9.
At each step, you may swap two adjacent tiles if their sum is a prime number. Two tiles are considered adjacent if they have a common edge.
This is a problem from:
http://www.codechef.com/problems/H1
I made this program which sorts the given array following the given rules. For arrays/puzzles with number of minimum flips=7, it works. but for arrays/puzzles with minimum flips more than that it does not work.
#include <stdio.h>
#include <stdlib.h>
int a[9]={6,3,5,4,7,2,1,9,8};
//6,3,5,7,9,4,1,8,2
int b[9]={0};
int c[9]={0};
int d[9]={0};
int e[9]={0};
int sortcond=0,count=0;
typedef struct Queue
{
int capacity;
int size;
int front;
int rear;
int *elements;
}Queue;
Queue * createQueue(int maxElements)
{
Queue *Q;
Q = (Queue *)malloc(sizeof(Queue));
Q->elements = (int *)malloc(sizeof(int)*maxElements);
Q->size = 0;
Q->capacity = maxElements;
Q->front = 0;
Q->rear = -1;
return Q;
}
void Dequeue(Queue *Q)
{
if(Q->size==0)
{
printf("Queue is Empty
");
return;
}
else
{
Q->size--;
Q->front++;
if(Q->front==Q->capacity)
{
Q->front=0;
}
}
return;
}
int front(Queue *Q)
{
if(Q->size==0)
{
printf("Queue is Empty
");
exit(0);
}
return Q->elements[Q->front];
}
void Enqueue(Queue *Q,int element)
{
if(Q->size == Q->capacity)
{
printf("Queue is Full
");
}
else
{
Q->size++;
Q->rear = Q->rear + 1;
if(Q->rear == Q->capacity)
{
Q->rear = 0;
}
Q->elements[Q->rear] = element;
}
return;
}
void enqueue(Queue *Q,int *element)
{
int i;
if(Q->size == Q->capacity)
{
printf("Queue is Full
");
}
else
{
for(i=0;i<9;i++){
Q->size++;
Q->rear = Q->rear + 1;
if(Q->rear == Q->capacity)
{
Q->rear = 0;
}
Q->elements[Q->rear] = *(element+i);
}
}
return;
}
void EnQueue(Queue *Q,int *element)
{
int i;
if(Q->size == Q->capacity)
{
printf("Queue is Full
");
}
else
{
Q->elements[Q->rear] = *element;
for(i=1;i<9;i++){
Q->size++;
Q->rear = Q->rear + 1;
if(Q->rear == Q->capacity)
{
Q->rear = 0;
}
Q->elements[Q->rear] = *(element+i);
}
}
return;
}
Queue *que,*seen;
int primecheck(int num1,int num2){
switch(num1+num2){
case 3:
case 5:
case 7:
case 11:
case 13:
case 17:
return 1;
}
return 0;
}
int possibleflips(){
int validpair[12][2] = { {0,1}, {1,2}, {3,4}, {4,5}, {6,7}, {7,8}, {0,3}, {3,6}, {1,4}, {4,7}, {2,5}, {5,8} };
int i,j,p,q,temp,seencond,seencond2;
//printf("entered possibleflips
");
for(i=0;i<12;i++){
int p = validpair[i][0];
int q = validpair[i][1];
if(primecheck(b[p],b[q])){
for(j=0;j<9;j++){
c[j]=b[j];
}
temp=c[p];
c[p]=c[q];
c[q]=temp;
while(front(seen)!=0){
seencond=1;
seencond2=0;
for(j=0;j<9;j++){
d[j]=front(seen);
if(c[j]==front(seen));
else
seencond=0;
Dequeue(seen);
}
enqueue(seen,d);
if(seencond==1){
seencond2=1;
}
}
if(seencond2==0){
EnQueue(seen,c);
Enqueue(seen,0);
enqueue(que,c);
}
else{
Dequeue(seen);
Enqueue(seen,0);
}
}
}
//printf("exit possibleflips
");
return;
}
int searching(){
int i,cond;
//printf("entered search
");
while(front(que)!=0){
cond=1;
for(i=0;i<9;i++){
e[i]=front(que);
if(front(que)==i+1);
else
cond=0;
Dequeue(que);
}
enqueue(que,e);
if(cond==1){
sortcond=1;
return;
}
}
Dequeue(que);
Enqueue(que,0);
//printf("exit search
");
return;
}
int firststep(){
int i;
//printf("firststep
");
while(sortcond==0){
while(front(que)!=0){
for(i=0;i<9;i++){
b[i]=front(que);
//printf("%d ",b[i]);
Dequeue(que);
}
//printf("
");
possibleflips();
}
Dequeue(que);
Enqueue(que,0);
searching();
count++;
}
return;
}
int main()
{
int i;
que=createQueue(5000000);
seen=createQueue(5000000);
enqueue(que,a);
Enqueue(que,0);
enqueue(seen,a);
Enqueue(seen,0);
firststep();
printf("count %d", count);
return 0;
}
a[] is the given array (you can put some simple problem like 1,3,2,4,5,6,7,8,9) and it works for them.
it first adds the given array to queue and, finds the arrays you can make in one swap on the given array and adds them to queue and removes the given array from the queue. searches if any of them makes it 1,2..9. If not, then it finds the arrays you can make in one more swap, i.e. two swaps away from the given array, and adds them to queue and so on. It also checks for the repetition of cases.
Works fine for arrays with minimum number of flips under 7 e.g. {6,3,5,7,9,4,1,8,2}. but for arrays with minimum number of flips more than that, e.g. {6,3,5,4,7,2,1,9,8}, it is not working.
See Question&Answers more detail:
os