logische schlussfolgerungen automatisieren
Daniel Schüle
schaut Euch diesen Rätsel an
http://www.lustigestories.de/fun/raetsel/raetsel_einstein.php?raetsel_id=9
ich hab in Vergangenheit derartige Rätsel schon gelöst, immer eine
Tabelle aufgebaut ... ich finde sie nicht schwer aber zeitraubend
und Konzentration braucht man auch dafür.
Also dachte mir diesmal meinen Sklaven .. ok meinen Rechner ;)
diesmal zur Lösung zu benutzen. Vor allem die Frage der Modellierung
der Beziehungen hat mich in Zustand des Nachdenkes versetzt.
Wie man das am geschicktesten anstellt. Ich kenne Prolog nur
vom Namen, ich hab in Erinnerung, dass mit Prolog solche
Probleme sich am natürlichsten beschreiben lassen.
Die Regeln müssen sich "elegant" formulieren lassen.
Unten ist meine profane Lösung. Ich habe mich mit Absicht auf eingebaute
Typen beschränkt, in C++ würde mein erster Gedanke wahrscheinlich sein,
wie bringe ich alle nötigen Informationen in einer Klasse zusammen.
Was interessant wäre .. wenn jemand andere Vorschläge liefert,
wie man solches Problem am besten angeht.
Und noch eine Kleinigkeit :) meine Lösung ist auch .. hmm falsch.
Ich würde doch bei einer eindeutigen Lösung (muss nicht sein),
6 übrigbleibende Einträge erwarten, bekomme aber nur 2, und ganz
ohne Fisch :)
***********************************************************************
#!/usr/bin/env python
orders = (1, 2, 3, 4, 5)
pets = ("bird", "fish", "horse", "dog", "cat")
nations =("germ", "brit", "schw", "dane", "norw")
drinks = ("caffee", "beer", "water", "milk", "tea")
houses = ("red", "yellow", "green", "blue", "white")
smokes = ("pallmall", "marlboro", "rothmanns", "dunhill", "winfield")
def allCombinations():
cnt = 0
all = {}
for order in orders:
for nation in nations:
for pet in pets:
for drink in drinks:
for smoke in smokes:
for house in houses:
all[cnt] = {"order" : order,
"nation": nation,
"pet" : pet,
"drink" : drink,
"smoke" : smoke,
"house" : house
}
cnt += 1
return all
"""
# hint 4 "green house left befor white"
# hint 7 "man in the middle drinks milk"
# hint 10 "marlboro smoker beside cat owner"
# hint 11 "dunhill smoker beside horse owner"
# hint 13 "norw beside blue house"
# hint 15 "marlboro smoker beside water drinker"
"""
def beside(what, with, what1, with1):
def search(combinations):
xx, yy = [], []
for i,c in combinations.iteritems():
if c[what] == with:
xx.append(i)
elif c[what1] == with1:
yy.append(i)
ok = []
for x in xx:
for y in yy:
if abs(combinations[x]["order"] - combinations[y]["order"]) == 1:
ok.extend((x,y))
return set(ok)
return search
hints = {
1 : lambda c: (c["nation"] == "brit") ^ (c["house"] == "red"),
2 : lambda c: (c["nation"] == "schw") ^ (c["pet"] == "dog"),
3 : lambda c: (c["nation"] == "dane") ^ (c["drink"] == "tea"),
4 : None,
5 : lambda c: (c["house"] == "green") ^ (c["drink"] == "caffee"),
6 : lambda c: (c["pet"] == "bird") ^ (c["smoke"] == "pallmall"),
7 : lambda c: (c["drink"] == "milk") ^ (c["order"] == 3),
8 : lambda c: (c["house"] == "yellow") ^ (c["smoke"] == "dunhill"),
9 : lambda c: (c["nation"] == "norw") ^ (c["order"] == 1),
10: beside("smoke", "marlboro", "pet", "cat"),
11: beside("smoke", "dunhill", "pet", "horse"),
12: lambda c: (c["drink"] == "beer") ^ (c["smoke"] == "winfield"),
13: beside("nation", "norw", "house", "blue"),
14: lambda c: (c["nation"] == "germ") ^ (c["smoke"] == "rothmanns"),
15: beside("smoke", "marlboro", "drink", "water")
}
def solve():
all = allCombinations()
assert len(all.keys()) == 5**6
d = all.copy()
for hint in (1, 2, 3, 5, 6, 8, 9, 12, 14):
remover = hints[hint]
for index, combination in all.iteritems():
if remover(combination):
del d[index]
all = d.copy()
for hint in (4, 7, 10, 11, 13, 15):
keeper = hints[hint]
if keeper is not None:
keep = keeper(all)
for index in all():
if index not in keep:
del d[index]
all = d.copy()
return all
solution = solve()
print len(solution.keys())
for i in solution.values():
print i
***********************************************************************
ich habe manche Zeilen einbischen nicht Pythonic eingerückt, damit hier
lesbarer wird.
Bin auf Eure Lösungen/Vorschläge gespannt.
Gruss, Daniel
ps.
Klarheit vor Effizienz ist mein Motto bei diesem Beispiel.
5 ** 6 Möglickeiten sind 3 sec für den Rechner.
--
>>> import base64
>>> base64.decodestring('eWFkYW5pZWxAZ214LmRl\n')
Daniel Schüle
[...]
> Wie man das am geschicktesten anstellt. Ich kenne Prolog nur
> vom Namen, ich hab in Erinnerung, dass mit Prolog solche
> Probleme sich am natürlichsten beschreiben lassen.
> Die Regeln müssen sich "elegant" formulieren lassen.
wäre interessant Meinungen derjenigen zu hören, die sich mehr
in der Materie auskennen.
> Unten ist meine profane Lösung. Ich habe mich mit Absicht auf eingebaute
> Typen beschränkt, in C++ würde mein erster Gedanke wahrscheinlich sein,
> wie bringe ich alle nötigen Informationen in einer Klasse zusammen.
unglücklich formuliert .. eher alle Informationen auf Klassen
zuverteilen. Sonst klingt es so, als ob ich alles in eine
Klasse reinzwingen will :)
Stefan Nobis
>> Wie man das am geschicktesten anstellt. Ich kenne Prolog nur
>> vom Namen, ich hab in Erinnerung, dass mit Prolog solche
>> Probleme sich am natürlichsten beschreiben lassen.
>> Die Regeln müssen sich "elegant" formulieren lassen.
> wäre interessant Meinungen derjenigen zu hören, die sich mehr
> in der Materie auskennen.
Prolog ist für solche Logik-Rätsel ein klein wenig
gewöhnungsbedürftig (genaugenommen: Solche Rätsel in
Prädikatenlogik aufzuschreiben kann manchmal recht tricky sein),
aber sehr mächtig und lohnenswert.
Dafür muss man aber nicht zwangsläufig Prolog selbst nehmen, du
kannst dir Prolog in jeder Sprache nachprogrammieren (du brauchst
halt einen Inferenzalgorithmus und Unifikation -- Stichwort:
SLD-Resolution; außerdem sollte man sich schon mal mit
Prädikatenlogik und Horn-Klauseln beschäftigt haben, aber
vielleicht gibt's ja auch für Python schon irgendwo eine fertige
Lib).
Hier mal ein paar Beispiele für Prolog-Programme:
http://hsg.region-kaiserslautern.de/faecher/inf/material/prolog/logik/index.php
,----[ luege.pl ]
| % -*- Mode: Prolog -*-
|
| wahrheiten(/*peter*/ _, /*thomas*/ _, /*frank*/ _).
|
| peter(wahrheiten(P,_,_),P).
| thomas(wahrheiten(_,T,_),T).
| frank(wahrheiten(_,_,F),F).
|
| satz1(W) :-
| peter(W,t), thomas(W,f)
| ;
| peter(W,f), thomas(W,t).
|
| satz2(W) :-
| thomas(W,t), frank(W,f)
| ;
| thomas(W,f), frank(W,t).
|
| satz3(W) :-
| frank(W,t), peter(W,f), thomas(W,f)
| ;
| frank(W,f), peter(W,t), thomas(W,f)
| ;
| frank(W,f), peter(W,f), thomas(W,t)
| ;
| frank(W,f), peter(W,t), thomas(W,t).
|
| wer_wahr(W) :-
| satz1(W),
| satz2(W),
| satz3(W).
|
| /*
| Lösung: peter, frank lügen, thomas sagt wahrheit
| */
`----
,----[ fib.pl ]
| % Fibonacci-Zahlen rekursiv.
|
| rfib(0,1) :- !.
| rfib(1,1) :- !.
| rfib(X,Y) :-
| X > 1,
| X1 is X - 1,
| rfib(X1,Y1),
| X2 is X - 2,
| rfib(X2,Y2),
| Y is Y1 + Y2.
|
| % Fibonacci-Zahlen iterativ.
|
| afib(X,Y) :- afib(X,1,1,Y).
| afib(0,A1,A2,A2) :- !. % Regel eigentlich überflüssig
| afib(1,A1,A2,A2) :- !.
| afib(X,A1,A2,Y) :-
| X > 1,
| X1 is X-1,
| A21 is A1 + A2,
| A11 is A2,
| afib(X1, A11, A21, Y).
`----
--
Stefan.
Stefan Nobis
> schaut Euch diesen Rätsel an
> http://www.lustigestories.de/fun/raetsel/raetsel_einstein.php?raetsel_id=9
Ich sehe gerade, sowas ähnliches habe ich auch mal gelöst:
,----[ fisch.pl ]
| % -*- Mode: Prolog -*-
|
| haeuser([
| haus(/*farbe*/_, /*land*/_, /*getraenk*/_, /*zmarke*/_, /*tier*/_),
| haus(_,_,_,_,_),
| haus(_,_,_,_,_),
| haus(_,_,_,_,_),
| haus(_,_,_,_,_)
| ]).
|
| belegung(H) :-
| haeuser(H),
| H = [_, _, haus(_, _, milch, _, _), _, _], % Aus Performancegründen am Anfang
| H = [haus(_, norweger, _, _, _), _, _, _, _], % Aus Performancegründen am Anfang
| member(haus(rot, brite, _, _, _), H),
| member(haus(_, schwede, _, _, hund), H),
| member(haus(_, daene, tee, _, _), H),
| links_von(haus(gruen, _, _, _, _), haus(weiss, _, _, _, _), H),
| member(haus(gruen, _, kaffee, _, _), H),
| member(haus(_, _, _, pall_mall, vogel), H),
| member(haus(gelb, _, _, dunhill, _), H),
| neben(haus(_, _, _, marlboro, _), haus(_, _, _, _, katze), H),
| neben(haus(_, _, _, _, pferd), haus(_, _, _, dunhill, _), H),
| member(haus(_, _, bier, winfield, _), H),
| neben(haus(blau, _, _, _, _), haus(_, norweger, _, _, _), H),
| member(haus(_, deutscher, _, rothmanns, _), H),
| neben(haus(_, _, _, marlboro, _), haus(_, _, wasser, _, _), H).
|
|
| links_von(H1, H2, [H1, H2|_]).
| links_von(H1, H2, [_|R]) :- links_von(H1, H2, R).
|
| neben(H1, H2, [H1, H2|_]).
| neben(H1, H2, [H2, H1|_]).
| neben(H1, H2, [_|L]) :- neben(H1, H2, L).
|
| farbe(haus(F,_,_,_,_), F).
| land(haus(_,L,_,_,_), L).
| getraenk(haus(_,_,G,_,_), G).
| zmarke(haus(_,_,_,Z,_), Z).
| tier(haus(_,_,_,_,T), T).
|
| portray(haus(F, L, G, Z, T)) :-
| format('~nFarbe: ~p~nLand: ~p~nGetränk: ~p~nZigarettenmarke: ~p~nHaustier: ~p~n', [F, L, G, Z, T]).
|
| wer_besitzt_tier(X) :-
| tier(Haus, X),
| belegung(H),
| member(Haus, H),
| print(Haus).
`----
Vielleicht noch einen wichtigen Hinweis zur Syntax: alles, was mit
Kleinbuchstaben beginnt, sind Literale/Konstanten oder
Regelnamen. Die Großbuchstaben stehen für sogenannte logische
Variablen (nicht zu verwechseln mit Variablen, wie man sie aus
Python kennt) -- logische Variablen sind Platzhalter, quasi wie in
der Mathematik, und das Inferenzsystem von Prolog versucht aus den
Fakten, Regeln sowie der Anfrage sukkzessiv alle gültigen
Belegungen aller log. Variablen zu berechnen.
--
Stefan.
Uwe Schmitt
> Hallo zusammen,
>
> schaut Euch diesen Rätsel an
> http://www.lustigestories.de/fun/raetsel/raetsel_einstein.php?
> raetsel_id=9
>
> ich hab in Vergangenheit derartige Rätsel schon gelöst, immer eine
> Tabelle aufgebaut ... ich finde sie nicht schwer aber zeitraubend
> und Konzentration braucht man auch dafür.
>
> Also dachte mir diesmal meinen Sklaven .. ok meinen Rechner ;)
> diesmal zur Lösung zu benutzen. Vor allem die Frage der Modellierung
> der Beziehungen hat mich in Zustand des Nachdenkes versetzt.
> Wie man das am geschicktesten anstellt. Ich kenne Prolog nur
> vom Namen, ich hab in Erinnerung, dass mit Prolog solche
> Probleme sich am natürlichsten beschreiben lassen.
> Die Regeln müssen sich "elegant" formulieren lassen.
>
http://www.logilab.org/projects/constraint/documentation
an.
könnte helfen,
gruß, uwe
Peter Hoffmann
> Hallo zusammen,
>
> schaut Euch diesen Rätsel an
> http://www.lustigestories.de/fun/raetsel/raetsel_einstein.php?raetsel_id=9
>
Zur Inspiration noch ein paar andere Lösungen.
LISP, C++ und C:
http://www.weitz.de/einstein.html
Python:
http://www.codecomments.com/Python/message202858.html
Gruss Peter
Marc 'BlackJack' Rintsch
> Hallo zusammen,
>
> schaut Euch diesen Rätsel an
> http://www.lustigestories.de/fun/raetsel/raetsel_einstein.php?raetsel_id=9
>
> […]
>
> Was interessant wäre .. wenn jemand andere Vorschläge liefert,
> wie man solches Problem am besten angeht.
Hier ist eine Lösung mit Gustavo Niemeyer's `constraint` Modul:
----8<--------8<--------8<--------8<--------8<----
import pickle
from constraint import Problem, AllDifferentConstraint
def varnames(name):
return ['%s_%d' % (name, i + 1) for i in xrange(5)]
def relates(value_a, value_b):
def f(*args):
for item_a, item_b in zip(args[:5], args[5:]):
if item_a == value_a and item_b == value_b:
return True
return False
return f
def neighbour(value_a, value_b):
def f(*args):
a_values = args[:5]
b_values = args[5:]
for item_a, item_b in (zip(a_values, b_values[1:])
+ zip(a_values[1:], b_values)):
if item_a == value_a and item_b == value_b:
return True
return False
return f
def green_left_of_white(*args):
house = dict((color, house_nr) for house_nr, color in enumerate(args))
return house['green'] < house['white']
def main():
problem = Problem()
nationality_vars = varnames('nationality')
nationalities = ('british', 'danish', 'german', 'norwegian', 'swedish')
color_vars = varnames('color')
colors = ('blue', 'green', 'red', 'white', 'yellow')
drink_vars = varnames('drink')
drinks = ('beer', 'coffee', 'milk', 'tea', 'water')
cigarette_vars = varnames('cigarette')
cigarettes = ('Dunhill', 'Pall Mall', 'Malboro', 'Rothmanns', 'Winfield')
pet_vars = varnames('pet')
pets = ('bird', 'cat', 'dog', 'fish', 'horse')
problem.addVariables(nationality_vars, nationalities)
problem.addVariables(color_vars, colors)
problem.addVariables(drink_vars, drinks)
problem.addVariables(cigarette_vars, cigarettes)
problem.addVariables(pet_vars, pets)
problem.addConstraint(AllDifferentConstraint())
problem.addConstraint(relates('british', 'red'),
nationality_vars + color_vars)
problem.addConstraint(relates('swedish', 'dog'),
nationality_vars + pet_vars)
problem.addConstraint(relates('danish', 'tea'),
nationality_vars + drink_vars)
problem.addConstraint(green_left_of_white, color_vars)
problem.addConstraint(relates('green', 'coffee'), color_vars + drink_vars)
problem.addConstraint(relates('Pall Mall', 'bird'),
cigarette_vars + pet_vars)
problem.addConstraint(lambda a: a == 'milk', ['drink_3'])
problem.addConstraint(relates('yellow', 'Dunhill'),
color_vars + cigarette_vars)
problem.addConstraint(lambda a: a == 'norwegian', ['nationality_1'])
problem.addConstraint(neighbour('Malboro', 'cat'),
cigarette_vars + pet_vars)
problem.addConstraint(neighbour('horse', 'Dunhill'),
pet_vars + cigarette_vars)
problem.addConstraint(relates('Winfield', 'beer'),
cigarette_vars + drink_vars)
problem.addConstraint(neighbour('norwegian', 'blue'),
nationality_vars + color_vars)
problem.addConstraint(relates('german', 'Rothmanns'),
nationality_vars + cigarette_vars)
problem.addConstraint(neighbour('Malboro', 'water'),
cigarette_vars + drink_vars)
solutions = list()
for solution in problem.getSolutionIter():
print solution
solutions.append(solution)
f = open('solutions.dat', 'wb')
pickle.dump(dict(solutions=solutions), f)
f.close()
if __name__ == '__main__':
main()
----8<--------8<--------8<--------8<----
Ciao,
Marc 'BlackJack' Rintsch