Program For Eight Queen Problem

Output

#include<stdio.h>
#include<malloc.h>
#include<conio.h>

// Declaration of Structure
typedef struct p
{
int row;
int col;
}position;

typedef struct node
{
position *p;
struct node *link;
}structnode;
typedef struct
{
int count;
structnode *link;
}stack;

//  Declaration of Function
int getsize();
int guarded(int board[9][9],int row,int col,int boardsize);
void *createstack();
void fillboard(stack *st,int boardsize);
void push(stack *st,position *p);
position pop(stack *st);
void printboard(stack *st,int boardsize);

// Main function
int main()
{
position p;
int boardsize;
stack *st;
boardsize=getsize();
st=(stack*)createstack();
fillboard(st,boardsize);
printboard(st,boardsize);
printf("\nwe hope you enjoyed queens\n");
getch();
}

// Return valid Size of the board
int getsize()
{
int boardsize;
printf("welcome toeight queens.you may select\n"
"a board size from 4*4 to 8*8.i will\n"
"then position a queen in each row of the\n"
"board so no queen may capture another\n"
"queen.note:there is no solution for board\n"
"less than 4*4 and more than 8*8\n");
printf("\nenter the size of board\n");
scanf("%d",&boardsize);
while(boardsize<4||boardsize>8)
{
printf("board size is greater than 3 and\n"
       "lesst han 9.you entered %d.\n"
       "please re-enter.thankyou.\a\a\n\n"
       "your board size:",boardsize);
scanf("%d",&boardsize);
}
return(boardsize);
}

// Create Stack header
void *createstack()
{
stack *st;
st=(stack*)malloc(sizeof(st));
st->count=0;
st->link=NULL;
return(st);
}

// Correct arrangements for queens on board
void fillboard(stack *st,int boardsize)
{
int row;
int col;
int board[9][9]={0};
position *p;
position s;
row=1;
col=0;
while(row<=boardsize)
{
while(col<=boardsize&&row<=boardsize)
{
col++;
if(guarded(board,row,col,boardsize)==0)
{
board[row][col]=1;
p=(position*)malloc(sizeof(position));
p->row=row;
p->col=col;
push(st,p);
row++;
col=0;
}
while(col>=boardsize)
{
s=pop(st);
row=s.row;
col=s.col;
board[row][col]=0;
}
}
}
}

// Stack push
void push(stack *st,position *p)
{
structnode *node;
(st->count)++;
node=(structnode*)malloc(sizeof(structnode));
node->p=p;
printf("\npush %d %d",node->p->row,node->p->col);
node->link=st->link;
st->link=node;
}
position pop(stack *st)
{
void *temp;
position s;
s.row=st->link->p->row;
s.col=st->link->p->col;
printf("\npop %d %d",s.row,s.col);
free(st->link->p);
temp=st->link;
st->link=st->link->link;
free(temp);
(st->count)--;
return(s);
}

// checking queen position
int guarded(int board[][9],int chkrow,int chkcol,int boardsize)
{
int row;
int col;
col=chkcol;
for(row=1;row<=chkrow;row++)
{
if(board[row][col]==1)
{
return(1);
}
}
for(row=chkrow-1,col=chkcol+1;row>0&&col<=boardsize;row--,col++)
{
if(board[row][col]==1)
{
return(1);
}
}
for(row=chkrow-1,col=chkcol-1;row>0&&col>0;row--,col--)
{
if(board[row][col]==1)
{
return(1);
}
}
return(0);
}

// Board
void printboard(stack *st,int boardsize)
{
int col;
position s;
stack *sp;
position *p;
sp=(stack*)createstack();
while(st->count!=0)
{
s=pop(st);
p=(position*)malloc(sizeof(position));
p->row=s.row;
p->col=s.col;
push(sp,p);
}
free(st);
if(sp->count==0)
{
printf("\nthere are no position on this board\n");
return;
}
printf("\nplace queens in following positions\n");
while(sp->count!=0)
{
s=pop(sp);
printf("row %d-col %d:\t|",
 s.row,s.col);
for(col=1;col<=boardsize;col++)
{
if(s.col==col)
{
printf(" Q|");
}
else
{
printf("  |");
}
}
printf("\n");
}
free(sp);

}