C program to solve N-Queen puzzle by recursive and iterative method

Q.Write a C program for solving N-Queen puzzle by Recursive and iterative method.

Source Code->  

#include<stdio.h>

#include<conio.h>

int n,x[20],count=0,st[50];

void display(int x[])

{

int i,j;

count++;

printf("\n\n\tTHE SOLUTION NO: %d",count);

for(i=1;i<=n;i++)

{

   printf("\n\n");

   for(j=1;j<=n;j++)

   {

if(x[i]==j)

printf("\tQ");

else

printf("\t.");

}

}

}

int Place(int k,int i)

{

int j;

for(j=1;j<=k-1;j++)

{

if((x[j]==i)||abs(x[j]-i)==abs(j-k))

return 0 ;

}

return 1;

}

void NQueen(int k,int n)

{

int i;

 for(i=1;i<=n;i++)

 {

if(Place(k,i))

{

x[k]=i;

if(k==n)

{

display(x);

}

else

NQueen(k+1,n);

}

 }

}

void INQueen(int k,int n)

{

int i=1;

st[0]=0;

while(k!=0)

{

if(Place(k,i))

{

x[k]=i;

if(k==n)

display(x);

else

{ st[k]=i;

k=k+1;

i=0;

}

}

while(i==n)

{ k=k-1;

i=st[k];

}

i++;

}

}

void main()

{

  int ch;

  do{ clrscr();      count=0;

printf("\n\n\t\t****MENU FOR N QUEEN PROBLEM****");

printf("\n\n\t\t1. BY ITERATIVE METHOD");

printf("\n\n\t\t2. BY RECURSIVE METHOD");

printf("\n\n\t\t3. EXIT");

printf("\n\n\t\tENTER YOUR CHOICE:");

scanf("%d",&ch);

switch(ch)

{

case 1:

printf("\n\n\t\tENTER THE VALUE OF N:");

scanf("%d",&n);

INQueen(1,n);

break;

case 2:

printf("\n\n\t\tENTER THE VALUE OF N:");

scanf("%d",&n);

NQueen(1,n);

break;

default: printf("\n\n\t\t ENTER VALID CHOICE");

}

printf("\n\n\t\tTHE NUMBER OF OPTIMAL SOLUTION: %d",count);

getch();

  }while(ch!=3);

 }

Output:->

          ****MENU FOR N QUEEN PROBLEM****

          1. BY ITERATIVE METHOD

          2. BY RECURSIVE METHOD

          3. EXIT

          ENTER YOUR CHOICE: 1

          ENTER THE VALUE OF N:4

  THE SOLUTION NO: 1

  .       Q       .       .

  .       .       .       Q

  Q       .       .       .

  .       .       Q       .

  THE SOLUTION NO: 2

  .       .       Q       .

  Q       .       .       .

  .       .       .       Q

  .       Q       .       .

 THE NUMBER OF OPTIMAL SOLUTION: 2

          ****MENU FOR N QUEEN PROBLEM****

          1. BY ITERATIVE METHOD

          2. BY RECURSIVE METHOD

          3. EXIT

          ENTER YOUR CHOICE: 2

          ENTER THE VALUE OF N:4

  THE SOLUTION NO: 1

  .       Q       .       .

  .       .       .       Q

  Q       .       .       .

  .       .       Q       .

  THE SOLUTION NO: 2

  .       .       Q       .

  Q       .       .       .

  .       .       .       Q

  .       Q       .       .

THE NUMBER OF OPTIMAL SOLUTION: 2

Share on Google Plus