0

I made my own program for N-queen problem (A popular algorithm in Data Structures). Check this code and post your suggestions. If you have any ideas for the improvement of algorithm speed, please post here. Thanks.

#include <stdio.h>
#include <stdlib.h>
//N-Queen Chess problem solving Algorithm//
//Note:- Uncomment The printf("") & if() condition lines if you want to know more about the behaviors of this algorithm
//Copyright (c) udinnet

struct queen
{
    int queenId;
    int col;
    int row;
    struct queen* next;
};

void insertq(struct queen**,int,int*);
void backtrack(struct queen**,int,int*);
void pop(struct queen **,int*);
void checkatt(struct queen**,int,int*);
void printans(struct queen*,int);

int main()
{
    struct queen* stk;
    stk=NULL;
    int chessN;
    int qcount=0;

    printf("Enter n for the chess board(NxN)(Min(N)=3): ");
    scanf("%d",&chessN);
    if(chessN<=3)
    {
        printf("I told you I want More than 3x3 Matrix\nTo run this Algoritm\n");
        exit(1);
    }

    while(qcount<chessN)
    {
        //printf("Loop Qcount main:%d\n",qcount);
        //if(stk!=NULL)
        //printf("Loop QID main:%d\n",stk->queenId);
        insertq(&stk,chessN,&qcount);

    }
    printans(stk,qcount);
    getchar();
    return 0;
}

void printans(struct queen *pnt,int id)
{
    printf("\n\n\n*** Wow!!! The answer is.... ***\n\n");
    while(pnt!=NULL)
    {
        printf("Queen:%d  Col:%d  --  Row:%d\n",id--,pnt->col,pnt->row);
        pnt=pnt->next;
    }
}


void insertq(struct queen **chq,int max,int *qcount)
{
    fflush(stdin);
    if(*chq==NULL)
    {
        *chq=malloc(sizeof(struct queen));
        (*chq)->next=NULL;
        *qcount=*qcount+1;
        (*chq)->queenId=*qcount;
        (*chq)->col=(*chq)->row=1;
        //printf("Init Qcount %d\n",*qcount);
        //printf("Init QID %d\n",(*chq)->queenId);
    }
    else
    {
        if((*chq)->queenId<max)
        {

            struct queen *tmp;
            tmp=malloc(sizeof(struct queen));
            *qcount=*qcount+1;
            tmp->queenId=*qcount;
            tmp->row=*qcount;
            //printf("Attach QID:%d\n",tmp->queenId);
            //printf("Attach Qcount:%d\n",tmp->queenId);
            tmp->col=1;
            tmp->next=*chq;
            *chq=tmp;
        }
    }
    checkatt(chq,max,qcount);
}

void pop(struct queen **popstk,int *qcount)
{
    if(*popstk!=NULL)
    {
        struct queen *tmp;
        tmp=*popstk;
        *popstk=(*popstk)->next;
        printf("\n\n** Poped out Queen Col:%d Row:%d **\n\n",tmp->col,tmp->row);
        --(*qcount);
        free(tmp);
    }
}

void backtrack(struct queen **btrk,int max,int *qcount)
{
    pop(btrk,qcount);
    if(*btrk!=NULL&&(*btrk)->col==max)
    {
        backtrack(btrk,max,qcount);
    }
    else
    {
        if(*btrk!=NULL)
        (*btrk)->col=(*btrk)->col+1;
        checkatt(btrk,max,qcount);
    }
}

void checkatt(struct queen **att,int max,int *qcount)
{
    struct queen *tmpq;
    tmpq=*att;
    int flag=0;
    int tmpcol;
    int tmprow;

    beginx:

        /*N-E*/
    tmpcol=(*att)->col;
    tmprow=(*att)->row;
    tmpcol++;
    tmprow++;
    while(flag!=1&&((tmpcol<=max&&tmpcol>0)&&(tmprow<=max&&tmprow>0)))
    {
        tmpq=*att;
        tmpq=tmpq->next;
        while(tmpq!=NULL)
        {
            if(tmpq->col==tmpcol&&tmpq->row==tmprow)
            {
                flag=1;
                break;
            }
            else
            {
                tmpq=tmpq->next;
            }
        }
        tmpcol++;
        tmprow++;
    }

    //printf("N-E Flag: %d\n",flag);


        /*S-E*/
    tmpcol=(*att)->col;
    tmprow=(*att)->row;
    tmpcol++;
    tmprow--;
    while(flag!=1&&((tmpcol<=max&&tmpcol>0)&&(tmprow<=max&&tmprow>0)))
    {
        tmpq=*att;
        tmpq=tmpq->next;
        while(tmpq!=NULL)
        {
            if(tmpq->col==tmpcol&&tmpq->row==tmprow)
            {
                flag=1;
                break;
            }
            else
            {
                tmpq=tmpq->next;
            }
        }
        tmpcol++;
        tmprow--;
    }
    //printf("S-E Flag: %d\n",flag);


        /*S-W*/
    tmpcol=(*att)->col;
    tmprow=(*att)->row;
    tmpcol--;
    tmprow--;
    while(flag!=1&&((tmpcol<=max&&tmpcol>0)&&(tmprow<=max&&tmprow>0)))
    {
        tmpq=*att;
        tmpq=tmpq->next;
        while(tmpq!=NULL)
        {
            if(tmpq->col==tmpcol&&tmpq->row==tmprow)
            {
                flag=1;
                break;
            }
            else
            {
                tmpq=tmpq->next;
            }
        }
        tmpcol--;
        tmprow--;
    }
    //printf("S-W Flag: %d\n",flag);


    /*N-W*/
    tmpcol=(*att)->col;
    tmprow=(*att)->row;
    tmpcol--;
    tmprow++;
    while(flag!=1&&((tmpcol<=max&&tmpcol>0)&&(tmprow<=max&&tmprow>0)))
    {
        tmpq=*att;
        tmpq=tmpq->next;
        while(tmpq!=NULL)
        {
            if(tmpq->col==tmpcol&&tmpq->row==tmprow)
            {
                flag=1;
                break;
            }
            else
            {
                tmpq=tmpq->next;
            }
        }
        tmpcol--;
        tmprow++;
    }
    //printf("N-W Flag: %d\n",flag);


        /*Row inc*/
    tmpcol=(*att)->col;
    tmprow=(*att)->row;
    tmprow++;
    while(flag!=1&&(tmprow<=max&&tmprow>0))
    {
        tmpq=*att;
        tmpq=tmpq->next;
        while(tmpq!=NULL)
        {
            if(tmpq->col==tmpcol&&tmpq->row==tmprow)
            {
                flag=1;
                break;
            }
            else
            {
                tmpq=tmpq->next;
            }
        }
        tmprow++;
    }
    //printf("Row-INC Flag: %d\n",flag);


     /*Row Dec*/
    tmpcol=(*att)->col;
    tmprow=(*att)->row;
    tmprow--;
    while(flag!=1&&(tmprow<=max&&tmprow>0))
    {
        tmpq=*att;
        tmpq=tmpq->next;
        while(tmpq!=NULL)
        {
            if(tmpq->col==tmpcol&&tmpq->row==tmprow)
            {
                flag=1;
                break;
            }
            else
            {
                tmpq=tmpq->next;
            }
        }
        tmprow--;
    }
    //printf("Row-DEC Flag: %d\n",flag);
    //printf("Now Queen(STK TOP)in:- clo:%d row:%d\n",(*att)->col,(*att)->row);
    /*final*/
    if(flag==1&&(*att)->col<max)
    {
        flag=0;
        (*att)->col=(*att)->col+1;
        goto beginx;
    }

    else
    {
        if(flag==1&&(*att)->col==max)
        {
            flag=0;
            backtrack(att,max,qcount);
        }
    }
}

Edited by udinnet: n/a

2
Contributors
1
Reply
10
Views
6 Years
Discussion Span
Last Post by Adak
0

Welcome to the forum, udinnet! ;)

Tell us a little about this program. Is it meant to find one solution, or all the solutions?

What kind of run times are you getting for 8 queens, on an 8 X 8 board? On what kind of system (cpu speed)?

Do you think it's slow, fast, or in-between? What is your opinion of it?

Edited by Adak: n/a

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.