// This... erm... "program" solves the following problem 
// by exhaustive search:
// 
//   Find a number consisting of 9 digits in which each of the digits
//   from 1 to 9 appears only once. This number must also satisfy these
//   divisibility requirements:
//
//     1. The number should be divisible by 9.
//     2. If the rightmost digit is removed, the remaining number 
//        should be divisible by 8.
//     3. If the rightmost digit of the new number is removed, 
//        the remaining number should be divisible by 7.
//     4. And so on, until s only one digit (which will necessarily 
//        be divisible by 1).
//
// Author: karoly@lorentey.hu, 2010-04-20.
//
// To compile this, you'll need a recent C++ compiler supporting C++0x
// variadic templates.
// 
// Sample command line for GCC 4.4:
//
// g++ -Wall -ftemplate-depth-2000 -std=c++0x -o 9digits 9digits.cc


#include <iostream>

// value<DIGITS>::v is the value of DIGITS in decimal.
// The list starts with the least significant digit.
template<int... digits>
struct value;

template<>
struct value<> 
{
  static const int v = 0;
};

template<int first, int... rest>
struct value<first, rest...>
{
  static int const v = 10 * value<rest...>::v + first;
};


// contains<ELEM, SET>::v is true if ELEM is in SET.
template<int elem, int... set>
struct contains;

template<int elem>
struct contains<elem>
{
  static const bool v = false;
};

template<int elem, int first, int... rest>
struct contains<elem, first, rest...>
{
  static const bool v = elem == first || contains<elem, rest...>::v;
};

// divisor_test<DIGITS>::v is true if the number of digits 
// in DIGITS is a divisor of their decimal value.
template<int... digits>
struct divisor_test;

template<>
struct divisor_test<>
{
  static const bool v = true;
};

template<int first, int... rest>
struct divisor_test<first, rest...>
{
  static const int num = value<first, rest...>::v;
  static const int div = sizeof...(rest) + 1;
  static const int mod = num % div;
  
  static const bool v = mod == 0;
};

// test_candidate<FIRST, REST>::v is true if cons(FIRST, REST) satisfies 
// all constraints, assuming that REST already does.
template<int first, int... rest>
struct test_candidate 
{
  static const bool v = (divisor_test<first, rest...>::v 
                         && !contains<first, rest...>::v);
};

// search<LENGTH, DIGITS>::v is the first number that is greater or 
// equal to the decimal value of DIGITS, satisifies all constraints
// and is of the given LENGTH.  (-1 if there is no such number.)
template<int length, int... digits>
struct search;

template<int length, bool good, bool final, int digit, int... rest>
struct search_i
{
  static const int v = search<length, digit + 1, rest...>::v;
};

template<int length, int digit, int... rest>
struct search_i<length, true, true, digit, rest...>
{
  static const int v = value<digit, rest...>::v;
};

template<int length, int digit, int... rest>
struct search_i<length, true, false, digit, rest...>
{
  static const int v = search<length, 1, digit, rest...>::v;
};

template<int length, int digit, int... rest>
struct search<length, digit, rest...>
{
  static const bool good = test_candidate<digit, rest...>::v;
  static const bool final = good && 1 + sizeof...(rest) == length;
  
  static const int v = search_i<length, good, final, digit, rest...>::v;
};

template<int length>
struct search<length, 10>
{
  static const int v = -1;
};

template<int length, int next, int... rest>
struct search<length, 10, next, rest...>
{
  static const int v = search<length, next + 1, rest...>::v;
};

template<int length>
struct search<length>
{
  static const int v = search<length, 1>::v;
};

// This program eats cute kittens for breakfast.
int
main ()
{
  std::cout << search<9>::v << '\n';
  return 0;
}