Kapitola 22: AI v praxi 4 – Logické hádanky

Prolog miluje hádanky. Nejslavnější je Einsteinova hádanka (Zebra Puzzle). Říká se, že ji vyřeší jen 2 % lidí. Pro člověka je to těžké, protože si musí pamatovat spoustu souvislostí ("Kdo bydlí vedle koho?"). Pro Prolog je to hračka. Vyřeší ji za milisekundu. Proč? Protože pro Prolog je to jen hledání kombinace, která splňuje všechna pravidla. Tomuto typu úloh říkáme CSP (Constraint Satisfaction Problems).

22.1 Einsteinova hádanka – Kdo chová rybičky?

Zadání: Máme 5 domů v řadě. Každý má jinou barvu, bydlí v něm člověk jiné národnosti, chová jiné zvíře, pije jiný nápoj a kouří jiné cigarety.

• Brit bydlí v červeném domě.
• Švéd chová psa.
• Dán pije čaj.
• Zelený dům je hned vlevo od bílého.
• Majitel zeleného domu pije kávu.
• Ten, kdo kouří Pall Mall, chová ptáky.
• Majitel žlutého domu kouří Dunhill.
• Ten, kdo bydlí uprostřed, pije mléko.
• Nor bydlí v prvním domě.
• Ten, kdo kouří Blend, bydlí vedle toho, kdo chová kočky.
• Ten, kdo chová koně, bydlí vedle toho, kdo kouří Dunhill.
• Ten, kdo kouří Blue Master, pije pivo.
• Němec kouří Prince.
• Nor bydlí vedle modrého domu.
• Ten, kdo kouří Blend, má souseda, který pije vodu.

Otázka: Kdo chová rybičky?

Obrázek 22.1: Vizualizace Einsteinovy hádanky s pěti domy a jejich obyvateli.

22.2 Řešení v Prologu

Definujeme strukturu ulice jako seznam 5 domů. Každý dům je struktura: dum(Barva, Narodnost, Zvire, Napoj, Cigarety).

reseni(RybyChovatel) :-
    % 1. Definujeme strukturu (5 domů)
    Ulice = [dum(_,_,_,_,_), dum(_,_,_,_,_), dum(zelena,_,_,kava,_), dum(_,_,_,_,_), dum(_,_,_,_,_)], % Předvyplníme známé pozice

    % 2. Fakta (přímá přiřazení)
    member(dum(cervena, brit, _, _, _), Ulice),
    member(dum(_, sved, pes, _, _), Ulice),
    member(dum(_, dan, _, caj, _), Ulice),
    member(dum(_, _, ptaci, _, pall_mall), Ulice),
    member(dum(zluta, _, _, _, dunhill), Ulice),
    member(dum(_, nemec, _, _, prince), Ulice),

    % 3. Relativní pozice (vlevo, vedle)
    vlevo(dum(zelena, _, _, _, _), dum(bila, _, _, _, _), Ulice),
    vedle(dum(_, _, _, _, blend), dum(_, _, kocky, _, _), Ulice),
    vedle(dum(_, _, kone, _, _), dum(_, _, _, _, dunhill), Ulice),
    vedle(dum(_, nor, _, _, _), dum(modra, _, _, _, _), Ulice),
    vedle(dum(_, _, _, _, blend), dum(_, _, _, voda, _), Ulice),

    % 4. Další podmínky
    member(dum(_, _, _, pivo, blue_master), Ulice),

    % 5. Cíl: Kdo chová rybičky?
    member(dum(_, RybyChovatel, rybicky, _, _), Ulice).

% Pomocné predikáty
vlevo(A, B, [A, B | _]).
vlevo(A, B, [_ | T]) :- vlevo(A, B, T).

vedle(A, B, List) :- vlevo(A, B, List).
vedle(A, B, List) :- vlevo(B, A, List).

22.3 Problém 8 dam (N-Queens)

Klasický problém: Jak umístit 8 dam na šachovnici tak, aby se žádné dvě neohrožovaly? (Dáma ohrožuje vše ve svém řádku, sloupci a diagonále).

queens(N, Queens) :-
    length(Queens, N), % Vytvoří seznam N proměnných
    % Queens je seznam čísel sloupců pro každý řádek [1, 5, 8, ...]
    % Hodnoty musí být 1..N
    maplist(between(1, N), Queens), % Každá proměnná získá hodnotu 1 až N
    all_distinct(Queens),           % Každá dáma v jiném sloupci
    safe(Queens).                   % Kontrola diagonál

safe([]).
safe([Queen|Others]) :-
    safe(Others),
    no_attack(Queen, Others, 1).

no_attack(_, [], _).
no_attack(Y, [Y1|Ylist], Xdist) :-
    % Kontrola diagonál: Rozdíl řádků nesmí být roven vzdálenosti sloupců
    % abs(Y1 - Y) je vertikální vzdálenost
    % Xdist je horizontální vzdálenost
    abs(Y1 - Y) =\= Xdist,
    Dist1 is Xdist + 1,
    no_attack(Y, Ylist, Dist1).