#include <iostream>

enum {
	N = 5
};

struct nil { };

template <int car_, class cdr_>
struct cons {
	static const int car = car_;
	typedef cdr_ cdr;
};

std::ostream&
operator<<(std::ostream& o, const nil&)
{
	return o;
}

template <int car_, class cdr_>
std::ostream&
operator<<(std::ostream& o, const cons<car_, cdr_>&)
{
	return o << car_ << " " << cdr_();
}

template<class list, int n>
struct nth
{
	static const int val = nth<typename list::cdr, n - 1>::val;
};

template<class list>
struct nth<list, 0>
{
	static const int val = list::car;
};

template<class list, int n>
struct append
{
	typedef cons<list::car, typename append<typename list::cdr, n>::val> val;
};

template <int n>
struct append<nil, n>
{
	typedef cons<n, nil> val;
};

template<class queens, int row, int col, int r>
struct foo 
{
	static const int val = !(nth<queens, r>::val == col
	  || nth<queens, r>::val - r == col - row
	  || N - 1 - nth<queens, r>::val - r == N - 1 - col - row)
	  && foo<queens, row, col, r - 1>::val;
};

template<class queens, int row, int col>
struct foo<queens, row, col, -1>
{
	static const int val = 1;
};

template<class queens, int row, int c>
struct bar;

template<int valid, class queens, int row>
struct baz : bar<queens, row, N  - 1>
{ };

template<class queens, int row>
struct baz<0, queens, row>
{ };

template<class queens>
struct baz<1, queens, N>
{
	baz() {
		std::cout << queens() << "\n";
	}
};

template<class queens, int row, int c>
struct bar
  : baz<
      foo<queens, row, c, row - 1>::val,
      typename append<queens, c>::val,
      row + 1>
  , bar<queens, row, c - 1>
{ };

template<class queens, int row>
struct bar<queens, row, -1>
{ };

baz<1, nil, 0> frob;

int
main()
{ }