#include <iostream>
 
const int N = 8;
int position[N];
 

// Check if a position is safe
bool isSafe(int queen_number, int row_position)
{
   // Check each queen before this one
   for (int i = 0; i < queen_number; i++) {
      // Get another queen's row_position
      int other_row_pos = position[i];
 
      // Now check if they're in the same row or diagonals
      if (other_row_pos == row_position || // Same row
          other_row_pos == row_position - (queen_number - i) || // Same diagonal
          other_row_pos == row_position + (queen_number - i))   // Same diagonal
         return false;
   }
   return true;
}
 

 
// Place N-k queens starting with queen #k
void solveNQueens(int k)
{
   if (k == N) { // We placed N-1 queens (0 included), problem solved! 
      // Solution found!
      std::cout << "Solution: [ ";
      for (int i = 0; i < N; i++) 
            std::cout << "(" << i+1 << "," << position[i]+1 << ") ";
      std::cout << "]" << std::endl;
   }
   else {
      for (int i = 0; i < N; i++) { // Generate ALL combinations
         // Before putting the k-th queen into a row, test if it is safe 
         if (isSafe(k, i))  {
            position[k] = i;
            // Place another queen
            solveNQueens(k + 1);
         }
      }
   }
}
 



int main()
{
   std::cout << "All possible Solutions ...\n" 
             << "The coordinates of the 8-queens are given as (Row,Col).\n";
   std::cout << "Note that the Rows and Colums are numbered 1--8.\n"; 

   solveNQueens(0);
 
   return 0;
}