// eight_queens.cpp   demonstrate recursive use of objects
// place eight queens on a chess board so they do not attack each other

#include <iostream>
using namespace std;

class Queen    // in main()  LastQueen is head of the list
{              //            of queen objects
  public:
    Queen(int C, Queen *Ngh);
    int First(void);
    void Print(void);
  private:
    int CanAttack(int R, int C);   // private member functions
    int TestOrAdvance(void);       // just used internally
    int Next(void);                // try next Row

    int   Row;                     // Row for this Queen
    int   Column;                  // Column for this Queen
    Queen *Neighbor;               // linked list of Queens
};


Queen::Queen(int C, Queen *Ngh)    // normal constructor
{
  Column = C;                      // Column will not change
  Row = 0;                         // Row will be computed
  Neighbor = Ngh;                  // linked list of Queen objects
}

int Queen::First(void)
{
  Row = 1;
  if (Neighbor && Neighbor -> First())  // order is important
  {                                     // note recursion
    return TestOrAdvance();
  }
  return 1;
}

void Queen::Print(void)
{
  if(Neighbor)
  {
    Neighbor -> Print();   // recursively print data inside all Queens
  }
  cout << "column " << Column << "  row " << Row << endl;
}

int Queen::TestOrAdvance(void)
{
  if(Neighbor && Neighbor -> CanAttack(Row, Column))
  {
    return Next();   // the member function 'next' does the 'advance'
  }
  return 1;
}

int Queen::CanAttack(int R, int C) // determine if this queen attacked
{
  int Cd;
  if (Row == R) return 1;      // a set of rules that detect in same
  Cd = C - Column;             // row or column or diagonal
  if((Row+Cd == R) || (Row-Cd == R)) return 1;
  if(Neighbor)
  {
    return Neighbor -> CanAttack(R, C);  // recursive
  }
  return 0;
}

int Queen::Next(void)   // advance Row but protect against bugs
{
  if (Row == 8)
  {
    if (!(Neighbor && Neighbor->Next()))
      return 0;
    Row = 0;
  }
  Row = Row + 1;
  return TestOrAdvance();
}

int main()
{
  Queen *LastQueen = 0;

  for ( int i=1; i <= 8; i++)             // initialize
  {
    LastQueen = new Queen(i, LastQueen);
  }

  if (LastQueen -> First())               // solve problem
  {
    LastQueen -> Print();                 // print solution
  }
  return 0;                               // finished
}

// output of execution is:
// column 1  row 1
// column 2  row 5
// column 3  row 8
// column 4  row 6
// column 5  row 3
// column 6  row 7
// column 7  row 2
// column 8  row 4