#include <cstdlib>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

/**
   Problem ośmiu hetmanów.
*/
class Queen
{
public:
   /**
      Konstruuje hetmana na podanej pozycji.
      @param r rząd
      @param c kolumna
   */
   Queen(int r, int c);

   /**
      Sprawdza, czy ten hetman atakuje drugiego.
      @param other drugi hetman
      @return wartość true, jeśli oba hetmany znajdują się w tym samym
      rzędzie lub kolumnie albo na jednej przekątnej
   */
   bool attacks(Queen other) const;

   /**
      Wypisuje położenie hetmana.
   */
   void print() const;

private:
   int row;
   int column;   
};

Queen::Queen(int r, int c)
{
   row = r;
   column = c;
}

bool Queen::attacks(Queen other) const
{
   return row == other.row
      || column == other.column
      || abs(row - other.row) == abs(column - other.column);
}

void Queen::print() const
{ 
   cout << "abcdefgh"[column] << row + 1; 
}

const int NQUEENS = 8;

const int ACCEPT = 1;   // przyjęcie
const int ABANDON = 2;  // porzucenie
const int CONTINUE = 3; // kontynuacja

/**
   Rozwiązanie częściowe dla zagadki ośmiu hetmanów
*/
class PartialSolution
{
public:
   /**
      Bada rozwiązanie częściowe.
      @return jedna ze stałych ACCEPT, ABANDON, CONTINUE
   */
   int examine() const;
   
   /**
      Zwraca wszystkie warianty rozszerzenia tego rozwiązania częściowego.
      @return wektor rozwiązań częściowych rozszerzających to rozwiązanie
   */
   vector<PartialSolution> extend() const;

   /**
      Wypisuje rozwiązanie częściowe.
   */
   void print() const;

private:
   vector<Queen> queens;
};

int PartialSolution::examine() const
{
   for (int i = 0; i < queens.size(); i++)
   {
      for (int j = i + 1; j < queens.size(); j++)
      {
         if (queens[i].attacks(queens[j])) { return ABANDON; }
      }
   }
   if (queens.size() == NQUEENS) { return ACCEPT; }
   else { return CONTINUE; }
}

vector<PartialSolution> PartialSolution::extend() const
{
   vector<PartialSolution> result;
   // Następny rząd do uzupełnienia
   int row = queens.size();
   // Wygeneruj nowe rozwiązanie dla każdej z kolumn.
   for (int column = 0; column < NQUEENS; column++)
   {
      PartialSolution extended;
      // Skopiuj wszystkie hetmany z danego rozwiązania.
      extended.queens = queens; 
      // Dodaj nowego hetmana.
      extended.queens.push_back(Queen(row, column));
      result.push_back(extended);
   }
   return result;
}

void PartialSolution::print() const
{
   for (int i = 0; i < queens.size(); i++)
   {
      if (i > 0) { cout << ", "; }
      queens[i].print();
   }
   cout << endl;
}

/**
   Wypisuje wszystkie rozwiązania problemu stanowiące rozszerzenie
   danego rozwiązania częściowego.
   @param sol rozwiązanie częściowe
*/
void solve(PartialSolution sol)
{
   int exam = sol.examine();
   if (exam == ACCEPT) 
   { 
      sol.print();
   }
   else if (exam == CONTINUE)
   {
      vector<PartialSolution> extended = sol.extend();
      for (int i = 0; i < extended.size(); i++)
      {
         solve(extended[i]);
      }
   }
}

int main()
{
   PartialSolution initial;
   solve(initial);
   return 0;
}

