750 8 Queens Chess Problem

Solution :

 #include<iostream>
 #include<stdio.h>

 using namespace std;

 #define max_row 8
 #define max_col 8

 int chaseboard[max_row][max_col];
 bool backTracking(int chaseboard[max_row][max_col],int column);
 void printQueensMovement(int chaseboard[max_row][max_col]);
 bool isSafe(int chaseboard[max_row][max_col],int row,int col);
 void printSolution();
 bool isHeaderPrint = false;
 int sourceX,sourceY;
 int laxographicalOutput[201][201];
 int numberOfSolutionPerTestCase;


 int main()
 {
  int tc,T;
  freopen("750.txt","r",stdin);

  cin>>T;
  for(tc=0;tc<T;tc++)
  {
  
   for(int x=0; x <8; x++) {
    for(int y=0; y <8; y++) {
     chaseboard[x][y] = 0;
    }
   }

   sourceX=sourceY=0;

   cin >> sourceX >> sourceY;
   sourceX=sourceX-1;
   sourceY=sourceY-1;
   //chaseboard[sourceX][sourceY] = 1;
  
   numberOfSolutionPerTestCase = 0;
   isHeaderPrint = false;
  
   backTracking(chaseboard,0);
   printSolution();

   if(tc<T-1){
      cout << endl;
   }

  }
  return 0;
 }

 bool backTracking(int chaseboard[max_row][max_col],int column)
 {
  if(column == max_col)
  {
   if(chaseboard[sourceX][sourceY])
   {
    printQueensMovement(chaseboard);
   }

   return true;
  }

  for(int i=0;i<max_row;i++)
  {
   if(isSafe(chaseboard,i,column))
   {
    chaseboard[i][column]=1; //set 
    backTracking(chaseboard,column+1);
    chaseboard[i][column]=0; //unset
   }
  }

  return false;
 }

 bool isSafe(int chaseboard[max_row][max_col],int row,int col)
 {
  int i,j;

  //Row Check
  for(i=0;i<row;i++)
  {
   if(chaseboard[i][col] == 1) return false;
  }

  //Column Check
  for(i=0;i<col;i++)
  {
   if(chaseboard[row][i] == 1) return false;
  }
 
  //left most upper diag 
  for(i=row,j=col;i>=0 && j>=0;i--,j--)
  {
   if(chaseboard[i][j] == 1) return false;
  }

  //left most lower diag 
  for(i=row,j=col; i<max_row && j>=0;i++,j--)
  {
   if(chaseboard[i][j] == 1) return false;
  }
 
  return true;
 }

 void printQueensMovement(int chaseboard[max_row][max_col])
 {
  int i,j;
 
  for(i=0;i<max_row;i++)
  {
   for(j=0;j<max_col;j++)
   {
    if(chaseboard[i][j] == 1)
    {
     laxographicalOutput[numberOfSolutionPerTestCase][j] = i+1;
    }
   }
  }
  numberOfSolutionPerTestCase++;
 }

 void printSolution()
 {
  int i,j;
  if(numberOfSolutionPerTestCase<=0) return;
  if(!isHeaderPrint)
  {
   cout << "SOLN       COLUMN"<<endl;
   cout <<" #      1 2 3 4 5 6 7 8"<<endl<<endl;
   isHeaderPrint = true;
  }

  int solFlag=1;
  for(i=1;i<=numberOfSolutionPerTestCase;i++)
  {
   if(solFlag<10) cout <<" ";
   cout<< solFlag++ <<"      "<<laxographicalOutput[i-1][0]<<" "<<laxographicalOutput[i-1][1]<<" "<<laxographicalOutput[i-1][2]<<" "<<laxographicalOutput[i-1][3]<<" "<<laxographicalOutput[i-1][4]<<" "<<laxographicalOutput[i-1][5]<<" "<<laxographicalOutput[i-1][6]<<" "<<laxographicalOutput[i-1][7]<<endl;
  }
 
  if(solFlag<numberOfSolutionPerTestCase)
   cout<<endl;
 }