eight queen problem using recursion

#include<iostream>
using namespace std;

int Queens_totl=0; //globally defined since its involvemnt is needed in the every function and in the main as well
bool position(int **arr,int row,int col)
{

for(int i=0;i<col;i++)
{
if(arr[row][i]==1)
return false;
}
for(int i=row,j=col;i>=0 && j>=0;i--,j--)
{
if (arr[i][j]==1)
{
return false;
}
}
for(int i=row,j=col;j>=0 && i<Queens_totl;i++,j--)
{
if(arr[i][j]==1)
return false;
}
return true;
}
bool occupy_space(int **arr,int col)
{
if(col>=Queens_totl) //base case
{
return true;
}
for(int i=0;i<Queens_totl;i++)
{
if(position(arr,i,col))
{
arr[i][col]=1;
if(occupy_space(arr,col+1))
{
return true;
}
arr[i][col]=0;
}
}
return false;
}
void Queens_bord(int ** arr)
{
int j=0;
for(int i=0;i<Queens_totl;i++)
{
for( j=0;j<Queens_totl;j++)
cout<<"\t"<<arr[i][j]<<" ";
cout<<endl;  
}
}
void main()
{
cout<<"Please ! Enter the number of queens \n";
cin>>Queens_totl;
int **arr=NULL;
arr=new int*[Queens_totl];
for(int i=0;i<Queens_totl;i++)
{
arr[i]=new int [Queens_totl]();
}

if(!occupy_space(arr,0))
{
cout<<"Sorry your input is not correct please restart the program \n"<<endl;
}
Queens_bord(arr);
system("pause");
}

Comments

Popular Posts