import Prog1Tools.IOTools;
public class Achtdamen {
   //
   static int z = 1;
  // Testet, ob eine der Damen eine andere schlagen kann. //
  //  ----------------------------------------------------
  public static boolean bedroht(int[] brett, int spalte) {
    // Teste als Erstes, ob eine Dame in derselben Zeile steht
    for (int i=0; i < spalte; i++)
      if (brett[i] == brett[spalte])
        return true;

    // Teste nun, ob in der oberen Diagonale eine Dame steht
    for (int i = spalte-1, j = brett[spalte]-1; i >= 0; i--,j--)
      if (brett[i] == j)
        return true;

    // Teste, ob in der unteren Diagonale eine Dame steht
    for (int i = spalte-1, j = brett[spalte]+1; i >= 0; i--,j++)
      if (brett[i] == j)
        return true;

    // Wenn das Programm hier angekommen ist, steht die Dame "frei"
    return false;
  }


  /** Sucht rekursiv eine Loesung des Problems. */
  //  -----------------------------------------
  public static void suche(int[] brett, int spalte) {
    // Sind wir fertig?
    if (spalte ==  brett.length) {
          Ausgabe(brett);
          return ;
    }
    //
    // Suche die richtige Position fuer die naechste Dame
    //
    for (int i=0; i < brett.length; i++) {
      brett[spalte] = i;         // Probiere jede Stelle aus
      if (!bedroht(brett,spalte)) // Falls die Dame nicht frei steht
         suche(brett,spalte+1);   // Teste die folgenden Spalten
      }
    // Wenn das Programm hier angekommen ist,
    // stecken wir in einer Sackgasse
  }
  //
  //
  // Gibt das Schachbrett auf dem Bildschirm aus. //
  //  
  //
 public static void Ausgabe(int[  ] brett) {
 int i = 0;
 System.out.print(z+ ".  ");
 z++;
 while (i < brett.length) {
    System.out.print(" " + brett[i]);
    i++; 
    }
 System.out.println( );     
 }      
  //
  //
  // Initialisiert das Schachbrett und
  //   ruft die Methode "setze" auf 
  //  
  public static void main(String[] args) {
    int n,i ;
    n = IOTools.readInteger("n einlesen  " );
    int[] feld = new int[n] ; // Deklariere das Spielfeld
    // 
    i= 0;
    while (i < feld.length){
    feld[i] = 0;
    i++;
    }
    //
    suche(feld,0); // Starte die Suche am linken Rand
    
  }
}