Cvičenie 6

V moodli odovzdávajte riešenie úloh Hamiltonovská kružnica a Graph color (môžete ich spojiť do jedného textového súboru, ak budú dostatočne viditeľne oddelené).

Informácie o tom, ako získať DLV a smodels sú na stránke predmetu ASP.

Choice

Napíšte program, ktorý bude mať dva stabilné modely: jeden v ktorom platí predikát a/0 a jeden v ktorom neplatí.

2-choice.sm

a :- not b.
b :- not a.

Choice 2

Napíšte program, ktorý bude mať pre nejaký vstupný predikát a/1 stabilné modely, z ktorých v každom bude predikát b/1 platný pre nejakú podmožinu X z { X | a(X)}. Teda pre

a(1). a(2).

dostaneme modely ( predikát a vynechávam ):

{}
{ b(1) }
{ b(2) }
{ b(1), b(2) }

Ináč povedané pre každé X z a(X) sa chceme nezávisle na ostatných rozhodnúť či v modeli bude alebo nebude b(X).

2-choice2.sm

a(1). a(2). a(3).

b(X) :- not notb(X), a(X).
notb(X) :- not b(X), a(X).

N-Queens

Máme šachovnicu NxN políčok, rozmiestnite na ňu N dám tak aby sa žiadne neohrozovali. Riešenie cez predikát q(X,Y) znamenajúci, že na políčku X,Y je kráľovná.

Choose

Napíšte program, tak aby v každom modeli bol chosen(X) pravdivý práve pre jedno X z option(X).

2-choose.sm

#hide.
#show b(X).

a(1). a(2). a(3). a(4).

b(X) :- not notChosen(X), a(X).
notChosen(X) :- b(Y), X != Y, a(X), a(Y).

2-choose.dlv

a(1). a(2). a(3). a(4).

b(X) :- not notChosen(X), a(X).
notChosen(X) :- b(Y), X != Y, a(X), a(Y).

Graph coloring

Napíšte program, ktorého modely budú zodpovedať rôznym zafarbeniam grafu farbami col1..colN tak aby žíadne dva vrcholy spojené hranou nemali rovnakú farbu.

Graf je zadaný predikátmi node/1 a edge/2, možné farby predikátom color/1. Výsledné zafarbenie bude dané predikátom nodeColor( node, color ).

Mozny vstup:

2-graphcolor-input.sm

color(c1).  color(c2). color(c3).

node(a). node(b). node(c).
edge(a,b). edge(b,c). edge(a,c).

Hamiltonovská kružnica

Zadaný je (neorientovaný) graf, pomocou predikátov edge/2 a node/1. Napíšte program ktorého modely budú zodpovedať možným hamiltonovským kružniciam na tomto grafe. Hrany vybrané do hamiltonovskej kružnice nech sú reprezentované predikátom ham/2.

Vstup:

ham-vstup.dlv

%input:
% d - a - e
% | X | / |
% c - b - f

nd(a). nd(b). nd(c). nd(d).
edge(A,B) :- nd(A), nd(B), A<B.
node(A) :- nd(A).
node(e). edge(a,e). edge(b,e).
node(f). edge(b,f). edge(e,f).