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);
}
}
}