Dokumentation des Programms SETGAME

Lösungsidee

Die Speicherung der Karten

Die Karten werden in der Variable Karten gespeichert. Diese ist ein Pointer auf Byte. Nach dem Einlesen von v und n werden vn Bytes für diesen Zeiger allokiert. Mittels Karten[i] (diese einfache Schreibweise war ein Grund, Free Pascal statt Turbo Pascal zu benutzen) kann nun auf alle Elemente von bis 0 vn-1 zugegriffen werden Nun wird das ganze Array mit dem Wert False gefüllt, was bedeutet, daß noch keine Karten vorhanden sind. Vorhandene Karten werden durch den Wert True dargestellt.
Die Umrechnung der angegebenen Koordinaten, zum Beispiel 0201, geschieht, indem die Summe der Ziffern an den Stellen 0 bis n-1, jeweils mit 3n multipliziert, gebildet wird.

Das Hinzufügen von Karten

Karten werden einfach hinzugefügt, indem der Methode Add oder AddByI die hinzuzufügende Karte übergeben wird, wobei Add einen Zeiger auf ein Array mit den Zahlen und AddByI den schon umgerechneten Index erwartet. Karten dürfen nur hinzugefügt werden, wenn diese kein Set bilden; daher werden bei jedem Hinzufügen einer Karte alle setbildenden ausgeschlossen.

Der Ausschluß der setbildenden Karten

In dem Objekt TKarten wird durch die Variable VerbotenVon gespeichert, ob eine Karte verboten ist oder nicht. Bei jedem Hinzufügen einer Karte wird die Methode SchliesseAus aufgerufen, die alle setbildenden Karten ermittelt, die mit der hinzugefügten Karte und den v-2 weiteren, schon ausgewählten Karten entstehen könnten. Die Karten, die noch nicht ausgeschlossen und jetzt ein Set bilden würden, werden markiert.

Die Ermittlung der maximalen Anzahl Karten ohne Set

Die maximale Anzahl Karten ohne Set wird in der Methode GetMaxOhneSet realisiert. Über die rekursive Unterprozedur TryFrom wird dann versucht, möglichst viele Karten zu belegen. Dazu hat TryFrom einen Parameter, der diejenige Karte angibt, bei der angefangen werden soll zu suchen. Von dieser Karte bis zur letzten wird dann bei jeder Karte versucht, diese hinzuzufügen, worauf bei Erfolg ein weiterer Aufruf (die Rekursion) von TryFrom stattfindet, der als Startkarte den Nachfolger der zuletzt hinzugefügten Karte erhält.
Auf diese Weise probiert der Computer alle möglichen Kombinationen durch und findet in jedem Fall alle Maximallösungen; allerdings ist dieser Algorithmus bei nicht kleinen n und v ohne irgendwelche Vorgaben nicht sonderlich schnell.

Ablaufbeschreibungen der wichtigsten Methoden

Hauptprogramm

Einlesen von v und n
Objekt erstellen
Wiederhole:
Aktuelle Kartenkonfiguration ausgeben
Eingaben des Benutzers verarbeiten:
  • Karten hinzufügen / löschen
  • Karten verbieten / un-verbieten
  • Die Maximalzahl ermitteln
  • Bis Ende
    Objekt löschen

    Methode GetMaxOhneSet

    In dieser Methode gibt es eine Variable, Best, die die bis jetzt höchste Anzahl an Karten, die man ohne Set anordnen kann, angibt. GetMaxOhneSet verwendet die Unterprozedur TryFrom, die durch Rekursion alle Möglichkeiten durchprobiert.

    GetMaxOhneSet

    Best gleich 0 setzen, denn jede Lösung mit auch nur einer Karte soll besser sein
    Den Lösungsspeicher löschen
    TryFrom(0) aufrufen: 0 ist hierbei der Index der Karte, bei der angefangen werden soll zu suchen
    Best zurückgeben

    TryFrom(from):

    Wenn mehr Best Karten belegt sind:
    Best auf Anzahl der Karten setzen
    Alle gespeicherten Lösungen mit Best-1 Karten löschen
    Wenn genau Best Karten belegt sind:
    Lösung speichern und ausgeben
    Für alle i von from bis Anzahl der Karten-1:
    Wenn das Feld mit Index i belegt werden darf:
    Feld belegen
    Rekursiv TryFrom aufrufen, ab dem Index i+1
    Belegung des Feldes entfernen
    Aufheben aller durch dieses Feld verursachten Belegungsverbote

    SchliesseAus(hinz,from)

    Die Methode SchliesseAus wird im Programm immer dann aufgerufen, wenn eine Karte hinzugefügt wird. Sie markiert diejenigen Felder mit dem Wert from, die mit der Karte hinz und beliebigen anderen schon ausgewählten Karten Sets bilden würden. Wenn man Karten festlegt, hat from immer den Wert machine; das heißt, daß das Feld von der Maschine (dem Computer) automatisch ausgeschlossen wurde. Wenn dem Parameter from dagegen immer eindeutige Werte gegeben werden, wie das in der Procedure TryFrom in der Methode GetMaxOhneSet geschieht, kann man die nicht setbildenden Felder beim Entfernen einer Karte leicht identifizieren, wenn man die Karten in umgekehrter Reihenfolge zum Hinzufügen wieder entfernt.
    Zum Ausschließen wird die Karte hinz wird mit je v-2 anderen Karten kombiniert, dann wird die jeweils setbildende Karte ermittelt. Dazu werden im Array ausschluss[0..v*n-1] of Byte die Häufigkeiten der jeweiligen Varianten in den Eigenschaften gespeichert. Die setbildende Karte gibt es, wenn für alle Eigenschaften gilt, daß entweder eine Variante v-1 Mal vorkommt, dann hat die setbildende Karte in dieser Eigenschaft auch diese Variante, oder daß alle Varianten genau einmal vorkommen und eine gar nicht, die setbildende Karte hat dann die nicht vorkommende Variante. Wenn keiner dieser Fälle für eine (oder mehr) Eigenschaften zutrifft, gibt es keine setbildende Karte.

    Den Source zu diesem Programm senden wir gerne per email zu.
    vorheriges Kapitel


    Anregungen, Fragen, Kritik an: Wolf Behrenhoff, Felix Krahmer und Andreas Sorge