#include <iostream>

// just to prevent a name conflict with the symbol remove in stdio.h
// with the gcc
namespace { 

// a generic null
struct null {};

// select a type with a boolean expression
template <class A, class B, bool>
struct select {
  typedef A result;
};

template <class A, class B>
struct select<A,B,true> {
  typedef B result;
};

// Sets
template <int I>
struct item { 
  enum {id = I}; 
  typedef item<I-1> next;
};

template <class H, class T>
struct node {
  typedef H         head;
  typedef T         tail;
};

// Build a linked list with I+1 items
template <int I>
struct set {
  typedef node<item<I>, typename set<I-1>::value > value;
};

template <>
struct set<-1> { 
  typedef null value;
};

// test if an item is in a set
template <class List, class Item> 
struct inSet;

template <class Tail, class Item>
struct inSet<node<Item,Tail>, Item> {
  enum { result = 1};
};

template <class Head, class Tail, class Item>
struct inSet<node<Head, Tail>, Item> {
  enum { result = inSet<Tail, Item>::result};
};

template <class Item>
struct inSet<null, Item> {
  enum { result = 0};
};

// remove an item from a given set
template <class List, class Item> struct remove;

template <class List, class Item>
struct remove<node<Item, List>, Item> {
  typedef List result;
};

template <class Head, class Tail, class Item>
struct remove<node<Head, Tail>, Item> {
  typedef node<Head,
    typename remove<Tail, Item>::result> result;
};

template <class Item>
struct remove<null, Item> {
  typedef null result;
};

// size of the chessboard  
const int size = 8;

// some bookkeeping
template <class C, class F, class S>
struct state {
  typedef C            columns;
  typedef F            first_diag;
  typedef S            second_diag;
  typedef state<C,F,S> this_type;

  template <class Col, class Row> struct calc_diag {
    typedef item<Row::id + Col::id> first_d;
    typedef item<size - 1 - Row::id + Col::id> second_d;
  };

  template <class Col, class Row> struct isValid : calc_diag<Col,Row>  {
    static const bool result = 
      inSet<columns, Col>::result &&
      inSet<first_diag, first_d>::result &&
      inSet<second_diag, second_d>::result ;
  };

  template <class Col, class Row> struct use : calc_diag<Col,Row> {
    typedef typename select <
      null, 
      state< 
        typename remove<columns, Col>::result,
        typename remove<first_diag, first_d>::result,
        typename remove<second_diag, second_d>::result>,
        this_type::isValid<Col, Row>::result >::result result;
  };
};

// the algorithm
template <class State, class Column, class Row>
struct solution {
  // the new state after applying Column and Row
  typedef typename State::use<Column, Row>::result newState;

  // the next two possible steps
  typedef solution<newState,
                 item<size-1>,
                 typename Row::next> 
     tryNextRow;

  typedef solution<State, 
                 typename Column::next, 
                 Row>
     tryNextColumn;

  // can we place a queen here ?
  typedef typename State::isValid<Column, Row> checker;
  enum { thisValid = checker::result };

  // which one to use?
  enum { useNextRow   = 
         (thisValid && tryNextRow::isValid) };

  typedef typename 
    select<tryNextColumn, tryNextRow, useNextRow>::result 
    nextStep;

  enum { isValid  = nextStep::isValid};

  // resulting row/column
  enum { row    = Row::id };
  enum { column = Column::id };
};

template <class Row, class Column>
struct solution<null, Row, Column> {
  enum { isValid = 0 };
  typedef null nextStep;
};

template <>
struct solution<null, item<-1>, item<-1> > {
  enum { isValid = 0 };
  typedef null nextStep;
};

template <class Row>
struct solution<null, item<-1>, Row > {
  enum { isValid = 0 };
  typedef null nextStep;
};

template <class Row>
struct solution<null, Row, item<-1> > {
  enum { isValid = 0 };
  typedef null nextStep;
};

template <class State, class Row>
struct solution<State, item<-1>, Row> {
  enum { isValid = 0 };
  typedef null nextStep;
};

template <class State, class Column>
struct solution<State, Column, item<-1> > {
  enum { isValid = 1, useNextRow = 0 };
  typedef null nextStep;
  
};

template <class Solution = 
    solution<
      state<set<size-1>::value,
            set<2*size-2>::value,
            set<2*size-2>::value>,
      item<size-1>, item<size-1> > 
    >
struct queen : queen<typename Solution::nextStep> 
{
  template <bool, class ASolution>
  struct print {
    static void it() {}
  };

  template <class ASolution>
  struct print<true,ASolution> {
    static void it() {
      std::cout<<" ";
      std::cout<<static_cast<char>( 'a' + ASolution::column );
      std::cout<<static_cast<char>( '1' + ASolution::row );
    }
  };

  queen() {
    print<Solution::useNextRow,Solution>::it();
  }
};

template <> struct queen<null> {
  queen() {
    std::cout<<"Result:";
  }
};

} // namespace {

int main() {
  queen<> Queen;
}