Logical-Löse-Programm

[Hans-Peter St]

Hallo,
es gibt da so Logicals. Bsp.:
5 Personen mit 5 verschiedenen Namen, 5 verschiedenen Vornamen, 5 unterschiedlichen Beschäftigungen und 5 x verschiedenes Alter treffen sich.
Finden Sie aus den Hinweisen raus, wer (Name + Vorname) was tut u. wie alt er ist.
1. Herr X. ist Leichtathlet.
2. Herr F. ist Filmer u. 4 Jahre jünger als der Sportler.
..... (immer so 6 bis 10 Hinweise).
Dazu habe ich einen einfachen Lösungsalgorythmus in QB geschrieben.
Interessiert das überhaupt wen?
H.-P.

[Calavera]

Ich muss gestehen, nicht zu wissen, was du mit dem Beitrag aussagen oder bezwecken willst. Denn ich vermute mal vorsichtig, dass du hier im Forum keine Interessenten für den Algorithmus wirst. Denn wo bleibt der Spaß bei einem Rätsel, wenn man nicht mehr rätseln muss!?


Schönen Gruß,

Calavera

[~ÔttÔ~]

Interessanter (und herausfordernder) wäre ein Programm, das Logicals erstellt, beliebiger Größe, mit minimalen Angaben (d.h. man darf keine Angabe weglassen, ohne dass das Logical keine eindeutige Lösung mehr hat, und natürlich soll sich die Gesamtanzahl der Angaben in Grenzen halten), und das mit geordneten Attributen zurecht kommt (geordnete Attribute: Geldbeträge, Datums- und Zeitangaben, Längenangaben, etc.).

~ÔttÔ~

[Hans-Peter St]

Hi,
ich habe in einer Zeitschrift ein Logical mit vier Spalten und fünf Zeilen gesehen. Jede der Spalten kann irgendwie heissen. Z.B. Automarke, Vorname, ... Das hat mich auf den Gedanken gebracht, das doch schnell mit nem Progrämmchen zu lösen.
Als nettes Nebenprodukt kann ich mühelos nun meine eigenen Logicals erzeugen.
Um bei dem Beispiel zu bleiben, hat man für die Spalte Automarke die 5 Werte: Opel, Mercedes, Audi, Ford, VW und bei Vornamen: Peter, Paul, ...
Diese 5 Marken (oder Namen) nummeriere ich von 1 bis 5.
Damit kriege ich eine Matrix m(5,4). Also 5 Zeilen 4 Spalten.
Gut. Dann ist eine Reihenfolge der 5 Ziffern einer Spalte eine der 120 möglichen Permutationen der Ziffern 1 bis 5. Wenn ich nun für jede Spalte alle möglichen Permutationen mit denen aller anderen vergleiche UND nach jeder Zusammenstellung meine Bedingungen abfrage, geht mir NICHTS durch die Lappen.
Diese Bedingungen stelle ich in zunehmender Anzahl und rein willkürlich, bis nur eine mögliche Lösung bleibt. Natürlich sind ein paar kleine Tricks dabei, weil die Fülle der möglichen Kombinationen gigantisch ist.
Aber damit kreiere ich eigene Logicals. Oder löse fremde. Das gehr recht schnell.
Wenn ich mal mehr Zeit habe (derzeit im Stress), stelle ich mal was rein.
Gruss, H.-P.

[uvo]

Ich habe seit einiger Zeit auch schon darüber nachgedacht, mir ein solches Programm zu schreiben, diese Idee dann aber verworfen:

Meines Erachtens ist es ohne größeren Programmieraufwand erst einmal nur möglich, "leichte" Rätsel zu lösen bzw zu erzeugen, also solche mit Standard-Aussagen wie "Peter besitzt (k)einen Audi", um mal bei deinem Beispiel zu bleiben. Für solche Rätsel brauche ich allerdings kein Programm

Hinzu kommt, daß es extrem schwer ist, eine Art Spracherkennung einzubauen, die mit Aussagen der Form "Peter besitzt einen Audi" zurechtkommt (ich würde mir so etwas nicht zutrauen). Das bedeutet, zum Lösen muß ich die in Textform gegebenen Aussagen erst einmal in eine mathematische Formelsprache übersetzen - und in der Zeit, die ich dafür benötige, habe ich das Rätsel vermutlich schon gelöst.

Spannender sind Rätsel mit Relativhinweisen, etwa in der Form "Peters Auto ist 3 Jahre älter als das Auto des Münchners", oder verschärft "Peters Auto ist 3 Jahre älter als das Auto, das 5000 Euro teurer war als das Auto des Münchners". Interessante und schwierige Rätsel bekommt man vermutlich nur hin, indem man viele derartige Relativhinweise kombiniert. Wie löst man jetzt derartige Rätsel per Computer? Intelligente Algorithmen zu schreiben, ist nicht ganz einfach, da man dabei auf alle möglichen Arten von Hinweisen vorbereitet sein muß, und die Kreativität von Rätselautoren einem dabei immer wieder einen Strich durch die Rechnung machen kann. Natürlich ist es möglich, per Brute Force einfach alle Möglichkeiten durchzuprobieren - für die von dir genannte Rätselgröße wären das 120^4 Möglichkeiten, also rund 200 Millionen, was mit heutigen Rechnerleistungen überhaupt kein Problem darstellt - aber was steckt da für ein Sinn dahinter?

Und das ist meines Erachtens die Kernfrage: Wozu ein solches Programm?
Um Rätsel zu lösen? Entweder mir macht diese Art von Rätseln Spaß, dann möchte ich sie auch selbst lösen und mir nicht simpel von einem Programm die Lösung ausgeben lassen, oder mir machen diese Rätsel keinen Spaß, dann wird sich das durch ein Programm auch nicht ändern...

Oder um Rätsel zu erstellen? In dieser Community überwiegt die Meinung, daß händisch erstellte Rätsel höherwertig sind als computergenerierte. Ein Grund ist, daß es bei einem ohne Computer erstellten Rätsel zwangsläufig einen Lösungsweg gibt, den ein menschlicher Löser finden kann. Bei einem computergenerierten Rätsel kann es passieren, daß der Computer zwar sieht, daß von den 200 Millionen Möglichkeiten nur eine in Frage kommt, aber das menschliche Gehirn ist dazu nicht in der Lage... dann besteht der Lösungsweg darin, vieles auszuprobieren und nur langsam Fortschritte zu machen; der Spaß dabei hält sich in Grenzen.

Natürlich läßt sich das vermeiden, indem man ein Programm schreibt, welches möglichst menschlich vorgeht, also beim Lösen nur Schlußfolgerungen verwendet, die ein menschlicher Löser auch nutzen würde. Aber das führt wieder auf die Kernfrage zurück - wozu ein solches Programm?

Grüße,
uvo

[~ÔttÔ~]

"In dieser Community überwiegt die Meinung, daß händisch erstellte Rätsel höherwertig sind als computergenerierte." -- Das bezweifle ich, bzw. kommt das auf die Qualität des Generators an. Man könnte ja mal einen kleinen Test machen: 10 Sudokus, 5 handgestrickte, 5 computergenerierte. Die Löser müssen die Aufgaben bewerten und auch erraten, welche handgestrickt und welche computergeneriert sind. [Warum Sudoku? Weil da die Generatoren ziemlich ausgereift sind.]

"Programm, welches möglichst menschlich vorgeht, also beim Lösen nur Schlußfolgerungen verwendet, die ein menschlicher Löser auch nutzen würde." -- Alle guten Generatoren arbeiten so. Und da es schwierig und vor allem zeitaufwändig ist, solche zu schreiben, gibt es auch so wenig gute. Wieder Beispiel Sudoku: Da haben zehntausende Programmierer jahrelang zusammengearbeitet, Algorithmen ausgetauscht, etc. Das Ergebnis ist ziemlich gut. Bei anderen Rätselarten sind die Generatoren als Geschäftsgeheimnis gehütet worden - und entsprechend schlecht sind die meisten.

"Aber das führt wieder auf die Kernfrage zurück - wozu ein solches Programm?" -- Weil schon alleine das Programmieren Spaß macht. Weil man danach ein *sehr* tiefes Verständnis der Rätselart hat. Weil das Programm keine Fehler macht, keine Aufgaben mit mehreren Lösungen erstellt. Weil in der heutigen Zeit solche Programme für kommerzielle Überleben notwendig sind.

~ÔttÔ~

[berni]

"In dieser Community überwiegt die Meinung, daß händisch erstellte Rätsel höherwertig sind als computergenerierte." -- Das bezweifle ich, bzw. kommt das auf die Qualität des Generators an.

Es gibt sicherlich gute Generatoren, die gute Rätsel erstellen und es gibt sehr gute Generatoren, die sehr gute Rätsel erstellen. An händisch erstellte Rätsel werden Generatoren aber nie herankommen können, weil Computern die dazu notwendige Kreativität fehlt. Natürlich kann man, wenn man eine kreative Idee hat, diese in den Generator einbauen. Dann kann der Generator auch Rätsel mit dieser Idee generieren. Nur irgendwann kommt man halt an einen Punkt, wo es nur noch genau ein Rätsel zu einer Idee gibt. Da halte ich es dann für absurd, sowas noch zu programmieren. Da hat man mehr aufwand mit, wie wenn man das Rätsel von Hand erstellt. Ich bin jedenfalls nach wie vor der Meinung, dass man von Hand Rätsel erstellen kann, an die kein Generator herankommt.

Man könnte ja mal einen kleinen Test machen: 10 Sudokus, 5 handgestrickte, 5 computergenerierte. Die Löser müssen die Aufgaben bewerten und auch erraten, welche handgestrickt und welche computergeneriert sind.

So eine Art Turingtest für Sudoku? Ich möchte behaupten, dass man das problemlos herausfinden kann!

Weil das Programm keine Fehler macht, keine Aufgaben mit mehreren Lösungen erstellt.

Das wiederum wage ich zu bezweifeln. Wer mal Informatik studiert hat, wird dort gelernt haben, dass man die Abwesenheit von Fehlern in einem Programm nicht beweisen kann. Und das das auch in der Praxis passieren kann, zeigt erst jüngst das Pyramidenrätsel bei CrocoPuzzle: Da habe ich auch jahrelang einen Fehler nicht bemerkt, weil der nur selten auftritt; und selbst wenn er auftritt muss das Rätsel noch nicht unbedingt fehlerhaft sein...

Weil in der heutigen Zeit solche Programme für kommerzielle Überleben notwendig sind.

"Leider" kann ich da nur sagen. Ich würde gerne in einer Welt leben, wo man von handgefertigten Rätseln leben kann. In unserer Welt, wo leider das Geld überall im Mittelpunkt steht, nimmt die Qualität der Produkte immer weiter ab. Darunter leiden die Arbeiter (die meist wissen, was für einen Schrott sie herstellen), die Verbraucher und die Umwelt. Was für Ausmaße das annehmen kann, wird bei Legebatterien deutlich (und auch andernorts - z.B. der Artikel von Günter Wallraff über die Zustände bei einem Lidl-Zulieferer, der vor einiger Zeit im Zeitmagazin erschien, ist da sehr erhellend)...

Berni

[Statistica]

"Leider" kann ich da nur sagen. Ich würde gerne in einer Welt leben, wo man von handgefertigten Rätseln leben kann. In unserer Welt, wo leider das Geld überall im Mittelpunkt steht, nimmt die Qualität der Produkte immer weiter ab. Darunter leiden die Arbeiter (die meist wissen, was für einen Schrott sie herstellen), die Verbraucher und die Umwelt. Was für Ausmaße das annehmen kann, wird bei Legebatterien deutlich (und auch andernorts - z.B. der Artikel von Günter Wallraff über die Zustände bei einem Lidl-Zulieferer, der vor einiger Zeit im Zeitmagazin erschien, ist da sehr erhellend)...

Ob ich bei Sudokus ad hoc rausbekommen würde, was handgefertigt und was computergeneriert ist, weiß ich nicht, aber prinzipiell hast Du natürlich recht...
Den Artikel habe ich damals auch gelesen und es wurde einem richtig schlecht. Ich weiß auch nicht, warum man Aufbackbrötchen für 10 Cent das Stück kaufen muss wenn um die Ecke ein Bäcker ist...? Und dass man bei solchen Preisen (z.B. auch bei Discounter-Milch) mal überlegen sollte wie denn die Handelsspannen sind und was der Erzeuger denn dabei noch verdient. Aber es ist halt auch ein Teufelskreis: Gute Ware kostet etwas mehr, aber nicht jeder hat dieses 'Etwas' und Geiz und Sparen wird halt irgendwie immer mehr groß geschrieben. Das Geld eigentlich Mittel zum Zweck ist wird immer mehr vergessen.
Klammer auf: Eine Gesellschaft ohne Geld kann ich mir auch nicht mehr vorstellen, aber dieser Hype darum, mein Gott Klammer zu.

Ist langsam wohl nix für ein Rätselforum hier...

Lasst uns weiter das saugeile Wetter genießen: Jörg

[SilBer]

Bei so einem Test würde ich sofort mitmachen!! Und obwohl ich vermute, dass ich keine hohe Trefferquote hätte, mir natürlich trotzdem Mühe geben! LG Silke

[~ÔttÔ~]

Berni: "An händisch erstellte Rätsel werden Generatoren aber nie herankommen können, weil Computern die dazu notwendige Kreativität fehlt." -- Das stimmt, zumindest abseits des Mainstreams. Bei Sudoku stellt sich die Frage, on es solche Ideen überhaupt noch gibt. Aber Du (oder wer anders) kannst gerne das Gegenteil beweisen: Finde ein Sudoku, für das es einen Logischen Lösungsweg gibt, dessen Lösung ein Sudoku-Generator/Löser aber nur mit Brute Force lösen kann.

Es kann natürlich sein, dass jemand ein Sudoku findet, das man pfiffigerweise mit unüblichen Überlegungen schneller lösen kann (Beispiel, was ich meine: "Kann man ein Schachbrett, dem zwei diagonal gegenüberliegende Felder fehlen, vollständig mit Dominon belegen?"). Aber solche Aufgaben dürften sehr rar sein und sich keinesfalls am Fließband produzieren lassen.

Berni: "So eine Art Turingtest für Sudoku? Ich möchte behaupten, dass man das problemlos herausfinden kann!" -- Ja, sowas ähnliches sagen die Weinkenner auch, aber deren Trefferquote in Blindverkostungen ist dann trotzdem gering. Präzisierung: Es geht um Sudokus, die man "standardmäßig" lösen kann, nicht um die oben diskutieren Ausnahmen. Und wenn Du meinst, dass Generatoren keine Bildchen malen können, dann probiere mal den Generator von Hirofumi Fujiwara (da kannst Du genau die Felder vorgeben, die die Vorgabezahlen enthalten sollen).

Berni: "Wer mal Informatik studiert hat, wird dort gelernt haben, dass man die Abwesenheit von Fehlern in einem Programm nicht beweisen kann. Und das das auch in der Praxis passieren kann, zeigt erst jüngst das Pyramidenrätsel bei CrocoPuzzle" -- Ja, klar. Ist mit auch schon mal passiert. Trotzdem: Die Fehlerrate ist geringer. Beispiel: Als Sudoku noch kein Moderätsel war und alle Sudokus handgefertigt wurden, habe ich ~100 handgefertigte Aufgaben eines bekannten japanischen Meisters übernommen. Im Laufe der Zeit hat sich herausgestellt dass ~5% davon mehrere Lösungen hatten. Ich sehe das auch bei anderen Rätselarten anderer Autoren. Gibt es eine Statistik, wie viele Aufgaben im Rätselportal fehlerhaft waren? [Aber das sagt nicht viel, da die meisten Löser, die eine Zweitlösung finden, diese nicht melden. Darum habe ich was eingebaut, dass meine Applets Zweitlösungen automatisch melden.]

Off Topic: Schau mal, wie viele Schachaufgaben früher fehlerhaft waren und wie viele heute noch fehlerhaft sind. Standard-Schachaufgaben werden heute alle vor der Veröffentlichung per Computer auf Fehlerfreiheit geprüft. Ausnahme: Retro-Analysen, die widerstehen größtenteils der Computerprüfung - entsprechend hoch ist auch der Anteil an veröffentlichten, aber fehlerhaften Aufgaben.

Berni: "Ich würde gerne in einer Welt leben, wo man von handgefertigten Rätseln leben kann." -- Ja, aber die Zeiten sind vorbei. Möglicherweise ist es das bessere Investment, den "besten Generator der Welt" zu schreiben. Ist natürlich nur dann von Vorteil, wenn die Konsumenten auch merken, dass die damit generierten Aufgaben besser sind. Und für die große Masse der Kosumenten dürfte das nicht gelten :-( [Die merken ja auch nicht, dass frische Semmeln besser sind als Aufgebackene Diskonter-Ware.]

~ÔttÔ~