/************************************************
Grundlegende Algorithmen mit Java,
http://algorithmen-und-problemloesungen.de/
Copyright @2007-2009 by Doina Logofatu

in C#: Michael Gärtner
************************************************/


using System;
using System.IO;

namespace Logofatu
{
    class P01NQueens
    {
        private static String FileOutputName = "nQueens.out";

        static void Main(string[] args)
        {
            StreamWriter sw = new StreamWriter(FileOutputName);
            try
            {
                Console.Write(" n = ");
                int n = int.Parse(Console.ReadLine());

                int noSol = 0;
                int[] x = new int[n];
                int k = 0;
                x[k] = -1;
                while ( k >= 0 )
                {
                    bool flag = false;
                    while ( !flag && x[k] < n - 1 )
                    {
                        x[k]++;
                        flag = true;
                        for ( int i = 0; i < k; i++ )
                            if ( x[i] == x[k] || Math.Abs(x[i] - x[k]) == k - i )
                                flag = false;
                    }
                    if ( flag )
                    {
                        if ( k == n - 1 )
                        {
                            foreach ( int i in x )
                            {
                                sw.Write(i + 1);
                                sw.Write(' ');
                            }
                            sw.WriteLine();
                            noSol++;
                        }
                        else
                            x[++k] = -1;
                    }
                    else
                        k--;
                }
                sw.Write(n);
                sw.Write(' ');
                sw.WriteLine(noSol);               
            }
            catch ( IOException ex )
            {
                Console.WriteLine("Fehler bei der Dateiverarbeitung!\n" + ex);
            }
            finally
            {
                sw.Close();
            }
        }
    }
}