Zahlenlogical

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Zahlenlogical

    Hallo.

    bin als PROLOG-BEGINNER gerade dabei ein zahlenrätsel zu lösen.
    gegeben ist eine tabelle mit leeren feldern (5X5)

    Die Zeilen sind mit A,B,C,D,E und Spalten mit
    mit 1,2,3,4,5 angegeben. Somit gibt es 25 Felder A1 bis E5.
    Wie gesagt alle sind leer außer D3. D3 hat nämlich den Wert 7.
    Alle anderen Felder sollen mit den Zahlen 1 bis 9 aufgefüllt werden.

    Und nun die Bedingungen:
    - jede Zeile, Spalte und die beiden Hauptdiagonalen sollen die Summe 25 ergeben.
    - je Zeile und je Spalte kann nur dann eine Zahl mehr als einmal vorkommen, falls
    dies ausdrücklich in den anderen Hinweisen erwähnt wird. für die diagonalen
    muss dies NICHT notwendigerweise gelten.

    HINWEISE.
    - Spalte 1 weist exakt eine ungerade Zahl auf.
    - die summe aus A2 und C2 ist das Dreifache der Zahl in B2.
    - Die Summe aus D4 und E4 ist fünfmal so hoch wie das Produkt aus C4 und E4.
    - Zeile D enthält die Zahl 2 doppelt, Spalte 1 die Zahl 6 doppelt und Spalte 3 die Zahl 3 doppelt. In Zeile A taucht die Zahl 4 dreimal auf.
    - In Spalte 5 sind die drei obersten Zahlen eine um den jeweils selben Betrag aufsteigende Zahlenfolge (z.B. 1-4-7)
    - In den Diagonalen A1/E5 ist die Zahl 5 zweifach vorhanden, die Zahl 9 hingegen überhaupt nicht.


    So. Das waren alle Regeln und Hinweise.

    Wie gesagt, ich habe gerade mit PROLOG angefangen und bin über jede Hilfe, auch wenn sie nur eine Teilhilfe ist, dankbar.

    THANKS.Tailor
  • Also ich hab zwar auch recht wenig mit Prolog am hut, aber vom Prinzip könntest du ja mal eine Liste versuchen, für jede Zeile eine Liste mit den jeweiligen Positionen und die dann miteinander vergleichen. Aber wie gesagt, dass nur von jemandem mit begrenztem Proglog Wissen :D Ich denke Siracusa weiß wie mans richtig macht :)
    mfg KC
  • Hi tailor,

    entschuldige bitte, daß ich jetzt erst antworte. Zwar hatte ich deinen Beitrag vor zwei Tagen schon gelesen, habe aber studienbedingt erst jetzt die Zeit gefunden eine Antwort zu schreiben. :oops:

    Deine Aufgabe finde ich als Einstiegsaufgabe recht schwierig und eine schnelle Lösung ist nicht einfach zu implementieren. Alle möglichen Zahlenkombinationen durchzutesten fällt bei ca. 7*10^23 Möglichkeiten wohl weg, bleibt bspw. ein Bachtracking-Algorithmus. Du könntest dir eine Liste mit 25 Elementen [A1, ..., E5] oder eine 5x5-Matrix [[A1, ..., A5], ..., [E1, ..., E5]] anlegen, die die einzelnen Tabelleneinträge widerspiegelt. Nun wird an der ersten Stelle eine Zahl zwischen 1 und 9 gesetzt und überprüft, ob diese Zahl an der Stelle korrekt sein kann oder nicht. Wenn es zu keinen Konflikten mit den Spielregeln/Hinweisen kommt, wird zur nächsten Stelle gerückt und dort eine Zahl gesetzt. Tritt ein Konflikt auf, so wird für die aktuelle Zahl ersteinmal die nächstgrößere gesetzt. Dies wird solange wiederholt, bis die aktuelle Stelle paßt, oder keine Zahl mehr zur Verfügung steht, die gesetzt werden kann. Im letzteren Fall wird zur Stelle davor zurückgegangen und die Zahl dort korrigiert.
    Ein Problem bei der Sache ist, daß anfangs einige Stellen noch nicht besetzt sind und z.B. mit 0 aufgefüllt werden müssen. Wird in einem Schritt zurückgegangen, so muß vorher die alte aktuelle Position wieder gelöscht werden. Dementsprechend dürfen die Regeln, die in jedem Schritt überprüft werden, bei einer leeren Stelle keinen fehlerhaften Wert liefern, sondern müssen diese Stelle dann einfach ignorieren.

    Hier ist ein kleines Beispiel, das den Algorithmus verdeutlichen soll.

    [code:1]
    Gesucht sind drei Zahlen A, B, und C, für die folgendes gilt:
    (1) A, B, C sind Zahlen zwischen 1 und 9
    (2) A + B + C = 10
    (3) B + C = 3
    (4) A > B > C

    [_] _ _

    Setzen: Aktuelle Stelle ist leer => ersten gültigen Wert setzen
    [1] _ _
    Prüfen: Keine Regel wird verletzt => zur nächsten Stelle rücken
    1 [_] _

    Setzen: Aktuelle Stelle ist leer => ersten gültigen Wert setzen
    1 [1] _
    Prüfen: Regel (4) wird verletzt => nicht weiterrücken
    1 [1] _

    Setzen: Aktuelle Stelle ist nicht leer => um 1 erhöhen
    1 [2] _
    Prüfen: Regel (4) wird verletzt => nicht weiterrücken
    1 [2] _

    ...

    Setzen: Aktuelle Stelle ist nicht leer => um 1 erhöhen
    1 [9] _
    Prüfen: Regel (4) wird verletzt => nicht weiterrücken
    1 [9] _

    Setzen: Aktuelle Stelle ist letzter gültiger Wert => zurükgehen und Stelle um 1 erhöhen
    [2] _ _
    Prüfen: Keine Regel wird verletzt => zur nächsten Stelle rücken
    2 [_] _

    Setzen: Aktuelle Stelle ist leer => ersten gültigen Wert setzen
    2 [1] _
    Prüfen: Keine Regel wird verletzt => zur nächsten Stelle rücken
    2 1 [_]

    Setzen: Aktuelle Stelle ist leer => ersten gültigen Wert setzen
    2 1 [1]
    Prüfen: Regel (2) wird verletzt => nicht weiterrücken
    2 1 [1]

    Setzen: Aktuelle Stelle ist nicht leer => um 1 erhöhen
    2 1 [2]
    Prüfen: Regel (2) wird verletzt => nicht weiterrücken
    2 1 [2]

    ...

    Setzen: Aktuelle Stelle ist nicht leer => um 1 erhöhen
    2 1 [9]
    Prüfen: Regel (2) wird verletzt => nicht weiterrücken
    2 1 [9]

    Setzen: Aktuelle Stelle ist letzter gültiger Wert => zurükgehen und Stelle um 1 erhöhen
    2 [2] _
    Prüfen: Regel (4) wird verletzt => nicht weiterrücken
    2 [2] _

    ...

    Setzen: Aktuelle Stelle ist leer => ersten gültigen Wert setzen
    7 2 [1]
    Prüfen: Keine Regel wird verletzt, alle Stellen sind besetzt
    => Lösung gefunden
    [/code:1]

    Die Hauptfunktion könnte dann etwa so aussehen:

    [code:1]
    loesen(Matrix0, Pos0):-
    // Wert an aktueller Position ändern
    setzen(Matrix0, Pos0, Matrix1, Pos1),

    // Regeln überprüfen und entsprechend Position ändern
    pruefen(Matrix1, Pos1, Matrix2, Pos2),

    // rekursiver Aufruf mit veränderter Matrix
    loesen(Matrix2, Pos2).

    Aufruf: loesen(startmatrix).
    [/code:1]

    Soviel erstmal zum allgemeinen Algorithmus. Wenn es noch Unklarheiten oder sonstige Fragen gibt, dann immer raus damit. :)


    Viele Grüße,

    Siracusa