EMZETT.
Login

Emzett Wiki

Prolog: Klassische Probleme lösen

Properties1
tagsprogrammiersprachen, prolog

3 Min. Lesezeit

Kurz: Typisch für Prolog: Bedingungen formulieren, die Suche erledigt das System.

Teil des Kurses Prolog

Kapitel 5 von 8 im Kurs Prolog. Mit Fortschritt, Quiz und Zertifikat auf der Lernseite.

Kartenfärbung und Logikrätsel

Typisch für Prolog: Bedingungen formulieren, die Suche erledigt das System.

benachbart(X, Y) :- X \= Y.
 
faerbung(A, B, C, D) :-
    Farben = [rot, gruen, blau],
    member(A, Farben), member(B, Farben), member(C, Farben), member(D, Farben),
    benachbart(A, B), benachbart(A, C), benachbart(B, C), benachbart(B, D), benachbart(C, D).
 
main :-
    faerbung(A, B, C, D),
    format("A=~w B=~w C=~w D=~w~n", [A, B, C, D]),
    aggregate_all(count, faerbung(_, _, _, _), Anzahl),
    format("~d Lösungen~n", [Anzahl]).

Ausgabe:

A=rot B=gruen C=blau D=rot
6 Lösungen

SEND + MORE = MONEY mit clpfd

Mit Constraint-Programmierung (library(clpfd)) beschreibt man Einschränkungen statt zu raten:

:- use_module(library(clpfd)).
 
puzzle([S, E, N, D] + [M, O, R, E] = [M, O, N, E, Y]) :-
    Vars = [S, E, N, D, M, O, R, Y],
    Vars ins 0..9,
    all_different(Vars),
    S * 1000 + E * 100 + N * 10 + D + M * 1000 + O * 100 + R * 10 + E #=
    M * 10000 + O * 1000 + N * 100 + E * 10 + Y,
    M #\= 0, S #\= 0,
    label(Vars).
 
main :-
    puzzle(Loesung), writeln(Loesung),
    X #= 3 + 4, writeln(X),
    Y + 2 #= 10, writeln(Y),
    Z in 1..5, Z #> 3, findall(Z, label([Z]), Moegliche), writeln(Moegliche).

Ausgabe:

[9,5,6,7]+[1,0,8,5]=[1,0,6,5,2]
7
8
[4,5]

N-Damen-Problem

:- use_module(library(clpfd)).
 
damen(N, Spalten) :-
    length(Spalten, N),
    Spalten ins 1..N,
    sicher(Spalten),
    labeling([ff], Spalten).
 
sicher([]).
sicher([D|Rest]) :- kein_angriff(D, Rest, 1), sicher(Rest).
 
kein_angriff(_, [], _).
kein_angriff(D, [D2|Rest], Abstand) :-
    D #\= D2,
    D #\= D2 + Abstand,
    D #\= D2 - Abstand,
    A1 is Abstand + 1,
    kein_angriff(D, Rest, A1).
 
main :-
    damen(8, L), writeln(L),
    aggregate_all(count, damen(6, _), Anzahl), writeln(Anzahl).

Ausgabe:

[1,5,8,6,3,7,2,4]
4

Graphensuche

kante(a, b). kante(b, c). kante(c, d). kante(a, e). kante(e, d). kante(d, f).
 
weg(Start, Ziel, Weg) :- weg(Start, Ziel, [Start], Rueckwaerts), reverse(Rueckwaerts, Weg).
weg(Ziel, Ziel, Besucht, Besucht).
weg(Von, Ziel, Besucht, Weg) :-
    kante(Von, Naechster),
    \+ member(Naechster, Besucht),
    weg(Naechster, Ziel, [Naechster|Besucht], Weg).
 
main :-
    findall(W, weg(a, f, W), Wege),
    forall(member(W, Wege), (atomic_list_concat(W, ' -> ', Text), writeln(Text))),
    findall(L-W, (weg(a, f, W), length(W, L)), Paare),
    keysort(Paare, [Kuerzester-KW|_]),
    format("kürzester Weg (~d Knoten): ~w~n", [Kuerzester, KW]).

Ausgabe:

a -> b -> c -> d -> f
a -> e -> d -> f
kürzester Weg (4 Knoten): [a,e,d,f]

Türme von Hanoi

hanoi(0, _, _, _) :- !.
hanoi(N, Von, Nach, Hilf) :-
    N1 is N - 1,
    hanoi(N1, Von, Hilf, Nach),
    format("Scheibe ~w: ~w -> ~w~n", [N, Von, Nach]),
    hanoi(N1, Hilf, Nach, Von).
 
main :- hanoi(3, links, rechts, mitte).

Ausgabe:

Scheibe 1: links -> rechts
Scheibe 2: links -> mitte
Scheibe 1: rechts -> mitte
Scheibe 3: links -> rechts
Scheibe 1: mitte -> links
Scheibe 2: mitte -> rechts
Scheibe 1: links -> rechts

Merke

  • Kartenfärbung, Rätsel und Suchprobleme beschreibt man durch Bedingungen
  • library(clpfd) löst ganzzahlige Constraints mit #=, ins, all_different, label
  • Graphensuche: Besuchte Knoten in einer Liste mitführen
  • Rekursive Probleme wie Hanoi lassen sich in wenigen Zeilen schreiben

Übungsaufgabe

Löse ein Sudoku-Teilfeld (3x3) mit clpfd.

Quiz zur Selbstkontrolle

Weiter im Kurs

Zurück: Backtracking, Cut und Kontrolle

Weiter: DCG, Grammatiken und Sprachverarbeitung

Alle Kapitel: Prolog im Überblick

Graphansicht

Backlinks