B a c k t r a c k i n g

Beispielprogramm 2:   pisces escheri



PROGRAM             pisces_escheri;  {
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
HMO ludens, Warendorf, 27.6.1988, ein Beispiel für  BACKTRACKING.

M.C.Escher hat auf einer Kugeloberfläche 12 Fische so angeordnet, daß sie
eine Parkettierung der Oberfläche bilden. Die Kugel von Escher haben Doris
Schattschneider und Wallace Walker zu einem Würfel deformiert, der mit dem
gleichen Fischmuster bedeckt ist. Viermal stoßen 3 Fische jeweils mit den
Schwanzflossen zusammen und viermal stoßen 3 Fische jeweils mit der Rücken-
flosse zusammen. Dies raffinierte Muster muß man sehen !

Das Muster soll jetzt so gefärbt werden, daß
-  jeder Fisch eine Farbe erhält,
-  benachbarte Fische unterschiedliche Farben haben,
-  genau vier Farben verwendet werden.

Bei 12 Fischen in 4 Farben liefert die Kombinatorik   4^12 = 16.777.216
Möglichkeiten. Darunter dürften die meisten nicht die Bedingungen erfüllen.
Es ergeben sich genau 240 Lösungen, von den aber die meisten zueinander
symmetrisch sind. }

CONST N               =  12;    { Gegeben sind 12 Fische }
      farbenanzahl    =  4;     { Gesucht ist eine Lösung mit 4 Farben }
      auswahlanfang   =  1;
      auswahlende     =  farbenanzahl;
TYPE  inzidenztyp     =  SET OF 0..N;
      vektortyp       =  ARRAY [0..N] OF 0..farbenanzahl;
CONST {Aus dem vorgelegten Muster der 12 Fische, ergibt sich, daß jeder Fisch
       5 andere berührt. Die Fische werden (willkürlich) mit Nummern von 1 bis
       12 markiert. In der Menge "inzidenzen[i]" sind alle die Nummern der
       Fische enthalten, die den Fisch mit Nummer i berühren.}
      inzidenzen      :  ARRAY [1..12] OF inzidenztyp
                      = ([2,3,4,5,6],   [1,3,6,7,8],   [1,2,5,8,9],
                         [1,5,6,10,11], [1,3,4,9,10],  [1,2,4,7,11],
                         [2,6,8,11,12], [2,3,7,9,12],  [3,5,8,10,12],
                         [4,5,9,11,12], [4,6,7,10,12], [7,8,9,10,11]);
      farbbezeichnung :  ARRAY [1..farbenanzahl] OF String[4]
                      = ('rot', 'blau', 'gelb', 'grün');
VAR   zaehler         :  Integer;
      vektor          :  vektortyp;

  { T }
  PROCEDURE try (stufe: Integer; vektor: vektortyp);
  VAR wahl         : Integer;
      lebend       : Boolean;
      neues_optimum: Boolean;

    { T.1 }
    PROCEDURE vektor_bewerten;
    { Es muß nur geprüft werden, ob die Farbe bei Position k im Vektor
      nicht gleich den Farben der benachbarten bereits gesetzten Fische ist. }
    VAR i,k: Integer;
    BEGIN
      k:=vektor[0]; lebend:=TRUE; i:=1;
      WHILE (i<k) AND lebend DO
      BEGIN
        IF (vektor[i] = vektor[k]) AND (i IN inzidenzen[k])
           THEN lebend:=FALSE;
        i:=i+1
      END;
      neues_optimum:=lebend
    END;

    { T.2 }
    FUNCTION vollstaendig: Boolean;
    BEGIN  vollstaendig := (vektor[0]=N)  END;

    { T.3 }
    PROCEDURE loesung_speichern;
    { Speichern entfällt, stattdessen wird eine Lösung ausgegeben }
    VAR i: Integer;
    BEGIN
      zaehler:=zaehler+1; { zaehler für die Lösungen, global! }
      Write(zaehler:2,' : ');
      FOR i:=1 TO N DO Write(farbbezeichnung[vektor[i]]:5); Writeln
    END;

  BEGIN { T }
    FOR wahl:=auswahlanfang TO auswahlende DO
    BEGIN
      vektor[0]:=stufe;      { Stelligkeit setzen, Fisch "stufe" ist dran }
      vektor[stufe]:=wahl;   { wahl für diesen Fisch setzen }
      vektor_bewerten;       { hier feststellen ob Farbkonflikt }
      IF vollstaendig
        THEN BEGIN  IF neues_optimum THEN  loesung_speichern   END
        ELSE BEGIN  IF lebend        THEN  try(stufe+1,vektor) END
    END
  END;

BEGIN
  zaehler:=0;
  Writeln; Writeln('P I S C E S   E S C H E R I');
           Writeln('---------------------------'); Writeln;
  vektor[0]:=0;
  try(1,vektor)
END.



HTML-Texte: Münzen 1 Münzen 2 ADT Stack Escher knapsac bunte Reihe salesman HAUPTTEXT
Paket mit Pascal-Dateien laden: BackPac.Zip   (47 K)

zur Informatik-Leitseite


© HMO, Neubearbeitung Januar 1998