Tanzabend - das Logikrätsel

[terter]

Diese Aufgaben lassen sich gut als CSP beschreiben:

http://de.wikipedia.org/wiki/Constra...action-Problem

Eine Lösungsmöglichkeit sieht z.B. so aus:

Das ganze CSP lässt sich lösen, in dem wir uns eine Tabelle denken. Diese Tabelle beinhaltet einmal als Zeilen alle Namen die im Text vorkommen. Aus Übersichtsgründen habe ich Männer und Frauen gruppiert.

Für jede Person gibt es verschiedene belebgbare Variablen: "Kleidung", "beziehung-zu" und "tanzt-mit".

Hier suchen wir uns einmal alle möglichen Belegungen aus den Text (samt Fragen) heraus. Jede Spalte steht für eine Variable und beinhaltet von Haus aus eine Liste aller Möglichkeiten.

PHP-Code:

        | Kleidung             | Beziehung-mit            | tanzt-mit
-------------------------------------------------------------
Leonie    | {rot, gelb, ..}    | {Max, ...}            | {Max, ...}
...        | ...                | ...                    | ...
Max        | {grau, blau, ..}  | { Leonie, ...}        | { Leonie, ...} 

Danach schreibst du dir eine Liste der Constraints auf. Hier muss man etwas aufpassen, da einige Punkte im Text mehrere Constraints beinhalten.

Danach gehst du die Constraints einfach immer durch und streichst die Attribute die nicht in Frage kommen aus der Tabelle heraus. Das machst du so lange, bis du keine Constraints mehr anwenden kannst.

Dieses CSP ist eindeutig lösbar.

...

Hi,

danke für die Antwort. Die Tabelle ist klar. Was meinst du mit ich schreibe mir eine Liste der "Contrains" auf und streiche die weg?ß Kannste mir mal ein Beispiel machen?

Danke

[Mog]

Hi,

danke für die Antwort. Die Tabelle ist klar. Was meinst du mit ich schreibe mir eine Liste der "Contrains" auf und streiche die weg?ß Kannste mir mal ein Beispiel machen?

Danke

...

Constraints sind irgendwann komplett konsumiert. Manche Constraints können öfters angewandt werden, manche aber auch nur genau einmal. Wenn ein Constraint nicht mehr angewandt werden kann, empfiehlt es sich dieses heraus zu streichen, damit man das nicht immer wieder durchdenkt.


Ein Beispiel:

PHP-Code:

| Kleidung             | Beziehung-mit            | tanzt-mit
-------------------------------------------------------------
Leonie    | {rot, gelb, ..}    | {Max, ...}            | {Max, ...}
Anna     | {rot, gelb, ..}    | {Max, ...}            | {Max, ...}
...        | ...                | ...                    | ...
Max        | {grau, blau, ..}  | { Leonie, ...}        | { Leonie, ...} 

3. Anna trägt nicht das rote Kleid.

Dieses Constraint füht dazu, dass wir "rot" bei Anna heraus streichen. Durch dieses Constraint wissen wir, dass die Variable "Kleidung" für Anna niemals rot ergeben kann. Somit bleiben nur KLeider der anderen Farbe übrig.

PHP-Code:

              | Kleidung             | Beziehung-mit            | tanzt-mit
-------------------------------------------------------------
Leonie    | {rot, gelb, ..}    | {Max, ...}            | {Max, ...}
Anna     | {--r-o-t--, gelb, ..}    | {Max, ...}            | {Max, ...}
...        | ...                | ...                    | ...
Max        | {grau, blau, ..}  | { Leonie, ...}        | { Leonie, ...} 

Das Constraint wird bei weiterer Anwendung niemals mehr eine Veränderung an der Tabelle erzielen. Wir können es aus unserer Constraint-Liste heraus streichen, da es nie wieder gebraucht wird.


Folgendes Constraint hingegen können wir durchaus öfters gebrauchen:

1. Keines der Paare tanzt zusammen!

So können wir z.B. in die Situation kommen, dass wir über diese Regel erst bei Anna anwenden können und erst viel später bei Max. Wir können das Constraint erst aus unserer Liste entfernen, wenn wir es auf alle Zeilen angewandt wissen.



EDIT:

Manche Punkte beschreiben mehrere Constraints:

9. Leonie trägt an diesem Abend ein kurzes gelbes Kleid. Sie ist nicht mit dem Mann verheiratet der den hellblauen Anzug trägt. Auch Lisa ist nicht mit dem Mann in dem hellblauen Anzug verheiratet.

=> Leonie trägt an diesem Abend ein kurzes gelbes Kleid.
=> Leonie ist nicht mit dem Mann verheiratet der den hellblauen Anzug trägt.
=> Auch Lisa ist nicht mit dem Mann in dem hellblauen Anzug verheiratet.


Genau so gibt es einige Constraints die durch die Tabelle zusätzlich bestehen, da Veränderungen einer Zeile gleich die Andere mit beeinflussen. (Unterschiedliche Beziehungen, ...., sobald etwas eindeutig ist, fällt die Variable natürlich aus den Anderen Listen der selben Spalte weg)

[terter]

Danke für die Info. Nun habe ich aber auch das Problem, dass ich nicht alle Namen kenne...was mache ich da?

[Mog]

Danke für die Info. Nun habe ich aber auch das Problem, dass ich nicht alle Namen kenne...was mache ich da?

...

Die stehen alle im Text. Du musst auch die Fragen beachten, da stecken die fehlenden drinnen.

[terter]

Die stehen alle im Text. Du musst auch die Fragen beachten, da stecken die fehlenden drinnen.

...

ich komme einfach nicht weiter :-( Hat jemand eine Musterlösung?

[Liferipper]

Diese Art von Rätsel nennt man Logical und Einstein sagte angeblich zu seiner Variation, dass nur 2% der Menschheit in der Lage seien, es lösen zu können.

...

Naja, das ist vermutlich eher der Tatsache geschuldet, dass 98% der Menschheit die Geduld fehlt, als der Verstand.