c - Program to sort an array under conditions on sum and movement of elements

Question

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.

Answer 1

I couldn't go through the whole code you gave, but as far as I could understand it, you don't check partial results for uniqueness: you never know if the board state has already been checked. As a result your code makes the same flips to and fro, repeating the same analysis multiple times. The same board states are enqueued again and again, resulting in data structure overflow.

Add another queue, eg. Queue *seen;, to keep all numbers' permutations tested, and check every new permuttion in posflips() if it is already in seen. If so, ignore the permutation, else add it both to qu and to seen.

PS.
You know the numbers are 1 to 9 only, so the sum of two can be 3 to 17, consequently there are only 6 possible primes and your primecheck() can be simplified to

int primecheck(int numloc1,int numloc2){
    switch(numloc1+numloc2){
        case  3:
        case  5:
        case  7:
        case 11:
        case 13:
        case 17:
            return 1;
    }
    return 0;
}

There are 36 total pairs of tiles in your board and only 12 of them are pairs of adjacent tiles. So 2/3 of primecheck() invocations done in posflips() are useless. You should call check() first and only if it succeedes call primecheck(), like this:

if(check(i,j) && primecheck(c[i],c[j])){
    //....
}

In addidtion, you can get rid of check() at all. Your board is quite small, so it might be easier to enumerate all valid pairs of positions than test every pair for validity:

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 p;
for(p=0;p<12;p++){
    int i = validPair[p][0];
    int j = validPair[p][1];
    if(primecheck(c[i],c[j])){
        // ... do flips
        // ... check flipped board against 'seen' queue
        // ... and Enqueue if the board not seen before
    }

EDIT

If you rename seencond to arraysAreEqual and seencond2 to arrayWasSeen it will become quite obvious the initialization

arrayWasSeen=0;

formerly

seencond2=0;

should go just before the while loop.

Note: as you construct a flipped array in a separate place, you don't need temp variable – just cross-copy the two items from the original array:

for(j=0;j<9;j++)
    c[j]=b[j];
c[p]=b[q];
c[q]=b[p];