DouKaku?

List<List<int>> list = new List<List<int>>();
int counter = 0;

int Solve(int n)
{
  List<int> numbers = new List<int>();
  for (int i = 0; i < n * n; i++) numbers.Add(i + 1);
  int sum = (1 + n * n) * n / 2;
  List<int> empty = new List<int>();
  MakeList(numbers, empty, sum, n);
  Count(numbers, list);
  return counter;
}

void MakeList(List<int> src, List<int> dst, int sum, int c)
{
  if (c == 1)
  {
    if (src.Contains(sum))
    {
      dst.Add(sum);
      list.Add(dst);
    }
    return;
  }
  for (int i = 0; i < src.Count; i++)
  {
    List<int> src2 = src.GetRange(i + 1, src.Count - i - 1);
    List<int> dst2 = dst.GetRange(0, dst.Count);
    dst2.Add(src[i]);
    MakeList(src2, dst2, sum - src[i], c - 1);
  }
  return;
}

void Count(List<int> s, List<List<int>> src)
{
  for (int i = 0; i < src.Count; i++)
  {
    List<int> s2 = s.GetRange(0, s.Count);
    src[i].ForEach(delegate(int n) { s2.Remove(n); });
    if (s2.Count == 0)
    {
      counter++;
    }
    else
    {
      List<List<int>> src2
        = src.GetRange(i + 1, src.Count - i - 1)
        .FindAll(delegate(List<int> l)
      {
        return !l.Exists(delegate(int n)
        {
          return src[i].Contains(n);
        });
      });
      Count(s2, src2);
    }
  }
}