public class uke_7_3
{
    int n;            // Problemstørrelse
    int p[];          // Lagrer permutasjonene
    boolean brukt[];  // Merker av brukte tall
    int antUnikeLoes; // Antall unike løsninger funnet

    // Konstruktør
    public uke_7_3(int n)
    {
	this.n = n;
	p = new int[n];
	brukt = new boolean[n];
	for (int i = 0; i < n; i++)
	    brukt[i] = false;
	antUnikeLoes = 0;   
    }
    
    void lagLoesning(int rad)
    {
	// Lager alle mulige løsninger på dronningproblemet fra og med
	// denne raden og ned til rad n-1. Det er allerede satt ut
	// dronninger på radene 0, 2, ..., rad-1

	if (rad == n)
	{
	    // Laget ferdig en løsning
	    skrivLoesning();
	}
	else
	{
	    // Setter etter tur dronninger inn på alle ledige
	    // kolonner i denne raden, sjekker om den kan
	    // slås av dronningene ovenfor, hvis ikke går vi
	    // rekursivt videre til neste rad 

	    for (int kol = 0; kol < n; kol++)
	    {
		if (!brukt[kol] && lovligPlassering(rad, kol))
		{
		    p[rad] = kol;
		    brukt[kol] = true;
 
		    lagLoesning(rad + 1);
		      
		    brukt[kol] = false;
		}
	    }
	}
    }

    boolean lovligPlassering(int rad, int kol)
    {
	// Sjekker om dronningene i ovenstående rader kan
	// slå utplassert dronning diagonalt

	int k1 = kol, k2 = kol;
	for (int r = rad-1; r >= 0; r--)
	{
	    k1--;
	    k2++;
	    if (k1 >= 0 && p[r] == k1)
		return false;
	    if (k2 < n && p[r] == k2)
		return false;
	}
	    return true;
    }

    boolean tidligereLoesning(int q[])
    {
	// Returnerer true hvis q representer en løsning
	// som er *mindre enn* den vi nå har funnet i
	// permutasjonsvektoren p. Siden vi lager løsningene
	// i stigende rekkefølge, vil dette sikre at vi bare
	// skriver ut den minste av løsningene i hver gruppe
	// av løsninger som er speilinger/rotasjoner av 
	// hverandre

	int i = 0;
	while (q[i] == p[i] && i < n-1)
	    i++;
	if (q[i] < p[i])
	    return true;
	return false;
    }

    void skrivLoesning()
    {
	// Skriver ut en løsning av dronningproblemet
	// Filtrerer ut løsninger som er speilinger eller
	// rotasjoner av en løsning som allerede er funnet

	int p1[] = new int[n];
	int p2[] = new int[n];
	int p3[] = new int[n];
	int p4[] = new int[n];
	int p5[] = new int[n];
	int p6[] = new int[n];
	int p7[] = new int[n];
	
	// Lager de syv speilingene/rotasjonene

	int N = n-1;
	for (int i = 0; i < n; i++)
	{
	    p1[p[i]]     = i;
	    p2[N - p[i]] = N - i;
	    p3[N - i]    = p[i];
	    p4[i]        = N - p[i];
	    p5[N - p[i]] = i;
	    p6[N - i]    = N - p[i];
	    p7[p[i]]     = N - i;
	}

	// Sjekker om noen av speilingene/rotasjonene er
	// skrevet ut tidligere

	if (tidligereLoesning(p1) || tidligereLoesning(p2) ||
	    tidligereLoesning(p3) || tidligereLoesning(p4) ||
	    tidligereLoesning(p5) || tidligereLoesning(p6) ||
	    tidligereLoesning(p7))
	    return;

	for (int i = 0; i < n; i++)
	    System.out.print((p[i]+1) + " ");
	System.out.println();
	
	antUnikeLoes++;
    }

    public static void main(String args[])
    {
	// Leser n fra kommandolinjen
	int n = Integer.parseInt(args[0]);

	// Skriver ut alle løsninger på dronningproblemet
	if (n > 0 && n < 16)
	{
	    
	    uke_7_3 D = new uke_7_3(n);
	    D.lagLoesning(0);
	    System.out.println("Antall løsninger: " + D.antUnikeLoes);
	}
	else
	    System.out.println("Bruk 0 < n < 16");
    }
}