Bearbeiten: Dieses Puzzle ist auch als "Einsteins Rätsel" bekannt.
The Who besitzt das Zebra (Sie können die Online-Version hier ausprobieren ) ist ein Beispiel für ein klassisches Puzzleset, und ich wette, dass die meisten Leute bei Stack Overflow es mit Stift und Papier lösen können. Aber wie würde eine programmatische Lösung aussehen?
Basierend auf den unten aufgeführten Hinweisen ...
- Es gibt fünf Häuser.
- Jedes Haus hat seine eigene Farbe.
- Alle Hausbesitzer sind unterschiedlicher Nationalität.
- Sie haben alle verschiedene Haustiere.
- Sie alle trinken verschiedene Getränke.
- Sie alle rauchen verschiedene Zigaretten.
- Der Engländer lebt im roten Haus.
- Der Schwede hat einen Hund.
- Der Däne trinkt Tee.
- Das Gewächshaus befindet sich auf der linken Seite des Weißen Hauses.
- Sie trinken Kaffee im Gewächshaus.
- Der Mann, der Pall Mall raucht, hat Vögel.
- Im gelben Haus rauchen sie Dunhill.
- Im mittleren Haus trinken sie Milch.
- Der Norweger lebt im ersten Haus.
- Der Mann, der Blend raucht, lebt mit Katzen im Haus neben dem Haus.
- In dem Haus neben dem Haus, in dem sie ein Pferd haben, rauchen sie Dunhill.
- Der Mann, der Blue Master raucht, trinkt Bier.
- Der Deutsche raucht Prince.
- Der Norweger wohnt neben dem blauen Haus.
- Sie trinken Wasser im Haus neben dem Haus, in dem sie Blend rauchen.
... wem gehört das Zebra?
language-agnostic
logic
constraint-programming
zebra-puzzle
activout.se
quelle
quelle
Antworten:
Hier ist eine Lösung in Python, die auf Constraint-Programmierung basiert:
Ausgabe:
Es dauert 0,6 Sekunden (CPU 1,5 GHz), um die Lösung zu finden.
Die Antwort lautet "Deutsch besitzt Zebra".
So installieren Sie das
constraint
Modul überpip
: pip Install Python-ConstraintSo installieren Sie manuell:
herunterladen:
$ wget https://pypi.python.org/packages/source/p/python-constraint/python-constraint-1.2.tar.bz2#md5=d58de49c85992493db53fcb59b9a0a45
Auszug (Linux / Mac / BSD):
$ bzip2 -cd Python-Constraint-1.2.tar.bz2 | tar xvf -
Auszug (Windows, mit 7zip ):
> 7z e Python-Constraint-1.2.tar.bz2
> 7z e Python-Constraint-1.2.tar
Installieren:
$ cd python-beschränkung-1.2
$ python setup.py install
quelle
pip install python-constraint
tun? Ich habe das erst vor einem Moment getan und es scheint die erwartete Ausgabe zu geben.In Prolog können wir die Domäne instanziieren, indem wir Elemente aus ihr auswählen :) ( aus Effizienzgründen gegenseitig ausschließende Entscheidungen treffen ). Mit SWI-Prolog,
Läuft ganz sofort:
quelle
Ein Poster erwähnte bereits, dass Prolog eine mögliche Lösung ist. Dies ist wahr und es ist die Lösung, die ich verwenden würde. Allgemeiner ausgedrückt ist dies ein perfektes Problem für ein automatisiertes Inferenzsystem. Prolog ist eine logische Programmiersprache (und ein zugehöriger Interpreter), die ein solches System bilden. Grundsätzlich können Fakten aus Aussagen geschlossen werden, die mit First Order Logic gemacht wurden . FOL ist im Grunde eine fortgeschrittenere Form der Aussagenlogik. Wenn Sie sich entscheiden, Prolog nicht zu verwenden, können Sie ein ähnliches System Ihrer eigenen Kreation verwenden, das eine Technik wie modus ponens verwendet , um die Schlussfolgerungen zu ziehen.
Sie müssen natürlich einige Regeln für Zebras hinzufügen, da diese nirgendwo erwähnt werden ... Ich glaube, die Absicht ist, dass Sie die anderen 4 Haustiere herausfinden und daraus schließen können, dass das letzte das Zebra ist? Sie sollten Regeln hinzufügen, die besagen, dass ein Zebra eines der Haustiere ist und jedes Haus nur ein Haustier haben kann. Diese Art von "gesundem Menschenverstand" -Wissen in ein Inferenzsystem zu bringen, ist die größte Hürde, um die Technik als echte KI zu verwenden. Es gibt einige Forschungsprojekte wie Cyc, die versuchen, dieses allgemeine Wissen durch rohe Gewalt zu vermitteln. Sie haben eine interessante Menge an Erfolg gehabt.
quelle
SWI-Prolog kompatibel:
Beim Dolmetscher:
quelle
So würde ich vorgehen. Zuerst würde ich alle bestellten n-Tupel generieren
5 ^ 6 davon, 15625, leicht zu handhaben. Dann würde ich die einfachen booleschen Bedingungen herausfiltern. Es gibt zehn von ihnen, und jeder von ihnen würde 8/25 der Bedingungen herausfiltern (1/25 der Bedingungen enthalten einen Schweden mit einem Hund, 16/25 enthalten einen Nicht-Schweden mit einem Nicht-Hund). . Natürlich sind sie nicht unabhängig, aber nach dem Herausfiltern sollten nicht mehr viele übrig sein.
Danach haben Sie ein schönes Grafikproblem. Erstellen Sie ein Diagramm, wobei jeder Knoten eines der verbleibenden n-Tupel darstellt. Fügen Sie dem Diagramm Kanten hinzu, wenn die beiden Enden Duplikate in einer n-Tupel-Position enthalten oder gegen Positionsbeschränkungen verstoßen (es gibt fünf davon). Von dort aus sind Sie fast zu Hause. Durchsuchen Sie das Diagramm nach einem unabhängigen Satz von fünf Knoten (wobei keiner der Knoten durch Kanten verbunden ist). Wenn es nicht zu viele gibt, können Sie möglicherweise alle 5-Tupel von n-Tupeln vollständig generieren und sie einfach erneut filtern.
Dies könnte ein guter Kandidat für Code Golf sein. Jemand kann es wahrscheinlich in einer Zeile mit so etwas wie haskell lösen :)
nachträglicher Gedanke: Der anfängliche Filterdurchlauf kann auch Informationen aus den Positionsbeschränkungen entfernen. Nicht viel (1/25), aber immer noch signifikant.
quelle
Eine weitere Python-Lösung, diesmal mit Pythons PyKE (Python Knowledge Engine). Zugegeben, es ist ausführlicher als die Verwendung von Pythons "Constraint" -Modul in der Lösung von @JFSebastian, aber es bietet einen interessanten Vergleich für alle, die eine Rohwissens-Engine für diese Art von Problem suchen.
clues.kfb
Relations.krb
driver.py (eigentlich größer, aber das ist die Essenz)
Beispielausgabe:
Quelle: https://github.com/DreadPirateShawn/pyke-who-owns-zebra
quelle
Hier ist ein Auszug aus der vollständigen Lösung mit NSolver , veröffentlicht bei Einstein's Riddle in C # :
quelle
Hier ist eine einfache Lösung in CLP (FD) (siehe auch clpfd):
Wenn Sie es ausführen, wird Folgendes erzeugt:
quelle
neighbor(X,Y) :- abs(X-Y) #= 1.
In PAIP (Kapitel 11) löst Norvig das Zebra-Rätsel mit einem in Lisp eingebetteten Prolog .
quelle
ES6 (Javascript) -Lösung
Mit vielen ES6-Generatoren und ein bisschen Lodash . Sie benötigen Babel , um dies auszuführen.
Ergebnis:
Die Laufzeit beträgt für mich ungefähr 2,5 Sekunden, aber dies kann durch Ändern der Reihenfolge der Regeln erheblich verbessert werden. Ich habe mich aus Gründen der Klarheit entschlossen, die ursprüngliche Reihenfolge beizubehalten.
Danke, das war eine coole Herausforderung!
quelle
Dies ist wirklich ein Problem zur Lösung von Einschränkungen. Sie können dies mit einer verallgemeinerten Art der Weitergabe von Einschränkungen in logikprogrammierähnlichen Sprachen tun. Wir haben eine Demo speziell für das Zebra-Problem im ALE-System (Attribut Logic Engine):
http://www.cs.toronto.edu/~gpenn/ale.html
Hier ist der Link zur Codierung eines vereinfachten Zebra-Puzzles:
http://www.cs.toronto.edu/~gpenn/ale/files/grammars/baby.pl
Dies effizient zu tun ist eine andere Sache.
quelle
Der einfachste Weg, solche Probleme programmgesteuert zu lösen, besteht darin, verschachtelte Schleifen über alle Permutationen zu verwenden und zu überprüfen, ob das Ergebnis den Prädikaten in der Frage entspricht. Viele der Prädikate können von der inneren Schleife in die äußeren Schleifen gehoben werden, um den Rechenaufwand drastisch zu verringern, bis die Antwort in einer angemessenen Zeit berechnet werden kann.
Hier ist eine einfache F # -Lösung, die aus einem Artikel im F # -Journal abgeleitet wurde :
Die in 9 ms erhaltene Ausgabe ist:
quelle
Das Microsoft Solver Foundation-Beispiel von: https://msdn.microsoft.com/en-us/library/ff525831%28v=vs.93%29.aspx?f=255&MSPPError=-2147217396
quelle
Dies ist eine MiniZinc-Lösung für das in Wikipedia definierte Zebra-Puzzle:
Lösung:
quelle