class Damen
{ static int       damen=8; // damenanzahl
  static boolean[] zeileFrei;
  static boolean[] steigDiagFrei;
  static boolean[] fallDiagFrei;
  static int[]     posInSpalte; // merken, wo man ist
  static int       loesungsAnzahl=0;

  static void initArrays()
  { zeileFrei     = new boolean[damen+1];
    steigDiagFrei = new boolean[2*damen];
    fallDiagFrei  = new boolean[2*damen+1];
    posInSpalte   = new int[damen+1];
    // Erst mal alles auf true, d.h. alles frei
    for (int i=1; i<=damen; i++)     zeileFrei[i]     = true;
    for (int i=1; i<=2*damen-1; i++) steigDiagFrei[i] = true;
    for (int i=2; i<=2*damen; i++)   fallDiagFrei[i]  = true;
    for (int i=1; i<=damen; i++)     posInSpalte[i]   = 0;
  } // initArrays

  static void loesungAusgeben()
  {  for (int spalte=1; spalte<=damen; spalte++)
          Out.print(posInSpalte[spalte]);
     Out.print("  ");
     loesungsAnzahl++;
  } // loesungAusgeben

  static void setzeDame(int x, int y)
  {  zeileFrei[y] = false;
     steigDiagFrei[damen+y-x] = false;
     fallDiagFrei[x+y] = false;
     posInSpalte[x] = y;
  } // setzeDame

  static void loescheDame(int x, int y)
  {  zeileFrei[y] = true;
     steigDiagFrei[damen+y-x] = true;
     fallDiagFrei[x+y] = true;
     posInSpalte[x] = 0; // eigentlich ueberfluessig
  } // loescheDame

  static boolean nichtBedroht(int x, int y)
  { return (zeileFrei[y] &&
            steigDiagFrei[damen+y-x] &&
            fallDiagFrei[x+y]);
  } // nichtBedroht

  static void probiereDameZuSetzen(int spalte)
  {  for (int zeile=1; zeile<=damen; zeile++)
     {  if (nichtBedroht(spalte, zeile))
             { setzeDame(spalte, zeile);
               if (spalte<damen)
                    probiereDameZuSetzen(spalte+1);
               else loesungAusgeben();
               loescheDame(spalte, zeile);
             }
     } // for zeile
  } // probiereDameZuSetzen

  public static void main(String[] arg)
  { Out.println("Das Programm bestimmt alle Loesungen des N-Damen-Problems.");
    Out.print("Wie viele Damen sollen gesetzt werden? ");
    damen = In.readInt();
    initArrays();
    probiereDameZuSetzen(1); // 1. Dame in 1. Spalte setzen
    Out.println();
    Out.println("Es ergaben sich "+loesungsAnzahl+" Loesungen.");
  } // main
} // class Damen