class Nikolaus
{ static final int   maxPunktAnz=5;
  static final int   maxKantenAnz=8;
  static boolean[][] kanteZulaessig;
  static boolean[][] kanteGezeichnet;
  static int[]       loesungsWeg;
  static int         aktKantenAnzahl = 0;
  static int         loesungsAnzahl = 0;

  static void initArrays()
  { kanteZulaessig  = new boolean[maxKantenAnz+1][maxKantenAnz+1];
    kanteGezeichnet = new boolean[maxKantenAnz+1][maxKantenAnz+1];
    loesungsWeg     = new int[maxKantenAnz+2]; // mit Startpunkt
    // Erst mal alles auf false;
    for (int i=1; i<=maxPunktAnz; i++)
    {  for (int k=1; k<=maxPunktAnz; k++)
       {  kanteZulaessig[i][k] = false;
          kanteGezeichnet[i][k] = false;
       } // for k
    } // for i
    /* Zulaessige Kanten fuer das "Haus des Nikolaus"
       eintragen. Der Nummerierung liegt das Bild in main
       zu Grunde.
       Eine Anpassung an andere Graphen ist leicht moeglich.
    */
    kanteZulaessig[1][2] = true; // von 1 nach 2 zulaessig
    kanteZulaessig[1][3] = true;
    kanteZulaessig[1][5] = true;
    kanteZulaessig[2][1] = true;
    kanteZulaessig[2][3] = true;
    kanteZulaessig[2][5] = true;
    kanteZulaessig[3][1] = true;
    kanteZulaessig[3][2] = true;
    kanteZulaessig[3][4] = true;
    kanteZulaessig[3][5] = true;
    kanteZulaessig[4][3] = true;
    kanteZulaessig[4][5] = true;
    kanteZulaessig[5][1] = true;
    kanteZulaessig[5][2] = true;
    kanteZulaessig[5][3] = true;
    kanteZulaessig[5][4] = true;
    for (int i=0; i<=maxKantenAnz; i++)
      loesungsWeg[i] = 0;
  } // initArrays

  static void zeichneKante(int von, int nach)
  {  kanteGezeichnet[von][nach] = true;
     kanteGezeichnet[nach][von] = true;
     aktKantenAnzahl++;
     loesungsWeg[aktKantenAnzahl] = nach;
  } // zeichneKante

  static void loescheKante(int von, int nach)
  {  kanteGezeichnet[von][nach] = false;
     kanteGezeichnet[nach][von] = false;
     aktKantenAnzahl--;
  } // loescheKante

  static boolean fertig()
  { return (aktKantenAnzahl==maxKantenAnz);
  } // fertig

  static void loesungAusgeben()
  { for (int i=0; i<=maxKantenAnz; i++)
      Out.print(loesungsWeg[i]);
    Out.print(" ");
    loesungsAnzahl++;
    if (loesungsAnzahl%5==0)
         Out.println();
  } // loesungAusgeben

  static void versucheKanteZuZeichnen(int start)
  { for (int ziel=1; ziel<=maxPunktAnz; ziel++)
    {  if (kanteZulaessig[start][ziel] &&
           !kanteGezeichnet[start][ziel])
            {  zeichneKante(start, ziel);
               if (!fertig())
                    versucheKanteZuZeichnen(ziel);
               else loesungAusgeben();
               loescheKante(start, ziel);
            }
    } // for ziel
  } // versucheKanteZuZeichnen

  public static void main(String[] arg)
  { initArrays();
    Out.println("Das Programm bestimmt alle Loesungen des Problems,");
    Out.println("das \"Haus des Nikolaus\" in einem Zug zu zeichnen.");
    Out.println("      4     ");
    Out.println("     . .    ");
    Out.println("    .   .   ");
    Out.println("   5-----3  ");
    Out.println("   |.   .|  ");
    Out.println("   | . . |  ");
    Out.println("   | . . |  ");
    Out.println("   |.   .|  ");
    Out.println("   1-----2  ");
    Out.print("Mit RETURN geht es los!");
    String quatsch = In.readLine();
    for (int punktNr=1; punktNr<=maxPunktAnz; punktNr++)
    {  loesungsWeg[0] = punktNr;
       versucheKanteZuZeichnen(punktNr);
    } // for punktNr
    Out.println();
    Out.println("Es ergaben sich "+loesungsAnzahl+" Loesungen.");
  } // main
} // class Nikolaus