Lösung von Logikproblemen mit dem Computer

Ein Computer eignet sich vorzüglich zur Behandlung von Logikproblemen. Man kann damit logisches Denken trainieren, so beim Lösen von Logikrätseln oder beim Ziehen logischer Schlüsse, ebenso beim Prüfen logischer Schlüsse auf Richtigkeit. Wer nicht nur sein logisches Denkvermögen, sondern auch seine Kreativität fordern möchte, findet in der Entwicklung von Logikrätseln oder komplizierten logischen Schlüssen ein weites Betätigungsfeld. Diese Computeranwendungen sind nicht nur sinnvoll, sie machen auch Spaß. In diesem Aufsatz werden einige Lösungsalgorithmen anhand von einfachen Beispielen kurz besprochen. Auf die Problematik unrealisierbar langer Laufzeiten wird eingegangen.

Genau genommen: Logikrätsel sind keine Rätsel, denn mit Raten kommt man bei ihnen nicht weit. Auch Wissen ist nicht gefragt. So braucht beispielsweise nicht nach dem Namen eines Flusses in Frankreich mit sechs Buchstaben und einem „n“ am Ende gefahndet zu werden. Statt dessen erhält man die Lösung durch Kombinieren und logisches Schließen. Alle dazu nötigen Angaben sind im Logikrätsel enthalten. Um sich von „Rate-Rätseln“ deutlich abzuheben, werden Logikrätsel verschiedentlich Logicals, Logeleien oder einfach Denksportaufgaben genannt.

Wie löst man Logikrätsel?

Die Lösung kann mit Bleistift und Papier in Verbindung mit intensiver Kopfarbeit gesucht werden. Man kann sich aber statt dessen eine Stärke des Computers zunutze machen und ihm das Kombinieren und logische Schließen überlassen. Nur: ohne Kopfarbeit geht es trotzdem nicht. Vor der Lösungssuche mit einem Computer müssen die Lösungsprinzipien präzise erarbeitet werden, meist auch viele Details des Computerprogrammes. Das erfordert oft eingehendere Denkarbeit als die Lösungssuche ohne Computer. Aber es stellen sich bald Trainingserfolge ein, die notwendigen Überlegungen fallen auch dem Einsteiger bald leichter. Öftere Aha-Erlebnisse sorgen für Spaß an der Sache. Somit handelt es sich um ein sinnvolles und amüsantes Hobby.

Ein einfaches Beispiel

Es gibt viele Arten von Logikrätseln; dies ist ein sehr einfaches Beispiel:

„Wer von Euch hat noch nicht gefrüh-stückt?“ fragte die Mutter ihre vier Kinder nach ihrer unerwartet frühen Rückkehr. Katja, die Älteste, antwortete auf ihre etwas umständliche, aber präzise Art: „(1) Wenn Ingo gefrühstückt hat, dann sind auch Astrid und Marco abgefüttert. (2) Wenn Astrid und ich noch nichts zu uns genommen haben, dann hat es sich Marco schmecken lassen. (3) Wenn dagegen Astrid und ich gefrühstückt haben, dann hat auch Ingo mit uns getäfelt. (4) Wenn Marco sein Frühstück intus hat, dann haben entweder Astrid oder Ingo noch nicht gefrühstückt. (5) Wenn Astrid fertig ist und Marco noch nicht angefangen hat, dann hat es mir bereits geschmeckt. (6) Wenn weder Astrid noch Ingo ihr Frühstück angerührt haben, dann bin auch ich noch nicht zum Frühstücken gekommen.“ Wer hat gefrühstückt?

Eine Denksportaufgabe dieser Art läßt sich lösen, indem per Computerprogramm nacheinander jede der theoretischen Mög-

lichkeiten geprüft wird, ob sie irgendeiner der (hier sechs) Bedingungen widerspricht. Im Falle des Widerspruchs scheidet die betreffende Mögl ichkeit aus dem Lösungsgang aus. Einzig die allen Bedingungen entsprechende Möglichkeit wird ausgegeben, sie ist die Lösung.

Wieviele theoretische Möglichkeiten gibt es? Bei jedem Kind gibt es zwei Möglichkeiten: hat gefrühstückt oder hat nicht gefrühstückt. Bei den vier Kindern zusammen existieren somit 222* 2 = 16 Möglichkeiten. Hier sei gleich angemerkt, daß Logikrätsel ohne jegliche Mathematikkenntnisse lösbar sind. Entsprechende Betrachtungen in diesem Aufsatz sind Zusatzinformationen an mathematisch interessierte Leser.

Das genannte Lösungsprinzip kann beispielsweise folgendermaßen realisiert werden: Vier geschachtelte Wiederholungsschleifen erzeugen alle Möglichkeiten. Jede Schleife steht für ein Kind; die Laufvariablen sind mit den Initialen bezeichnet: A für Astrid usw. Jede Laufvariable nimmt nacheinander zwei Werte an: 0 für „hat nicht gefrühstückt“, 1 für „hat gefrühstückt“. Anschließend wird in sechs Verzweigungen geprüft, ob die Kombination aus den Werten der vier Laufvariablen den Bedingungen 1 bis 6 entspricht oder nicht. So widerspricht eine Kombination beispielsweise der Bedingung 3, wenn nach deren Werten Astrid gefrühstückt hat (A = 1) und Katja ebenfalls (K = 1), aber

Ingo noch auf sein Frühstück wartet (I = 0). Bei Widerspruch wird der betreffende Programmdurchlauf beendet (z.B. bei BASIC mit einer NEXT-An Weisung, bei Turbo Pascal mit EXIT). Danach wird der Programmlauf mit der nächsten Kombination fortgesetzt. Falls die Kombination allen Bedingungen entspricht, werden ihre Werte mittels der Ausgabeanweisung als Lösung ausgegeben, in unserem Beispiel A = 1,I = 0, K = 0, M = 1, d.h. Astrid und Marco haben gefrühstückt, Ingo und Katja nicht. Ein entsprechendes BASIC-Pro-gramm kann z.B. so wie das beigefügte Programm „Frühstück“ geschrieben werden.

10 REM Programm Frühstück
20 FOR A=0 TO 1 : FOR 1=0 TO 1
30 FOR K=0 TO 1 : FOR M=0 TO 1
110 IF 1=1 AND NOT(A=1 AND M=1) THEN 200
120 IF A=0 AND K=0 AND NOT(M=1) THEN 200
130 IF A=1 AND K=1 AND NOT(I=1) THEN 200
140 IF M=1 AND NOT (A<>I) THEN 200
150 IF A=1 AND M=0 AND NOT(K=1) THEN 200
160 IF A=0 AND 1=0 AND NOT(K=0) THEN 200
190 PRINT A;I;K;M
200 NEXT M : NEXT K : NEXT I : NEXT A 
210 END

BASIC-Programm „Frühstück“

Otmar  Bankkaufmann	       im Großhandel   Diebstahl
Paul   Industriekaufmann   im Bankfach     Betrug
Rolf   Außenh.-Kaufmann	   im Gewerbe      Geheimnisverrat
Stefan Verw.-Ang.          im Außenhandel  Schwänzen
Walter Steuergehilfe       im Einzelhandel Unterschlagung

Tabelle: Lösung des Logikrätsels „Allroundmen“

Zu lange Laufzeiten

Der Vorteil des vorgenannten Lösungsprinzips ist seine Einfachheit. Die Lösung größerer Logikrätsel dauert damit aber zu lange. Auch dazu ein Beispiel:

Mit einer Stellenanzeige war ein „All-roundman“, nicht älter als 35 Jahre, aber mit 20jähriger Erfahrung im „Kaufmännischen“ gesucht worden. Die fünf Bewerber, unter ihnen Paul (wegen des Datenschutzes werden nur die Vornamen genannt), waren offenbar nicht seriöser als die Anzeige. Sie wiesen zwar ihre Ausbildung nach, als Berufserfahrung gaben sie aber nur Tätigkeitsbereiche an. Den Grund ihrer Entlassung von der letzten Beschäftigungsstelle verschwiegen sie ganz, darunter den Verrat von Betriebsgeheimnissen an die Konkurrenz. Jeder hatte einen anderen Beruf erlernt, einen anderen Tätigkeitsbereich angegeben und einen anderen Entlassungsgrund verschwiegen -jeweils welchen? Bekannt ist:

(1) Otmar, der nicht Erfahrungen im Bankfach oder im Außenhandel angegeben hatte, war gelernter Bankkaufmann. (2) Derjenige, der eingehende Erfahrungen im Großhandel angegeben hatte, war wegen Diebstahls entlassen worden. (3) Der Bewerber, der seine letzte Arbeitsstelle wegen Betrugs verloren hatte, hieß nicht Walter, hatte keine Erfahrungen im Außenhandel oder im Gewerbe aufgeführt und war gelernter Industriekaufmann. (4) Rolf hatte Berufserfahrungen im Gewerbe angegeben. (5) Stefan hatte die Papiere wegen notorischen Schwänzens bekommen. (6) Der ausgebildete Steuergehilfe hatte Berufserfahrung im Einzelhandel angegeben. (7) Der gelernte Außenhandelskaufmann war nicht wegen Unterschlagung geschaßt worden. (8) Der Verwaltungsangestellte hatte nicht . Erfahrungen im Gewerbe genannt, er war auch nicht wegen Unterschlagung entlassen worden.

Diese Denksportaufgabe handelt von vier Mengen: Der Menge der Personen, der gelernten Berufe, der angegebenen Berufserfahrungen und der Kündigungsgründe. Jede Menge enthält fünf Elemente: die fünf Vornamen, die fünf Berufe usw. Die Lösung besteht darin, die Elemente der verschiedenen Mengen so einander zuzuordnen, daß die (hier acht) Bedingungen eingehalten werden. Man könnte sinngemäß wie beim vorigen Logikrätsel verfähren, indem man dabei alle möglichen Zuordnungen erzeugt und jede Zuordnung (zu je 20 Elementen) auf Widerspruch zu den Bedingungen prüft. Aber: Bereits bei diesem nicht sehr großen Rätsel gibt es 1 728 000 Zuordnungsmöglichkeiten. Sie abzuarbeiten, kann je nach Computer, Programmiersprache und Programm Stunden bis mehrere Tage dauern.

Die Zahl der Zuordnungsmöglichkeiten (Z) steigt mit der Zahl der Mengen (M) und der Zahl der Elemente (E) steil an. Sie kann nach der Formel Z = (E!)(M-1) berechnet werden. Bereits zur Lösung eines derartigen Logikrätsels mit 6 Mengen je 7 Elementen wäre Jahrhunderte erforderlich, um die ca. 3,25 * 1018 Zuordnungsmöglichkeiten abzuarbeiten.

Um größere Logikrätsel dieser Art hinreichend schnell lösen zu können, bedarf es effektiverer Lösungsmethoden, beispielsweise der „Mehrschrittmethode“. Mit dieser gelingt es, unser Beispiel in Bruchteilen einer Sekunde bis wenigen Minuten zu lösen. Beim ersten Schritt werden nacheinander die Zuordnungsmöglichkeiten jeweils für eine Person auf Widersprüchlichkeit zu den Bedingungen geprüft und im Falle des Widerspruchs aus dem Lösungsgang ausgeschieden. Hier gibt es 625 solcher Zuordnungsmöglichkeiten, nämlich EM.

Ordnet man die Elemente jeder Menge alphabetisch, wird als erstes die Zuordnungsmöglichkeit Otmar, Außenhandelskaufmann, im Außenhandel, Betrug entsprechend behandelt, dann Otmar, Außenhandelskaufmann, im Außenhandel, Diebstahl usw., zuletzt Walter, Verwaltungsangestellter, im Großhandel, Unterschlagung. Diese drei Zuordnungsmöglichkeiten beispielsweise scheiden aus dem Lösungsgang aus: die erste, weil sie nicht den Bedingungen 1 und 3 entspricht, die zweite wegen Widerspruchs zur Bedingung 1 und die letzte wegen Widerspruchs zu den Bedingungen 2 und 8. Insgesamt werden beim ersten Lösungsschritt 601 der 625 Zuordnungsmöglichkeiten ausgeschieden, ihre Zahl wird somit schnell und rigoros reduziert.

In einem weiteren Lösungsschritt werden jeweils fünf (= E) der verbliebenen 24 Zuordnungsmöglichkeiten miteinander verglichen mit dem Ziel, diejenigen fünf herauszufinden, bei denen alle Elemente (hier 5*4 = 20) voneinander verschieden sind. Diese herausgefundenen Zuordnungen sind die Lösung und werden vom Computer ausgegeben, siehe Tabelle „Allroundmen“.

Mit falschen Angaben

Bei einer großen Zahl von Logikrätseln sind nicht alle Angaben wahr, beispielsweise:

Carmen:
„Entweder lügt Helga oder Jutta!“
Helga:
„Entweder lügt Carmen oder Jutta!“
Jutta:
„Carmen und Helga sagen die Wahrheit!“

Wessen Aussage ist richtig?

Im Lösungsalgorithmus solcher Denksportaufgaben sind meist neben den Aussagen auch deren Negationen zu berücksichtigen, so auch im beigefügten Pascal-Programm „Luege“ zur Lösung dieses Rätsels.

Die drei FOR-Schleifen im Hauptprogramm erzeugen nacheinander die Wahr-heitswerte: 0 bedeutet die Annahme falscher Aussage, 1 die Annahme wahrer Aussage. Jede Schleife steht für eine der Personen Carmen (C), Helga (H) und Jutta (J). In der Prozedur Bedingungen_Ausgabe wird für jede Person geprüft, ob - bei Annahme wahrer Aussage (z.B. 0=1) die anderen Werte zur betreffenden Aussage widersprüchlich sind (z.B. NOT(HoC)), - trotz Annahme falscher Aussage (z.B. 0=0) die anderen Werte der betreffenden Aussage entsprechen (z.B. (HoC ist).

Wird eines davon festgestellt, dann wird der betreffende Schleifendurchlauf durch EXIT beendet; danach wird die Verarbeitung mit der nächsten Kombination aus der Weiten von C, H und J fortgesetzt.

Carmens Aussage wäre wahr, wenn genau eine der beiden anderen Personen lügt, wenn also H und J voneinander verschiedene Werte haben.

Falls der Programmdurchlauf bei keiner der sechs IF-Anweisungen abgebrochen wird, heißt das: Nach den aktuellen Werten von C, H und J haben sich die als wahr angenommenen Aussagen als wahrerwiesen und die als falsch angenommennen Aussagen als falsch. Dies ist die Lösung. Sie wird mit der Ausgabe-Anweisung ausgegeben. In diesem Beispiel besteht die Ausgabe aus drei Nullen, d.h. alle drei Aussagen sind falsch. - Es empfiehlt sich, dieses Ergebnis anhand der Aussagen gedanklich nachzuvollziehen.

Mit indirekten Angaben

In sogenannten Metarätseln, die auch als „Rätsel über Rätsel“ bezeichnet worden sind, fehlt mindestens eine zur Lösung erforderliche Angabe. Dafür ist angegeben, ob jemand, der im Besitz zusätzlicher Informationen ist, die Denksportaufgabe lösen könnte oder nicht. Mit dieser Zusatzinformation über die Lösbarkeit kann nun das Rätsel gelöst werden. Dies ist ein Beispiel dieser Art:

Auf die Frage des Deutschlehrers, ob sie und ihre Freundinnen Elke und Gabi bereits einen Ausbildungsplatz gefunden hätten, antwortete Birgit: „Wenn Elkes Bewerbung erfolgreich war, dann hat Gabi eine Ausbildungsstelle oder ich keine. Wenn ich einen Ausbildungsplatz habe, dann ist Gabi noch auf der Suche. Und ob ich eine Ausbildungsstelle habe oder nicht, das habe ich Ihnen vorhin schon gesagt.“ -„Richtig“, erinnerte sich der Pädagoge; nach kurzem Nachdenken tat er kund, daß er jetzt auch über die beiden anderen Bescheid wisse. Wer von den dreien hat einen Ausbildungsplatz?

Man kann dieses Logikrätsel wie das Beispiel „Frühstück“ lösen, wobei die Bedingungen nur aus Birgits wörtlicher Rede abgeleitet werden. Allerdings gibt der Computer fünf Ergebnisse aus: nach vier von ihnen hat Birgit noch keinen Ausbildungsplatz, nach einem Ergebnis hat sie eine Stelle. Wäre dem Lehrer vorher mitgeteilt worden, Birgit habe keine Ausbildungsstelle, dann hätte er nicht dahinter kommen können, wie es um Elke und Gabi steht: jede von ihnen hätte einen Ausbildungsplatz haben können oder nich . Also muß ihm Birgit gesagt haben, daß sie bereits eine Stelle habe. Die entsprechende Ausgabe des Computers zeigt, daß die beiden anderen noch keine Ausbildungsstelle haben.

PROGRAM Luege 
VAR
C,H,J:	integer;

PROCEDURE Bedingungen_Ausgabe 
BEGIN
	IF (C=1) AND NOT (H<>J) THEN EXIT;
	IF (C=0) AND (H<>J) THEN EXIT;
	IF (H=1) AND NOT (C<>J) THEN EXIT;
	IF (H=0) AND (C<>J) THEN EXIT;
	IF (J=1) AND NOT ((C=1) AND (H=1)) THEN EXIT; 
	IF (J=0) AND ((C=1) AND (H=1)) THEN EXIT; 
	writeln(C,H,J)
END; (*der Prozedur*)

BEGIN (*Hauptprogramm*)
	FOR C:=0 TO 1 DO 
		FOR H:=0 TO 1 DO 
			FOR J:=0 TO 1 DO 
				Bedingungen_Ausgabe;
END (*Hauptprogramm*)

Pascal-Programm „Luege“

Selbst Logikrätsel erstellen

Im Prinzip wird man ein Programm zur Lösung eines Logikrätsels weitgehend auch zur Erstellung eines gleichartigen Rätsels verwenden können. In jedem Falle aber müssen die Anweisungen, die von den speziellen Bedingungen des einen Rätsels abgeleitet sind, durch entsprechende Anweisungen des zu erstellenden Logikrätsels ersetzt werden. Jedes selbst erstellte Logikrätsel ist sorgfältig daraufzu prüfen, daß es keine inneren Widersprüche enthält und in bezug auf die Lösung eindeutig ist. Auch soll es möglichst keine redundanten, also keine überflüssigen Bedingungen enthalten. Ein Computer ist zur Entwicklung und zur Prüfung des Bedingungssystems fast unentbehrlich.

Logische Schlüsse

Sehr einfach ist es, z.B. aus den Prämissen „Alle Boxweltmeister sind Sportler“ und „Max ist Boxweltmeister“ den Schlußsatz zu bilden, also den logischen Schluß zu ziehen: „Max ist Sportler“. Dazu benötigt man keinen Computer. Ist aber ein Schlußsatz aus mehr als zwei Prämissen abzuleiten, ist ein Computer meistens hilfreich.

Mit einem Computer kann man aber auch prüfen, ob der Schluß richtig gezogen worden ist, so z.B., ob der aus den Prämissen „Wenn ich lese, dann brauche ich Licht“ und „Ich brauche Licht“ gebildete Schlußsatz „Ich lese“ richtig ist. Möglich ist folgendes Vorgehen: Zunächst werden mit dem Computer alle Zuordnungsmöglichkeiten ausgeschieden, die nicht den Prämissen entsprechen. Danach wird jede der verbliebenen Zuordnungsmöglichkeiten geprüft, ob sie dem Schlußsatz widerspricht. Wenn dabei der Computer einen Widerspruch feststellt, gibt er eine entsprechende Mitteilung aus (z.B. „Schluß falsch“) - wie er es auch bei diesem sehr einfachen Beispiel täte.

Voraussetzungen

Spezielle Software ist zur Behandlung von Logikproblemen nicht erforderlich. Die nötigen Programme kann man selbst erstellen. Auch an die Hardware werden keine besonderen Anforderungen gestellt. Ein Einsteiger hat keine allzu großen Schwierigkeiten zu erwarten: Wie die Beispiele zeigen, gibt es (viele) Denksportaufgaben, die mit einigen nicht allzu schwierigen Überlegungen und nur geringen Programmierkenntnissen lösbar sind. Trotzdem w ird es nicht langweilig - selbst auf lange Sicht nicht. Bei den vielen verschiedenartigen Logikrätseln unterschiedlichen Schwierigkeitsgrades müssen sich auch „Fortgeschrittene“ immer wieder etwas einfallen lassen, sei es zur Lösungsmethode selbst oder zu Details des Computerprogrammes - was ja der Sinn der Sache ist.

Günter Süßmuth

Literatur:
Logiktraining mit Logikrätseln - Unterhaltsame Rätsel lösen mit Hilfe von BASIC und Turbo Pascal, Vaterstetten 1990
Logikrätsel und logische Schlüsse - Anspruchsvolle Logikrätsel lösen und logische Schlüsse ziehen mit Hilfe von BASIC und Turbo Pascal, Vaterstetten 1991



Aus: ST-Computer 09 / 1992, Seite 114

Links

Copyright-Bestimmungen: siehe Über diese Seite