Computer Science: 5th sem ADA Lab Program 14

Analysis and Design of Algorithms Lab.

Question 14.

//Implement N Queen's problem using backtracking.

#include <iostream>
#include <conio.h>

using namespace std;

bool isPossible(int *arr,int k)
{
for(int i=1;i<k;i++)
if(arr[k]==arr[i] || i-arr[i]==k-arr[k] || i+arr[i]==k+arr[k])
return false;
return true;
}
int queen(int n)
{
int x[10],count=0,k=1;
x[k]=0;

while(k!=0)
{
x[k]+=1;
while(x[k]<=n && !isPossible(x,k))
x[k]+=1;
if(x[k]<=n)
{
if(k==n)
{
count++;
cout<<"\nSolution"<<count;
for(int j=1;j<=n;j++)
{
cout<<"\n";
for(int k=1;k<=n;k++)
if(x[j]==k)
cout<<"q ";
else
cout<<"- ";
}
}
else
{
k++;
x[k]=0;
}
}
else
k--;
}

return 1;
}
void main()
{
cout<<"Enter the size of board:";int n;cin>>n;

int *arr=new int[n];
for(int i=0;i<n;i++)
arr[i]=-1;

queen(n);
getch();
}