TRABAJO FIN DE GRADO
FACULTAD DE MATEM ´
ATICAS
Depa amen o de Ciencias de la Compu aci´on e In eligencia
A i icial
Una in oducci´on a la
p og amaci´on con conjun os de
espues a. Aplicaciones
P esen ado po :
Ma ina Jim´
enez N´
u˜
nez
Di igido po :
And ´
es Co d´
on F anco
Ma
´
ıa Jos´
e Hidalgo Doblado
´
Indice gene al
Abs ac 3
Ag adecimien os 4
In oducci´on 5
1. In oducci´on a CLINGO 8
1.1. Sin axis y sem´an ica de p og amas ASP . . . . . . . . . . . . 8
1.1.1. Sem´an ica in o mal . . . . . . . . . . . . . . . . . . . . 15
1.1.2. Sem´an ica o mal . . . . . . . . . . . . . . . . . . . . . 19
1.2. Sin axis del sis ema CLINGO . . . . . . . . . . . . . . . . . . 26
1.2.1. Algunas gene alidades . . . . . . . . . . . . . . . . . . 26
1.2.2. Disyunci´on ........................ 28
1.2.3. Cons an es boolenas . . . . . . . . . . . . . . . . . . . 28
1.2.4. Funciones a i m´e icas . . . . . . . . . . . . . . . . . . . 29
1.2.5. P edicados de igualdad y o den . . . . . . . . . . . . . 29
1.2.6. In e alos ......................... 31
1.2.7. Ag upaci´on ........................ 31
1.2.8. Condicionales . . . . . . . . . . . . . . . . . . . . . . . 32
1
1.2.9. Res icciones . . . . . . . . . . . . . . . . . . . . . . . 33
2. P opiedades de los p og amas en ASP 35
2.1. Conjun os de espues a: Exis encia, unicidad y p opiedades . . 35
3. Bases de conocimien o 45
3.1. In oducci´on............................ 45
3.2. Modelizaci´on de un ba io . . . . . . . . . . . . . . . . . . . . 46
3.3. Modelizaci´on de las elaciones amilia es . . . . . . . . . . . . 51
3.3.1. De inici´on ecu si a de an epasado . . . . . . . . . . . 51
3.3.2. De inici´on de hijo ´unico . . . . . . . . . . . . . . . . . 53
3.4. Modelizaci´on de un conjun o de medios de anspo e . . . . . 55
4. Rep esen aci´on po de ec o 60
4.1. Rep esen aci´on po de ec o y ipos de excepciones . . . . . . . 60
4.2. Modelizaci´on de la in o maci´on con alo es nulos . . . . . . . . 69
4.3. P io idad en e de ec os . . . . . . . . . . . . . . . . . . . . . 73
4.4. De ec os en bases de conocimien o je ´a quicas . . . . . . . . . 77
5. El pa adigma de p og amaci´on ASP 83
5.1. Ciclos hamil onianos de un g a o . . . . . . . . . . . . . . . . 83
5.2. Sudokus .............................. 89
6. Aplicaciones 94
6.1. PuzzleNu ikabe.......................... 94
6.2. Puzzle Heyawake . . . . . . . . . . . . . . . . . . . . . . . . . 102
6.3. PuzzleMasyu...........................110
2
Abs ac
The main objec i e o his pape is o p esen he answe se p og amming
pa adigm as a ool o model and sol e combina o ial p oblems, in gene al,
and especially NP-comple e o NP-ha d p oblems. Fi s , in chap e s 1 and
2, we a e going o ocus on ca ying ou a heo ical de elopmen o help us
lea ning how o p og am in ASP and, in pa icula , in CLINGO, and some
p ope ies ha ASP p og ams ha e. In he ollowing chap e s, 3 and 4, we
a e going o s udy ep esen a ions o eal si ua ions and p oblems o apply
hese esul s hen o ele an ma hema ical p oblems in chap e 5. Finally,
in chap e 6, we s udy puzzles in which deciding whe he he e is a solu ion
o hem is a NP- comple e p oblem.
3
Ag adecimien os
En p ime luga , me gus a ´ıa ag adece a mis u o es And ´es Co d´on
F anco y Ma ´ıa Jos´e Hidalgo Doblado la ayuda y el apoyo que me han o ecido
du an e odo el p oceso de ealizaci´on de es e abajo.
En segundo luga , quisie a ag adece a mis compa˜ne os la in ini a pacien-
cia que han demos ado ene y el habe me ayudado siemp e. G acias a los
que han empezado es a e apa conmigo y a los que he encon ado po el camino
y me han acompa˜nado has a el in de la misma.
Po ´ul imo, da las g acias a mis he manos y a mis pad es. Nunca en-
con a ´e las palab as pa a ag adece os el ca i˜no que he ecibido du an e odos
es os a˜nos. G acias po con ia en m´ı has a cuando yo misma no lo hice.
Sois mi mayo sue e, mi mayo o gullo y mi ejemplo a segui po y pa a
siemp e.
4

In oducci´on
El p incipal obje i o del p esen e abajo es p esen a el pa adigma de la
p og amaci´on con conjun os de espues as como una he amien a pa a mo-
deliza y esol e p oblemas combina o ios, en gene al, y muy especialmen-
e p oblemas NP-comple os o NP-du os. En la ac ualidad, es gene almen e
acep ado que la clase de complejidad compu acional P, que comp ende los
p oblemas compu acionales esolubles po alg´un algo i mo en iempo poli-
nomial, cap u a la noci´on de “p oblema a able” (es o es, p oblemas que
pueden esol e se en un iempo de ejecuci´on “ azonable” incluso pa a en-
adas de ama˜no g ande). La clase de complejidad NP comp ende aquellos
p oblemas compu acionales ales que, dado un candida o, e i ica si es o
no una soluci´on del p oblema puede hace se en iempo polinomial (pe o, a
p io i, no se sabe si encon a una soluci´on del p oblema puede ambi´en con-
segui se en iempo polinomial). De e mina si las clases P y NP son o no
iguales es el amoso p oblema P e sus NP, uno de los p incipales p oblemas
abie os en la Ma em´a ica ac ual. Den o de la clase NP, des acan un ipo de
p oblemas muy ele an es: los p oblemas NP-comple os. Un p oblema A se
di ´a NP-comple o si: 1) pe enece a la clase NP y 2) cualquie o o p oblema
en la clase NP es educible (en iempo polinomial) a dicho p oblema A. Los
p oblemas NP-comple os cons i uyen, po an o, la clase de los p oblemas
“m´as di ´ıciles” den o de la clase NP. Es bien conocido que hay mul i ud
de p oblemas ma em´a icos in e esan es que esul an se NP-comple os. M´as
gene almen e, un p oblema A se di ´a NP-du o (o NP-ha d) si cualquie p o-
blema en la clase NP es educible (en iempo polinomial) a dicho p oblema
A, aunque aho a A no iene po qu´e pe enece a NP. De nue o, la clase de
p oblemas NP-du os cap u a la idea de “p oblemas compu acionales p esumi-
blemen e di ´ıciles de esol e ”. La p og amaci´on con conjun os de espues a
(o Answe Se P og amming, cuyo ac ´onimo es ASP) es una p og amaci´on
dis in a a la adicional (se enma ca en el campo de la p og amaci´on decla-
a i a) cuyo p incipal en oque es busca soluci´on a p oblemas de b´usqueda
di ´ıciles, p incipalmen e p oblemas NP-comple os o NP-du os.
5
Pa a el desa ollo del abajo, necesi amos aden a nos un poco m´as en la
p og amaci´on con conjun os de espues a, es deci , necesi amos sabe qu´e son
los p og amas de ASP, qu´e elemen os los o man y qu´e p opiedades ienen
es os p og amas y sus soluciones, los denominados conjun os de espues a.
Es o es lo que se es udia en los cap´ı ulos 1 y 2 de es e abajo. En el cap´ı ulo
1, abo damos la sin axis y la sem´an ica, an o o mal como in o mal, de los
p og amas de ASP, en la que se exponen algunos ejemplos pa a ilus a el
con enido. Adem´as, en el cap´ı ulo se habla ambi´en ace ca de la sin axis
de los p og amas de ASP en CLINGO, sis ema que usa emos a lo la go del
abajo pa a ep esen a y esol e los p oblemas que se an con emplando.
En el cap´ı ulo 2, nos cen amos en es udia las p opiedades de los p og amas
de ASP y de sus soluciones. Pa a el cap´ı ulo 1 y 2, se usa p incipalmen e
in o maci´on p oceden e de [GK14], [Li 08], [Li 19], [GKK+19], [GL88] y los
apun es de la p´agina web [HD21] que mencionamos en la bibliog a ´ıa.
Pa a abo da nues o obje i o, la b´usqueda de soluciones pa a p oblemas
NP-ha d, necesi amos ap ende a ep esen a p oblemas eales. Nos cen a-
mos en es o mismo en el cap´ı ulo 3: en es e, emos c´omo cons ui las de-
nominadas bases de conocimien o, en las que se es udia c´omo ep esen a
si uaciones eales, a a ´es de di e sos ejemplos, en los que in en amos mos-
a la impo ancia de la ep esen aci´on de odo el conocimien o, incluido
el que se posee po sen ido com´un, y ambi´en se mues a c´omo ep esen a
si uaciones en las que la in o maci´on no es comple a o posee una es uc u a
je ´a quica. En el cap´ı ulo 4, se es udian las si uaciones en las que apa ecen
de ec os, es deci , si uaciones que se igen po exp esiones como gene al-
men e, habi ualmen e, e c, y las excepciones que nos podemos encon a en
es e ipo de ci cuns ancias, ecupe ando los ejemplos que se exponen en el
cap´ı ulo 3 y a˜nadi´endoles algunos de ec os. Pa a es as secciones, seguimos
p incipalmen e el lib o [GK14] y la p´agina web [HD21].
Mien as que en los cap´ı ulos 3 y 4 nos cen amos p incipalmen e en la
ep esen aci´on del p oblema o si uaci´on que se con empla y en encon a ele-
men os que e i iquen cie as eglas, en el cap´ı ulo 5, el en oque cambia: el
obje i o es busca soluciones a p oblemas a a ´es de educi los a encon a
p og amas de ASP cuyos conjun os de espues a nos den es as mismas solu-
ciones. Exponemos c´omo se pueden plan ea es os p og amas con el es udio
de un p oblema ma em´a ico amoso, el encon a los ciclos hamil onianos de
un g a o, y un puzzle, el sudoku. Pa a es e cap´ı ulo, se uel e a usa an o
la p´agina web [HD21] como el lib o [GK14].
Finalmen e, en el cap´ı ulo 6, plan eamos algunos puzzles in e esan es en
6
la p og amaci´on con conjun os de espues a desde un pun o de is a compu-
acional y dada su ep esen aci´on. Es os puzzles son el Nu ikabe, el puzzle
Heyawake y po ´ul imo, el puzzle Masyu. Con es os puzzles, a amos o al-
men e nues o obje i o, ya que decidi cu´ando hay una soluci´on pa a es os
puzzles y cu´ando no cons i uye un p oblema NP-comple o (p oblema NP
y NP-ha d al mismo iempo). Pa a es e cap´ı ulo, se sigue muy de ce ca la
e e encia [CKK+07]. Pa a ilus a nues os p og amas, se han esuel o al-
gunos ejemplos de puzzles ex a´ıdos de aplicaciones y p´aginas web pa a la
gene aci´on alea o ia de los mismos.
Pa a es e abajo, no se necesi an conocimien os p e ios sob e la p og a-
maci´on con conjun os de espues a ni ace ca del sis ema CLINGO, pues el
desa ollo e´o ico necesa io pa a la comp ensi´on del abajo se ealiza a lo
la go del mismo.
7
Cap´ı ulo 1
In oducci´on a CLINGO
CLINGO es un sis ema desa ollado en la Uni e sidad de Pos dam con la
inalidad de ep esen a y esol e p oblemas en el ma co de la p og amaci´on
de conjun o de espues a (en ingl´es, Answe Se P og amming, de donde
p oceden las siglas ASP). En es e cap´ı ulo, nos cen a emos en p esen a
los elemen os esenciales de es e lenguaje pa a pode en ende los es an es
cap´ı ulos de es e abajo. Pa a una in o maci´on comple a de es e sis ema se
puede isi a la p´agina web: h ps://po assco.o g.
1.1. Sin axis y sem´an ica de p og amas ASP
ASP es un ipo de p og amaci´on decla a i a o ien ada a la esoluci´on de
p oblemas combina o ios. A a ´es de un conjun o de eglas, se desc iben los
obje os de un dominio y las elaciones que hay en e es os obje os.
Pa a pode de ini qu´e es un p og ama de ASP, eamos p ime o los ele-
men os que pueden apa ece en es os p og amas, que son las cons an es, las
unciones, los p edicados y las a iables. El conjun o de los nomb es de las
cons an es del p og ama se denomina ´a O, y de igual o ma, deno a emos
como F,PyVal conjun o de los nomb es de las unciones, los p edicados
y las a iables espec i amen e. Los p edicados exp esan las elaciones que
hay en e los obje os o p opiedades de los mismos. Se denomina signa u a a
Σ =< O, F, P, V >
Veamos algunos ejemplos.
8
•Sa is ace la egla:
p(a) o p(b) ←p(c), no q(c).
pues no sa is ace el cue po.
•Sa is ace la egla:
p(a) ← ¬p(b).
pues sa is ace el cue po y la cabeza de la egla.
•No sa is ace:
p(b) ←p(a), no p(c), no -p(c).
pues sa is ace el cue po de la egla y no sa is ace la cabeza.
Las es icciones, como dec´ıamos an es, son eglas que no poseen cabeza.
Po an o, pa a que un conjun o L sa is aga una es icci´on, alguno de los
li e ales ex endidos del cue po de la egla debe no sa is ace se en L.
Ejemplo 10. El conjun o L={p(a)}sa is ace la es icci´on:
←p(a),¬q(b),no p(c), no ¬q(a).
1.1.1. Sem´an ica in o mal
La de inici´on que imos an es de conjun o de espues a es una de inici´on
in o mal. En es a secci´on, amos a es udia algunos ejemplos de p og amas
y de sus conjun os de espues as co espondien es.
Ejemplo 1.
a←b. % C ee a si c ee b
b. % C ee b
La segunda egla del p og ama nos obliga a c ee b. Como los conjun os de
espues a del p og ama deben sa is ace odas las eglas, po la p ime a egla
es amos obligados a c ee a. As´ı, el conjun o {a b}cons i uye un conjun o
de espues a del p og ama pues sa is ace odas las eglas, no con iene con-
adicciones y e i ica el p incipio de acionalidad. Po o o lado, el conjun o
{a b c} e i ica ambi´en odas las eglas y no con iene con adicciones, pe o
no es un conjun o de espues a pues no e i ica el p incipio de acionalidad
(no debe c ee nada que no es ´e obligado a c ee , y sin emba go no hay
ninguna egla que obligue a c ee c).
15

Ejemplo 2 (Negaci´on cl´asica).
¬a← ¬b.
¬b.
Los conjun os de espues a del p og ama deben sa is ace odas las eglas.
Pa a ello, deben con ene a ¬b(si no, no se sa is ace ´ıa la segunda egla).
Pa a sa is ace la p ime a, como ya sa is acen el cue po, deben sa is ace la
cabeza, luego ambi´en deben con ene a ¬a. Po an o, el conjun o {¬b¬a}
es un conjun o de espues a pa a el p og ama, ya que sa is ace las eglas, no
con iene con adicciones y e i ica el p incipio de acionalidad.
Ejemplo 3 (Disyunci´on epis ´emica).
a o b. %C ee a o c ee b.
Tan o {a}y{b}como {a b}son conjun os que sa is acen las eglas del
p og ama, pe o solo los dos p ime os son conjun os de espues a pues el
e ce o no sa is ace el p incipio de acionalidad (c ee m´as de lo que es ´a
obligado a c ee ).
Es o no signi ica que la disyunci´on epis ´emica sea excluyen e, de hecho el
p og ama:
a o b.
a.
b.
iene como conjun o de espues a a {a b}, lo cual se ´ıa una con adicci´on si
la disyunci´on uese excluyen e (al se excluyen e, se pod ´ıa c ee aob, pe o
no los dos a ez).
Podemos exp esa la disyunci´on excluyen e a a ´es del siguien e p og ama:
a o b.
¬a o ¬b.
En cuyo caso los conjun os de espues a son {a¬b}y{b¬a}.
Ejemplo 4 (Res icciones).
a o b ←c.
c.
←a.
16
La segunda egla nos obliga a c ee c. La p ime a nos indica que si se c ee
c, se c ee aob, luego los conjun os {c a}y{c b}son posibles conjun os
de espues a. Pe o po la e ce a nos es imposible c ee a, luego el ´unico
conjun o de espues a de es e p og ama es {c b}.
Ejemplo 5 (Negaci´on po de ec o).
Supongamos el p og ama:
p(a) ←no p(b).
Es e p og ama nos obliga a c ee p(a) si p(b) no pe enece al conjun o de
ce ezas. Como no hay ninguna egla que enga a p(b) en la cabeza, no
enemos po qu´e c ee p(b), luego se e i ica el cue po de la egla. Pa a
sa is ace la cabeza, se debe c ee p(a). De es e modo, {p(a)}cons i uye el
´unico conjun o de espues a del p og ama.
Si conside amos aho a el siguien e p og ama m´as comple o:
p(a) ←no p(b).
p(d) ←no p(c).
p(c) ←no p(e).
p(b).
La cua a egla nos obliga a c ee p(b). Como se c ee p(b), el cue po de la
p ime a egla no se e i ica. Como no hay ninguna egla que enga a p(e) en
su cabeza, se sa is ace el cue po de la e ce a egla, po an o p(c) o ma ´a
pa e del conjun o de espues a. Como se c ee p(c), no se e i ica el cue po de
la segunda egla. As´ı, s´olo es amos obligados a c ee p(b) y p(c). El conjun o
de espues a de es e p og ama es po an o {p(c) p(b)}.
Pasemos aho a a de ini qu´e se en iende po consecuencia de un p og ama.
Un p og ama P implica un conjun o de li e ales L si L es ´a con enido en odos
los conjun os de espues a de P. Se dice en onces que L es una consecuencia
de P y se deno a po P L.
En la l´ogica cl´asica, la elaci´on de implicaci´on iene la p opiedad de se
mon´o ona, es deci , aunque a˜nadamos nue as hip´o esis adicionales a un eo-
ema, las consecuencias del eo ema o iginal se man ienen. Sin emba go, la
elaci´on de implicaci´on que acabamos de de ini no es mon´o ona: al a˜nadi
nue a in o maci´on al p og ama P, puede ocu i que las consecuencias de P
disminuyan.
17
Siguiendo con el segundo p og ama del Ejemplo 5, podemos e que los
li e ales p(b) y p(c) son consecuencias de es e, sin emba go, al a˜nadi le una
nue a egla:
p(a) ←no p(b).
p(d) ←no p(c).
p(c) ←no p(e).
p(b).
p(e).
p(c) deja de se una consecuencia.
Se denomina consul a a una conjunci´on o disyunci´on de li e ales. A las
consul as que ca ecen de a iables se les llama b´asicas. La espues a a una
consul a se ´a:
1. Si la consul a es conjun i a, L1∧. . . ∧Ln, en onces:
Si P {L1,. . . ,Ln}, en onces la espues a es s´ı.
Si exis e alg´un i al que P Li, en onces la espues a es no.
En o o caso, la espues a es desconocido.
2. Si la consul a es disyun i a, L1o . . . o Ln, en onces:
Si exis e alg´un i al que P Li, en onces la espues a es s´ı.
Si P {L1,. . . ,Ln}, en onces la espues a es no.
En o o caso, la espues a es desconocido.
3. Si la consul a es de la o ma p(X1, . . . , Xn) donde los Xison a iables,
en onces la espues a es una lis a de ´e minos 1, . . . , nde mane a que
Pp( 1, . . . , n).
donde Ldeno a el li e al complemen a io de L.
Conside amos el siguien e ejemplo:
Ejemplo 6 (Hip´o esis del mundo ce ado).
Se conside a el p og ama:
p(a) ←no q(a).
18
Como q(a) no apa ece como cabeza de ninguna egla, se e i ica el cue po
de la ´unica egla del p og ama y po an o el ´unico conjun o de espues a
que posee es {p(a)}. Veamos las espues as a las siguien es consul as:
¿p(a)? La espues a es s´ı, pues p(a) es consecuencia del p og ama.
¿q(a)? La espues a es desconocido, pues ni q(a) ni ¬q(a) son conse-
cuencias del p og ama.
¿p(a) o q(a)? Como el p og ama implica p(a), la espues a es s´ı.
¿p(a) ∧q(a)? La espues a es desconocido, pues p(a) es consecuencia
del p og ama pe o ni q(a) ni ¬q(a) son consecuencias.
Conside emos aho a el p og ama a˜nadiendo una egla m´as, la cual se deno-
mina hip´o esis del mundo ce ado:
p(a) ←no q(a).
¬q(X) ←no q(X).
Debemos en ende es a egla como: si q(X) no pe enece al conjun o de
ce ezas del p og ama en onces q(X) es also. Es o implica que cada ez que
se enga un ´e mino b´asico ,q( ) o ¬q( ) a a pe ence al conjun o de
espues a. As´ı, el ´unico conjun o de espues a del p og ama es {p(a) ¬q(a)}
y po an o las espues as a las consul as an e io es aho a son:
¿p(a)? La espues a es s´ı, pues p(a) es consecuencia del p og ama.
¿q(a)? La espues a es no, pues ¬q(a) es consecuencia del p og ama.
¿p(a) o q(a)? La espues a es s´ı po que el p og ama implica p(a).
¿p(a) ∧q(a)? La espues a es no, pues el p og ama implica ¬q(a).
1.1.2. Sem´an ica o mal
Pa a e la de inici´on o mal de conjun o de espues a, usamos la no-
ci´on de consis encia: Un conjun o L de li e ales b´asicos es consis en e si no
con iene li e ales complemen a ios.
Adem´as, debemos ene en cuen a si el p og ama con iene o no con iene
negaci´on po de ec o.
19
Conjun os de espues a I: p og amas sin negaci´on po de ec o.
Conside emos en p ime luga ´unicamen e p og amas cuyas eglas no con-
ienen negaci´on po de ec o. En es as condiciones, un conjun o L es un con-
jun o de espues a pa a un p og ama P si:
1. L es consis en e.
2. L sa is ace las eglas del p og ama.
3. L es minimal: ning´un subconjun o p opio de L sa is ace odas las eglas
de P.
A con inuaci´on amos a e a ios ejemplos, e omando algunos desc i os
con an e io idad en la Secci´on 1.1.1:
Ejemplo 7 (Ejemplo 1 de la Secci´on 1.1.1)
a←b.
b.
El conjun o L={a b}es un conjun o de espues a pa a es e p og ama
pues:
Es consis en e, no con iene li e ales complemen a ios.
Sa is ace odas eglas del p og ama: sa is ace la egla de cue po ac´ıo
pues b∈L. Pa a sa is ace la p ime a egla, como sa is ace el cue po
de la egla, debe sa is ace la cabeza, lo cual ocu e pues a∈L.
Es minimal: el conjun o ∅no sa is ace la segunda egla. Lo mismo
ocu e con {a}. Po o o pa e, el conjun o {b}no sa is ace la p ime a.
De es e modo, no hay subconjun os p opios de Lque sa is agan odas
las eglas.
Adem´as es el ´unico conjun o de espues a que posee el p og ama: si exis-
iese o o conjun o Mdis in o a Lde mane a que uese ambi´en un conjun o
de espues a del p og ama, en onces pa a sa is ace odas las eglas, L end ´ıa
que es a con enido en M. Pe o en onces Lse ´ıa un subconjun o p opio de
Mque sa is ace ´ıa odas las eglas del p og ama, luego Mno se ´ıa minimal
y po an o llega ´ıamos a una con adicci´on.
Algunas obse aciones ace ca del p og ama:
20

G¿Es auna consecuencia del p og ama? S´ı.
G¿Es buna consecuencia del p og ama? S´ı.
G¿Es ¬auna consecuencia del p og ama? No.
G¿Es ¬buna consecuencia del p og ama? No.
Ejemplo 8 (Ejemplo 3 de la Secci´on 1.1.1: disyunci´on epis ´emica.)
Conside amos de nue o el p og ama:
a o b.
Los conjun os L1={a}yL2={b}son conjun os de espues a pa a es e
p og ama: sa is acen las eglas, son minimales (el ´unico subconjun o p opio
que poseen ambos conjun os es ∅, que no sa is ace la egla) y son consis en es.
Con es a de inici´on o mal de conjun o de espues a se puede e ambi´en
que el conjun o {a b}no es un conjun o de espues a del p og ama: No es
minimal, pues los subconjun os {a}y{b}son p opios y sa is acen las eglas
del p og ama.
Si nos plan eamos algunas de las consul as an e io es, enemos que:
G¿Es auna consecuencia del p og ama? Desconocido, pues pa a se con-
secuencia, adebe ´ıa pe enece a odos los conjun os de espues a del
p og ama pe o a /∈ {b}, y po o o lado, el p og ama ampoco implica
a¬a
G¿Es buna consecuencia del p og ama? Desconocido: al igual que an-
es, el p og ama no implica a bpues es e no pe enece al conjun o de
espues a {a}, y ampoco implica a ¬b.
O o p og ama cuyas eglas con ienen disyunci´on epis ´emica es el siguien-
e:
a o ¬a.
b←a.
b← ¬a.
Veamos que los conjun os de espues a del p og ama son L1={b a}y
L2={b¬a}:
21
1. Ambos conjun os son consis en es.
2. Ve i ican las eglas: L1sa is ace la p ime a egla pues con iene al ´e mino
a, sa is ace la segunda egla pues e i ica an o el cue po, ya que con-
iene al ´e mino a, como la cabeza, po que con iene a b, y sa is ace la
e ce a egla al no sa is ace su cue po. De mane a an´aloga podemos
e que L2sa is ace odas las eglas del p og ama.
3. Son minimales: odos los ´e minos p esen es en L1son necesa ios pa-
a sa is ace las eglas del p og ama, as´ı que es e no puede con ene
subconjun os p opios que e i iquen odas las eglas. Con el mismo
azonamien o ob enemos que L2es minimal.
Como ya comen amos en la Secci´on 1.1, ao ¬ano es una au olog´ıa. As´ı,
si conside amos el p og ama an e io sin la p ime a egla, el ´unico conjun o
de espues a es ∅, ya que nada nos obliga a c ee que ao¬asea cie o, luego
no se e i ica el cue po de ninguna de las dos eglas.
Ejemplo 9.
Conside emos el siguien e p og ama P:
p(a) ←q(a).
¬p(a).
El conjun o L={¬p(a)}es un conjun o de espues a del p og ama pues es
consis en e, sa is ace odas las eglas del p og ama y es minimal (el ´unico
subconjun o p opio que iene es el ∅, que no sa is ace la segunda egla). De
mane a an´aloga que en el ejemplo an e io , se puede e que de hecho es el
´unico conjun o de espues a del p og ama.
Podemos plan ea las siguien es consul as:
¿¬p(a)? La espues a es s´ı, pues P ¬p(a). Po es e mo i o, la es-
pues a a la consul a ¿p(a)? es no.
Las consul as ¿q(a)? y ¿¬q(a)? ob ienen la misma espues a: desconoci-
do, pues ni q(a) ni su complemen a io son consecuencias del p og ama.
Ano aci´on: Es e ejemplo mues a la di e encia con la implicaci´on cl´asica.
Mien as que en nues o caso el li e al ¬q(a) no es una consecuencia, si
hubi´esemos u ilizado la implicaci´on cl´asica s´ı se ´ıa una consecuencia.
22
Conjun os de espues a II: p og amas con negaci´on po de ec o.
Conside emos aho a p og amas P cuyas eglas pueden con ene negaci´on
po de ec o. Deno amos po PSel p og ama educido de P espec o del con-
jun o de li e ales b´asicos S, que se o ma eliminando pa a cada li e al I∈S
odas las eglas del p og ama que con ienen a no Iy eliminando de las
es an es eglas las p emisas que con engan negaci´on po de ec o. En es a
si uaci´on, S es un conjun o de espues a de P si lo es de g ound(P)S.
Ejemplo 10.
Sea el p og ama Q:
Regla 1: p(a) o q(a) ← (a), no p(b), no q(b).
Regla 2: p(a) ← ¬ (a), p(b), no q(b).
Regla 3: q(a) ←no q(b), no (b).
Regla 4: p(b) ←no q(a), (b).
Regla 5: ¬ (b).
Regla 6: p(a) ←q(a), ¬ (b).
y el conjun o S={ (a), p(b), q(a),¬ (b)}.
En onces, el p og ama educido de Q espec o de S es:
p(a) ← ¬ (a), p(b). (P o iene de la egla 2)
q(a). (P o iene de la egla 3)
¬ (b). (Regla 5, no con en´ıa negaci´on po de ec o)
p(a) ←q(a), ¬ (b). (Regla 6, no con en´ıa negaci´on po de ec o)
La egla 1 del p og ama Q ha sido eliminada pues con en´ıa al li e al ex-
endido no p(b) yp(b)∈S. Po el mismo mo i o se elimina la egla 4, pues
apa ece en ella no q(a) yq(a)∈S.
De es e modo, pa a comp oba que S es un conjun o de espues a de un
p og ama P cualquie a, debemos:
1. Calcula g ound(P).
2. Calcula g ound(P)S.
3. Comp oba que S es consis en e y sa is ace odas las eglas de g ound(P)S.
23
4. Comp oba que S es minimal, es deci , ning´un subconjun o p opio de
S sa is ace odas las eglas de g ound(P)S.
P oseguimos con algunos ejemplos:
Ejemplo 11 (Ejemplo 5 de la Secci´on 1.1.1: negaci´on po de ec o.)
Sea P:
p(a) ←no p(b).
Tomemos el conjun o S={p(a)}.El p og ama educido de P espec o de S,
PS, es:
p(a).
ya que como no hay ninguna egla que con enga a no p(a), empezamos
di ec amen e a elimina las p emisas que con ienen negaci´on po de ec o de
las eglas. El conjun o S es el ´unico conjun o de espues a pa a el p og ama
PSluego es conjun o de espues a del p og ama P.
Veamos aho a el siguien e p og ama Qdel Ejemplo 5 de la secci´on 1.1.1:
p(a) ←no p(b).
p(d) ←no p(c).
p(c) ←no p(e).
p(b).
Sea L={p(b) p(c)}. Pa a ob ene el p og ama educido de Q espec o L,
eliminamos la p ime a y la segunda egla, que con ienen a los li e ales ex en-
didos no p(b) yno p(c), y despu´es de las eglas es an es eliminamos las
p emisas que con ienen negaci´on po de ec o, como no p(e). As´ı, QL iene
la o ma:
p(c).
p(b).
Como el conjun o L es conjun o de espues a del p og ama educido, L es
conjun o de espues a del p og ama Q.
Cabe des aca que algunos p og amas de ASP no poseen conjun os de
espues a. A es os p og amas se les denomina inconsis en es.
24
1.2.6. In e alos
Pa a cons ui in e alos, se usan exp esiones de la o ma s.. , donde
suponemos que s <= , que ep esen an la sucesi´on de n´ume os na u ales
consecu i os en e s y . Vemos un ejemplo de in e alos en un c´odigo:
pa es iguales(X,Y) :- X=0..2, Y=0..2, X=Y.
Ob enemos los pa es (X,X) con X en e 0 y 2.
En es e ejemplo, los in e alos se encuen an en el cue po de la egla po
lo que se expanden de o ma disyun i a. Si el in e alo apa ece en la cabeza
de la egla, se expande de o ma conjun i a. Po ejemplo, el hecho:
p(2..5).
se expande al conjun o de hechos:
p(2).
p(3).
p(4).
p(5).
1.2.7. Ag upaci´on
En los p og amas puede apa ece el mismo s´ımbolo de p edicado o unci´on
a ias eces e aluado en dis in os a gumen os. Es e es el caso del ejemplo que
se expone en la secci´on 1.2.5:
cons an e(a). cons an e(ab). cons an e(ac).
en e o(2). en e o(3). en e o(1).
es mayo (X,Y) :- X>Y, cons an e(X), cons an e(Y).
En es e ejemplo, los p edicados cons an e() oen e o() apa ecen m´as
de una ez en el p og ama e aluados en a gumen os di e en es.
La ag upaci´on se usa pa a esc ibi de o ma compac a los a gumen os
de p edicados o unciones, e i ando as´ı el uso ei e ado de es os. Pa a ello,
sepa amos los a gumen os con ";". De es a o ma, el c´odigo an e io puede
eesc ibi se como:
31

cons an e(a;ab;ac).
en e o(2;3;1).
es mayo (X,Y) :- X>Y, cons an e(X), cons an e(Y).
es mayo en e os(X,Y) :- X>Y, en e o(X), en e o(Y).
Como ocu ´ıa en el caso de los in e alos, dependiendo de si la ag upaci´on
se encuen a en la cabeza o en el cue po de la egla, se expande de o ma
conjun i a o disyun i a, espec i amen e.
1.2.8. Condicionales
Pa a esc ibi condicionales en CLINGO, se usa el s´ımbolo “:”. Los condi-
cionales son de la o ma:
L0:L1, . . . , Ln
donde los Ljpa a odo j=0 . . . n son li e ales. A L1, . . . , Lnse le denomina
condici´on. Los li e ales que o man la condici´on se encuen an sepa ados po
comas, al igual que los li e ales que apa ecen en el cue po de las eglas. Pa a
no con undi los li e ales que apa ecen despu´es de un condicional con los
li e ales que cons i uyen la condici´on, se usa el s´ımbolo “;” al inal de la
condici´on. Es o es, supongamos que enemos el p og ama:
elemen o(1..4).
consecu i os(X,Z):- elemen o(X), # alse : elemen o(Y), X<Y, Y<Z;
elemen o(Z), X<Z.
Hemos usado ";"pa a e i a la con usi´on en e los li e ales que pe enecen a
la condici´on del condicional y los que no. El condicional en es a egla e i a
que se e i ique el p edicado consecu i os(X,Z) cuando exis e un n´ume o
in e medio en e X y Z.
En las eglas de los p og amas apa ecen a iables que no se encuen an
suje as a ning´un condicional. Es as a iables se denominan globales y en el
p oceso de ins anciaci´on, se sus i uyen po ´e minos an es que las a iables
que s´ı es ´an suje as a condicionales. Es po es a az´on que no debemos nom-
b a a las a iables que apa ecen en las exp esiones condicionales de o ma
que se puedan con undi con las globales.
32
1.2.9. Res icciones
Las es icciones son exp esiones de la o ma:
s1<1α{ 1:L1;. . . ; n:Ln}<2s2
donde:
Los elemen os iyLison uplas de ´e minos y li e ales espec i amen e.
Si alguna de las uplas de li e ales es ´a ac´ıa, s´olo apa ece la upla de
´e minos que la p ecede (suponemos que no es ´a ac´ıa) y no apa ecen
los dos pun os.
s1ys2son ´e minos y <1y<2son p edicados de compa aci´on.
αes una unci´on que se aplica a las uplas de ´e minos que se encuen an
den o de las lla es una ez se hayan e aluado los condicionales.
CLINGO a a a los elemen os que apa ecen en e las lla es como ele-
men os de un conjun o. Po ello, si apa ece un condicional epe ido den o
de las lla es, se a a como un ´unico elemen o.
Los p edicados <1y<2pueden se eemplazados po “<=”, en cuyo caso
ob enemos una co a supe io o in e io pa a el conjun o.
αpuede se alguna de las unciones siguien es:
#coun , que nos da el n´ume o de elemen os que posee el conjun o.
#sum: Suma de los pesos de las uplas de ´e minos del conjun o (con
peso, nos e e imos al p ime elemen o de la upla). Tambi´en αpuede
se #sum+, en cuyo caso se suman solo los pesos posi i os.
#min y #max, que nos dan el m´ınimo elemen o y el m´aximo del con-
jun o, espec i amen e.
Veamos aho a un ejemplo. Supongamos que que emos e las dis in as
o mas de in e i en 4 emp esas de mane a que ob engamos m´ınimo 1000
eu os. Es o lo podemos esc ibi en CLINGO a a ´es de la es icci´on:
33
1000 <=#sum {300 : emp esa 1; 250: emp esa 2; 600: emp esa 3;
250: emp esa 4}.
Si se decide in e i en la emp esa 1 y en la emp esa 3, el conjun o se
educe a {300,600}. Como al aplica la suma ob enemos 900, no se e i ica
el p edicado de compa aci´on y po an o no se e i ica la es icci´on, luego
no es una posible soluci´on. Pa a que CLINGO nos de odas las soluciones, al
llama lo debemos inclui un ce o (supongamos que hemos llamado al a chi o
donde se encuen a el p og ama Ejemplo Res icciones):
% clingo Ejemplo Res icciones.lp 0
Es o nos da:
% Reading om Ejemplo Res icciones.lp
% Sol ing...
% Answe : 1
% emp esa 1 emp esa 4 emp esa 3
% Answe : 2
% emp esa 1 emp esa 2 emp esa 3
% Answe : 3
% emp esa 1 emp esa 2 emp esa 4 emp esa 3
34
Cap´ı ulo 2
P opiedades de los p og amas
en ASP
A lo la go de es e cap´ı ulo, amos a expone algunas de las p opiedades
que poseen los p og amas de ASP. Adem´as, es udia emos cu´ando un p og a-
ma de ASP es consis en e, es deci , posee alg´un conjun o de espues a, y los
equisi os bajos los cuales es e conjun o de espues a es ´unico.
2.1. Conjun os de espues a: Exis encia, uni-
cidad y p opiedades
Conside emos un p og ama P en ASP compues o po eglas de la o ma:
A0o .. . o Ai←Ai+1, . . . , Am,no Am+1,...,no An
donde los Aipa a i= 0 . . . n son li e ales.
Sean L1yL2dos conjun os de espues a dis in os de P. En onces, se
e i ica que L16⊆ L2yL26⊆ L1(los conjun os no pueden compa a se espec o
a la inclusi´on).
Obse aci´on: Si un conjun o uni a io, po ejemplo L={a}, es un conjun o
de espues a pa a P, no pueden exis i o os conjun os de espues a de P que
con engan al ´e mino a, pues si exis iese un conjun o M al que a∈Men-
onces L⊆My es o no puede ocu i como acabamos de e . Po el mismo
azonamien o, si ∅es un conjun o de espues a de P, en onces es el ´unico
35
conjun o de espues a de P pues odo conjun o L e i ica que ∅ ⊆ L.
Conside emos aho a p og amas de ASP cuyas eglas no con ienen nega-
ci´on cl´asica ni es icciones, es deci , p og amas que solo poseen eglas de la
o ma:
A0o .. . o Ai←Ai+1, . . . , Aj,no Aj+1,..., no Am.(2.1)
donde los Asson ´a omos pa a odo s≥0. Es e ipo de p og amas se deno-
minan no males.
Ejemplo 1.
El siguien e p og ama de una egla:
p(a) ←no p(a).
es un p og ama no mal, ya que no posee es icciones ni negaci´on cl´asica y
adem´as, es inconsis en e.
Con es o, emos que no podemos asegu a la exis encia de conjun os de
espues a pa a p og amas no males. Sin emba go, pa a algunos ipos de p o-
g amas no males pod emos ga an iza no s´olo la exis encia, sino ambi´en la
unicidad de conjun os de espues a. En p ime luga , es udiemos los deno-
minados p og amas posi i os.
De inici´on 1 (P og amas posi i os) Se dice que un p og ama P es po-
si i o si sus eglas no poseen negaci´on po de ec o, es deci , si sus eglas
ienen la o ma:
A0o .. . o Ai←Ai+1, . . . , Aj.(2.2)
donde los Asson ´a omos y s≥0.
Ejemplo 2.
El siguien e p og ama es un p og ama posi i o:
es udian e(juan,colegio).
es udian e(ana,uni ).
es udian e(ma a, ins i u o).
36

es udian e(ma co, uni ).
uni e si a io(X) ←es udian e(X, uni ).
Pa a es udia si es e p og ama posee alg´un conjun o de espues a, usamos
la p oposici´on:
P oposici´on 1 Sea P un p og ama posi i o. En onces, P es consis en e. M´as
a´un, si las eglas de P no con ienen disyunci´on, en onces P posee un ´unico
conjun o de espues a.
Como el p og ama an e io no posee disyunci´on en sus eglas, usando la
p oposici´on que acabamos de e podemos asegu a que el p og ama posee
un ´unico conjun o de espues a.
Ejemplo 3.
En el caso del p og ama (lo esc ibimos con la sin axis de CLINGO pa a
pode u iliza lo):
es udian e(ana;juan).
colegio(X);uni e sidad(X) :- es udian e(X).
sabemos que iene al menos un conjun o de espues a po que es posi i o,
pe o como posee disyunci´on en sus eglas, no podemos asegu a que posea
un ´unico conjun o de espues a. De hecho, CLINGO nos de uel e cua o
conjun os de espues a pa a es e p og ama:
% Answe : 1
% es udian e(ana) es udian e(juan) colegio(ana) uni e sidad(juan)
% Answe : 2
% es udian e(ana) es udian e(juan) colegio(ana) colegio(juan)
% Answe : 3
% es udian e(ana) es udian e(juan) uni e sidad(ana) uni e sidad(juan)
% Answe : 4
% es udian e(ana) es udian e(juan) uni e sidad(ana) colegio(juan)
Ejemplo 4.
Sea el p og ama:
(a,b).
(b,c).
37
(Y,X) ← (X,Y).
(X,Z) ← (X,Y), (Y,Z).
Es e p og ama es posi i o y po lo an o es consis en e. Como no po-
see disyunci´on epis ´emica en las eglas, podemos asegu a ambi´en que el
p og ama iene un ´unico conjun o de espues a.
Obs´e ese que el an e io p og ama posi i o cons uye el cie e sim´e ico
y ansi i o de la elaci´on bina ia /2.
Veamos aho a las nociones de p og amas es a i icados ylocalmen e es-
a i icados, pa a los que ambi´en amos a pode expone algunos esul ados
de exis encia y unidad de conjun os de espues a.
De inici´on 2 (G a o de dependencia) Conside emos un p og ama P cu-
yas eglas son de la o ma (2.1). Sea Q el conjun o o mado po los nomb es
de p edicados del p og ama P. Se denomina g a o de dependencia de P
al g a o cuyos nodos son los s´ımbolos de p edicado p esen es en Q y cuyas
a is as son de la o ma (p1, p2,+) o(p1, p2,−), donde p1yp2son s´ımbolos
de p edicado, que se denominan espec i amen e a co posi i o y nega i o y
que apa ecen en el g a o seg´un:
1. Si exis e una egla en P e i icando que su cabeza con iene un ´a omo
o mado po el s´ımbolo de p edicado p1y su cue po con iene un ´a omo
o mado po p2, en onces el a co (p1, p2,+) apa ece en el g a o.
2. Si exis e una egla en P e i icando que su cabeza con iene un ´a omo
o mado po el s´ımbolo de p edicado p1y su cue po con iene un li e al
de la o ma no I, con I el ´a omo o mado po el s´ımbolo de p edicado
p2, en onces el a co (p1, p2,−)apa ece en el g a o.
De inici´on 3 (Funci´on de ni el) Sea P un p og ama no mal sin a ia-
bles. Las unciones || || que asocian a cada elemen o del conjun o de los
´a omos b´asicos de P un n´ume o na u al se denominan unciones de ni el
pa a P.
Obse aciones:
1. Dos nodos p1yp2de un mismo g a o de dependencia pueden apa ece
conec ados po un a co posi i o (p1, p2,+) y uno nega i o (p1, p2,−)
simul ´aneamen e.
38
2. Sea D=p1o . . . o pnuna disyunci´on epis ´emica de a ´omos de un
p og ama P y sea || || la unci´on de ni el pa a el p og ama. En onces,
||D|| =min{||p1||,...,||pn||}.
Ejemplo 5.
Sea el p og ama no mal:
p(a) o p(c) ←no p(b).
p(c) ←p(d), no p(a).
p(d).
El conjun o de ´a omos b´asicos del p og ama es {p(a),p(b),p(c),p(d)}.
Tenemos que la siguien e unci´on es un ejemplo de unci´on de ni el pa a
el p og ama P:
||p(a)|| = 2, ||p(b)|| = 2, ||p(c)|| = 3, ||p(d)|| = 0
De inici´on 4 (P og amas es a i icados) Sea P un p og ama de la o -
ma (2.1) y sea G su g a o de dependencia. Se dice que P es un p og ama
es a i icado si G no con iene ning´un ciclo nega i o, es o es, ciclos que
con ienen al menos un a co nega i o.
De inici´on 5 (P og amas localmen e es a i icados) Sea un p og ama
P cuyas eglas son de la o ma:
A0o .. . o Ai←Ai+1, . . . , Aj,no Aj+1,..., no Am.
y sea g ound(P)el p og ama o mado po eglas de la o ma:
: A0o .. . o Ai←Ai+1, . . . , Aj,no Aj+1,..., no Am.
En onces se dice que P es ´a localmen e es a i icado si exis e una
unci´on de ni el || || pa a g ound(P)de mane a que pa a cada egla del
p og ama g ound(P), se e i ica:
1. ||Ak|| ≤ ||cabeza( )|| pa a odo Akcon i<k≤j.
2. ||Ak|| <||cabeza( )|| pa a odo Akcon j < k ≤m.
39
Sigamos con los ejemplos.
Ejemplo 6.
Conside amos el p og ama R:
p(a) ←q(a).
(a) ←no q(b).
q(a).
Los nodos del g a o de dependencia de R son p,qy .
El a co (p, q, +) debe apa ece en el g a o po que en la p ime a egla se
encuen a p(a) en la cabeza y q(a) en el cue po.
Del mismo modo, el a co ( , q, −) debe apa ece en el g a o pues en la cabeza
de la segunda egla apa ece (a) y en su cue po, no q(b).
Como no con iene ciclos nega i os, el p og ama R es ´a es a i icado.
Ejemplo 7.
Conside emos el p og ama S:
q(b) ←q(a).
q(a).
Las unciones:
||q(s)||1=1 si s=b
0 si s=a||q(s)||2=0 si s=b
1 si s=a
son unciones de ni el pa a el p og ama S. Sin emba go, || ||2no e i i-
ca las condiciones de la De inici´on 5, pues pa a la egla 1 no se e i ica
||q(a)||2= 1 ≤ ||q(b)||2= 0. A´un as´ı, se iene que S es un p og ama local-
men e es a i icado pues || ||1si e i ica las condiciones de la de inici´on.
Obse aciones:
1. Los p og amas que no con ienen negaci´on cl´asica ni negaci´on po de ec-
o es ´an localmen e es a i icados (una unci´on de ni el || || pa a es os
p og amas que e i ica las condiciones de la De inci´on 5 es la unci´on
que asocia cada ´a omo pkque apa ece en las eglas con el n´ume o 0, es
deci , ||pk|| = 0). En es e caso se encuen a el p og ama S que acabamos
de e en los ejemplos.
2. Si un p og ama es ´a es a i icado, en onces ambi´en es ´a localmen e
es a i icado; sin emba go, el ec´ıp oco no es cie o. El p og ama R
40
ecinos(X,Y) :- esidencia B(X), esidencia B(Y),
no con i ien es(X,Y).
Sin emba go, al ejecu a el c´odigo (las es eglas conjun amen e) ob enemos:
% Answe : 1
% ecinos(julia,julia) ecinos(ma a,julia) ecinos(manuel,julia)
% ecinos( ocio,julia) ecinos(ma a,ma a) ecinos(manuel,ma a)
% ecinos( ocio,ma a) ecinos(julia,manuel) ecinos(ma a,manuel)
% ecinos(manuel,manuel) ecinos( ocio,manuel) ecinos(julia, ocio)
% ecinos(ma a, ocio) ecinos( ocio, ocio)
No a: hemos usado la di ec iz #show pa a que s´olo salgan los hechos ela-
cionados con el p edicado ecinos.
Los hechos ecalcados no debe ´ıan apa ece en el conjun o de espues a ya que
una pe sona no puede se su p opio ecino y adem´as an o Roc´ıo y Manuel
como Ma a y Julia son con i ien es, luego ca ece de sen ido que sean a su
ez ecinos.
El p oblema eside en que:
1. No hemos modelizado el conocimien o ´ımplici o de que una pe sona no
puede se ecina de s´ı misma.
2. No hemos modelizado lo que sabemos po sen ido com´un: la elaci´on
“se con i ien e” es una elaci´on sim´e ica, es deci , si a es con i ien e
con b, b es con i ien e con a, po an o, ni a puede se ecino de b, ni
b de a.
Ca ´ac e sim´e ico de la elaci´on con i ien es/2.
A˜nadimos la siguien e egla al p og ama, que ep esen a el ca ´ac e sim´e i-
co de la elaci´on con i ien es:
con i ien es(X,Y) :- con i ien es(Y,X).
Veamos un segundo in en o (ya de ini i o) de ep esen aci´on de la elaci´on
ecinos. De inimos ecinos/2 de la siguien e o ma: X e Y son ecinos si
ambos esiden en el ba io B, no son la misma pe sona y no cons a que sean
con i ien es. De es a mane a, la egla queda como:
47

ecinos(X,Y) :- esidencia B(X), esidencia B(Y),
no con i ien es(X,Y), X != Y.
y ob enemos la siguien e salida p opo cion´andole a CLINGO el p og ama
comple o:
% Answe : 1
% ecinos(manuel,julia) ecinos( ocio,julia) ecinos(manuel,ma a)
% ecinos( ocio,ma a) ecinos(julia,manuel) ecinos(ma a,manuel)
% ecinos(julia, ocio) ecinos(ma a, ocio)
Ob enemos po an o la siguien e in o maci´on nue a:
1. Manuel y Roc´ıo son ecinos de Julia y Ma a.
2. Julia y Ma a son ecinas de Manuel y Roc´ıo.
A˜nadiendo nue a in o maci´on a la base de conocimien os.
Sabemos aho a que:
1. Albe o eside en el ba io B.
2. No enemos conocimien o de que Albe o i a con nadie m´as.
Modelizamos la in o maci´on usando de nue o los p edicados pe sona/1
y esidencia B/1:
pe sona(albe o).
esidencia B(albe o).
Si le p egun amos al p og ama: ¿son Ma a y Albe o con i ien es?, su es-
pues a es desconocido, pues no apa ecen los li e ales con i ien es(ma a,albe o)
ni -con i ien es(ma a,albe o) en el conjun o de espues a. Sin emba go, no-
so os no enemos cons ancia de que Ma a y Albe o sean con i ien es, y
po an o en nues o d´ıa a d´ıa abaja ´ıamos con la hip´o esis de que no lo
son a menos que se nos indicase lo con a io.
Modelizamos es e conocimien o a a ´es de la hip´o esis del mundo ce a-
do: si no se iene cons ancia de que dos pe sonas dis in as son con i ien es,
en onces no lo son. A˜nadimos as´ı la siguien e egla al p og ama:
48
-con i ien es(X,Y) :- no con i ien es(X,Y), pe sona(X),
pe sona(Y), X!=Y.
Ob enemos como salida:
% ecinos(julia,albe o) ecinos(ma a,albe o)
% ecinos(manuel,albe o) ecinos( ocio,albe o)
% ecinos(albe o,julia) ecinos(manuel,julia)
% ecinos( ocio,julia) ecinos(albe o,ma a)
% ecinos(manuel,ma a) ecinos( ocio,ma a)
% ecinos(albe o,manuel) ecinos(julia,manuel)
% ecinos(ma a,manuel) ecinos(albe o, ocio)
% ecinos(julia, ocio) ecinos(ma a, ocio)
% -con i ien es(julia,albe o) -con i ien es(ma a,albe o)
% -con i ien es(manuel,albe o) -con i ien es( ocio,albe o)
% -con i ien es(albe o,julia) -con i ien es(manuel,julia)
% -con i ien es( ocio,julia) -con i ien es(albe o,ma a)
% -con i ien es(manuel,ma a) -con i ien es( ocio,ma a)
% -con i ien es(albe o,manuel) -con i ien es(julia,manuel)
% -con i ien es(ma a,manuel) -con i ien es(albe o, ocio)
% -con i ien es(julia, ocio) -con i ien es(ma a, ocio)
Hemos ob enido as´ı la siguien e in o maci´on nue a sob e Albe o:
1. Albe o es ecino de Julia, Roc´ıo, Ma a y Manuel.
2. Albe o no con i e con Roc´ıo, Julia, Manuel, ni Ma a.
Es a egla adem´as no p o oca con adicciones, es deci , supongamos aho a
que se sabe que Albe o eside en el ba io B y que con i e con Ma a.
De nue o, modelizamos es a elaci´on a a ´es del p edicado con i ien es/2:
con i ien es(albe o,ma a).
Ob enemos as´ı la salida:
% ecinos(julia,albe o) ecinos(manuel,albe o) ecinos( ocio,albe o)
% ecinos(albe o,julia) ecinos(manuel,julia) ecinos( ocio,julia)
% ecinos(manuel,ma a) ecinos( ocio,ma a) ecinos(albe o,manuel)
% ecinos(julia,manuel) ecinos(ma a,manuel) ecinos(albe o, ocio)
% ecinos(julia, ocio) ecinos(ma a, ocio)
49
% -con i ien es(julia,albe o) -con i ien es(manuel,albe o)
% -con i ien es( ocio,albe o) -con i ien es(albe o,julia)
% -con i ien es(manuel,julia) -con i ien es( ocio,julia)
% -con i ien es(manuel,ma a) -con i ien es( ocio,ma a)
% -con i ien es(albe o,manuel) -con i ien es(julia,manuel)
% -con i ien es(ma a,manuel) -con i ien es(albe o, ocio)
% -con i ien es(julia, ocio) -con i ien es(ma a, ocio)
Aunque sin la egla an e io CLINGO nos de ol ´ıa -con i ien es(albe o,ma a)
en el conjun o de espues a, el inclui la no p o oca con adicci´on pues la adi-
ci´on de la nue a egla hace que el li e al an e io no apa ezca en el conjun o
de espues a al no e i ica se el cue po de la egla del que p ocede.
Algunas ano aciones de la egla (suponiendo que Albe o y Ma a son con-
i ien es):
1. Cuando CLINGO nos de uel e el conjun o de espues a de es e p o-
g ama, en ´el nos apa ece el li e al -con i ien es(albe o,julia). Es o es
po que el sen ido com´un no s´olo nos dice que la elaci´on “se con i-
ien es” es sim´e ica sino que ambi´en es ansi i a: si X es con i ien e
con Y e Y es con i ien e con Z, en onces X y Z son con i ien es, y
es a in o maci´on no apa ece e lejada en el p og ama. La modelizamos
a a ´es de la egla:
con i ien es(X,Z) :- con i ien es(X,Y), con i ien es(Y,Z),
X!=Z.
Es necesa io pone que X y Z no son la misma pe sona: en caso con a-
io, como se e i ica ´ıa con i ien es(albe o,ma a) y, po la sime ´ıa,
con i ien es(ma a,albe o), se ob end ´ıa con i ien es(albe o,albe o),
que no que emos que apa ezca en el conjun o de espues a ya que una
pe sona no con i e consigo misma.
2. Si en ez de la egla an e io , hubi´esemos pues o la egla:
-con i ien es(X,Y) :- no con i ien es(X,Y), X!=Y.
CLINGO nos hubiese de uel o el siguien e mensaje de e o (hemos
llamado al a chi o con las eglas del p og ama Ejemplo Vecinos.lp):
% Ejemplo Vecinos.lp:6:1-51: e o : unsa e a iables in:
% (-con i ien es(X,Y)):-#inc base;X!=Y;no con i ien es(X,Y).
% Ejemplo Vecinos.lp:6:15-16: no e: ‘X’ is unsa e
50
% Ejemplo Vecinos.lp:6:17-18: no e: ‘Y’ is unsa e
que nos indica que las a iables X e Y no son segu as. Una a iable Z
se dice segu a si apa ece al menos una ez en el cue po de la egla sin
es a in luenciada po la negaci´on po de ec o no . En nues o caso, las
a iables X e Y apa ecen a ec adas po no y po el ope ado “!=”, que
ampoco nos si e pa a hace la egla segu a. Po eso, debemos inclui
en la egla los li e ales pe sona(X) ype sona(Y).
3.3. Modelizaci´on de las elaciones amilia es
3.3.1. De inici´on ecu si a de an epasado
Tenemos el siguien e ma co amilia :
1. An onio y Luisa son los pad es de Rosa.
2. Rosa y Ma cos ienen un hijo llamado Lucas.
3. Roc´ıo y Lucas son los pad es de Julie a.
4. Ne ea y Ped o son los pad es de Roc´ıo.
5. Suponemos que X no es el pad e o la mad e de Y si no enemos cons-
ancia de es os hechos.
Modelicemos es a in o maci´on conocida.
Pa a clasi ica los elemen os, usamos el p edicado pe sona/1:
pe sona(ne ea;ped o; ocio;ma cos;an onio;luisa; osa;lucas;
julie a).
Pa a ep esen a las elaciones en e ellos, usamos los p edicados pad e/2
ymad e/2:
pad e(ped o, ocio;an onio, osa;ma cos,lucas;lucas,julie a).
mad e(ne ea, ocio; ocio,julie a;luisa, osa; osa,lucas).
51
Al igual que en la Secci´on 3.2, usamos la hip´o esis del mundo ce ado
pa a modeliza el siguien e conocimien o: si no enemos cons ancia de que X
sea pad e (o mad e) de Y, en onces X no es pad e ( espec i amen e mad e)
de Y. Incluimos po an o las siguien es dos eglas al p og ama:
-pad e(X,Y) :- no pad e(X,Y), pe sona(X), pe sona(Y).
-mad e(X,Y) :- no mad e(X,Y), pe sona(X), pe sona(Y).
No a: enemos que inclui los li e ales pe sona(X) y pe sona(Y) pa a que
la egla sea segu a pues an o X como Y se en a ec adas po la negaci´on po
de ec o.
Concep o: P ogeni o .
Usando los p edicados pad e/2 ymad e/2, de inimos ambi´en el p e-
dicado p ogeni o /2: X es p ogeni o de Y si es pad e o mad e de Y. Mo-
delizamos el conocimien o con las eglas:
p ogeni o (X,Y) :- pad e(X,Y).
p ogeni o (X,Y) :- mad e(X,Y).
Ob enemos con es as eglas la siguien e in o maci´on:
%p ogeni o (ped o, ocio) p ogeni o (an onio, osa) p ogeni o (ma cos,lucas)
% p ogeni o (lucas,julie a) p ogeni o (ne ea, ocio) p ogeni o ( ocio,julie a)
% p ogeni o (luisa, osa) p ogeni o ( osa,lucas)
Concep o: An epasado.
De inimos aho a la elaci´on an epasado de la siguien e o ma ecu si a:
Si X es p ogeni o de Y, en onces X es an epasado de Y.
Si X es an epasado de Y e Y es p ogeni o de Z, en onces X es an epa-
sado de Z.
Implemen amos es a in o maci´on a a ´es de las siguien es eglas:
an epasado(X,Y) :- p ogeni o (X,Y).
an epasado(X,Z) :- p ogeni o (Y,Z),an epasado(X,Y).
52

Comple amos la in o maci´on u ilizando la hip´o esis del mundo ce ado:
si no enemos cons ancia de que X sea an epasado de Y, en onces X no es
an epasado de Y.
-an epasado(X,Y) :- no an epasado(X,Y),pe sona(X), pe sona(Y).
Veamos el modelo que nos da CLINGO:
% an epasado(ped o, ocio) an epasado(an onio, osa) an epasado(ma cos,lucas)
% an epasado(lucas,julie a) an epasado(ne ea, ocio) an epasado( ocio,julie a)
% an epasado(luisa, osa) an epasado( osa,lucas) an epasado(ped o,julie a)
% an epasado(an onio,lucas) an epasado(ma cos,julie a)
% an epasado(ne ea,julie a) an epasado(luisa,lucas) an epasado( osa,julie a)
% an epasado(an onio,julie a) an epasado(luisa,julie a)
Ob enemos in o maci´on nue a, como:
1. Ped o, Ma co, Ne ea, Rosa, An onio y Luisa son an epasados de Julie a.
2. An onio y Luisa son an epasados de Lucas.
3.3.2. De inici´on de hijo ´unico
Poseemos los da os de dos amilias:
La p ime a es ´a o mada po Ne ea y Ped o, que ienen una hija, I ene.
La segunda es ´a o mada po Jose a y Rod igo, que ienen dos hijos,
Ma cos y Ma io.
Veamos c´omo podemos implemen a la in o maci´on.
Pa a clasi ica los elemen os ol emos a usa el p edicado pe sona/1
jun o con el p edicado gene o/2:
pe sona(ne ea;i ene;ped o;jose a; od igo;ma cos;ma io).
gene o(i ene,muje ;ne ea,muje ;jose a,muje ).
gene o(ped o,homb e;ma cos,homb e;ma io,homb e; od igo,homb e).
Pa a modeliza las elaciones en e ellos, usamos los p edicados pad e/2
ymad e/2:
53
pad e(ped o,i ene; od igo,ma io; od igo,ma cos).
mad e(ne ea,i ene;jose a,ma cos;jose a,ma io).
Si le p egun amos aho a a CLINGO si Ne ea es el pad e de Ma cos, su es-
pues a es desconocido, pues ni pad e(ne ea,ma cos) ni -pad e(ne ea,ma cos)
pe enecen al conjun o de espues a del p og ama. Pe o sabemos que Ne ea
no puede se el pad e de Ma cos, po que Ne ea es una muje . Pa a ep esen a
es e conocimien o impl´ıci o, usamos las dos eglas siguien es:
-pad e(X,Y) :- gene o(X,muje ),pe sona(Y), X!=Y.
-mad e(X,Y) :- gene o(X,homb e),pe sona(Y), X!=Y.
Concep o: p ogeni o .
De nue o, implemen amos en la base de conocimien o la elaci´on p oge-
ni o : X es p ogeni o de Y si X es pad e o mad e de Y.
p ogeni o (X,Y) :- pad e(X,Y).
p ogeni o (X,Y) :- mad e(X,Y).
Concep o: he manos.
Supongamos que que emos sabe qui´enes de los indi iduos son he manos.
Tenemos que modeliza la elaci´on he manos: X e Y son he manos si no son la
misma pe sona y ienen los mismos pad es. La de inici´on queda ep esen ada
usando el p edicado he manos/2:
he manos(X,Y) :- pad e(F,X), pad e(F,Y), mad e(M,X),mad e(M,Y),
X != Y.
La elaci´on he manos es sim´e ica y ansi i a:
he manos(X,Y) :- he manos(Y,X).
he manos(X,Z) :- he manos(X,Y),he manos(Y,Z), X != Z.
Si le p opo cionamos es e p og ama a CLINGO, nos de uel e (nos ijamos
s´olo en el p edicado he manos):
%he manos(ma io,ma cos) he manos(ma cos,ma io)
54
As´ı, CLINGO nos p opo ciona la in o maci´on que nos in e esaba conoce :
Ma cos y Ma io son he manos.
Comple i ud de la in o maci´on de la base de conocimien o.
U ilizamos la hip´o esis del mundo ce ado pa a ep esen a lo siguien e:
si no enemos cons ancia de que X e Y sean he manos, en onces X e Y no
son he manos.
-he manos(X,Y) :- no he manos(X,Y), pe sona(X), pe sona(Y).
Concep os: hijo e hijo ´unico.
Nos in e esa sabe qui´enes de los indi iduos son hijos ´unicos. Pa a ello,
de inamos p ime o la elaci´on hijo.
Usando el p edicado p ogeni o /2, modelizamos la elaci´on hijo: X es
hijo de Y si Y es un p ogeni o de X.
hijo(X,Y) :- p ogeni o (Y,X).
Po ´ul imo, ep esen emos la elaci´on “se hijo ´unico”: X es hijo ´unico si
es hijo de alguien y no iene he manos (su p ogeni o no iene m´as hijos):
hijoUnico(X) :- hijo(X,Y), # alse: Z !=X, hijo(Z,Y).
De es a mane a, p opo cion´andole a CLINGO odas las eglas an e io es,
ob enemos la salida:
%hijoUnico(i ene)
Y ob enemos as´ı la in o maci´on que busc´abamos: I ene es hija ´unica.
3.4. Modelizaci´on de un conjun o de medios
de anspo e
En es e ´ul imo ejemplo, amos a e c´omo modeliza una base je ´a quica
de conocimien o: los medios de anspo e.
55
Disponemos de la siguien e in o maci´on:
1. Los eh´ıculos se di iden en ma ´ı imos y no ma ´ı imos.
2. Los subma inos, los ele os y las lanchas son eh´ıculos ma ´ı imos.
3. Los au obuses y las ca a anas son eh´ıculos no ma ´ı imos.
4. Des as e es una ca a ana conc e a.
5. Ul ama es un eh´ıculo ma ´
imo conc e o.
Es udiemos c´omo modeliza es e conocimien o je ´a quico del que dispo-
nemos.
Usa emos el p edicado clase/1 pa a enume a las clases que cons i uyen
la je a qu´ıa:
clase( ehiculo;ma ;no ma ;subma ino; ele o;lancha;
au obus;ca a ana).
Pa a desc ibi la je a qu´ıa en e ellas, usamos el p edicado subclase de/2,
que ep esen a la con enci´on inmedia a o di ec a en e clases:
subclase de(ma , ehiculo).
subclase de(no ma , ehiculo).
subclase de(subma ino,ma ).
subclase de( ele o,ma ).
subclase de(lancha,ma ).
subclase de(au obus,no ma ).
subclase de(ca a ana,no ma ).
Concep o: subclase.
Vamos a modeliza la clausu a ansi i a de la elaci´on subclase de/2:
1. Si C1 es subclase di ec a de C2, en onces C1 es subclase de C2.
2. Si C1 es subclase di ec a de C2 y C2 es subclase de C3, en onces C1 es
subclase de C3.
56
Rep esen aci´on del de ec o 1.
Sigamos con el ejemplo. Pa a ep esen a el de ec o “no malmen e, los
ecinos son amigos”, usamos la egla:
amigos(X,Y) :- ecinos(X,Y), no ab(d amigos(X,Y)),
no -amigos(X,Y).
La elaci´on “se amigos” es sim´e ica:
amigos(X,Y) :- amigos(Y,X).
Adem´as, si X no es amigo de Y, Y ampoco es amigo de X:
-amigos(X,Y) :- -amigos(Y,X).
La in o maci´on que disponemos ace ca de que Ma a y Manuel no son
amigos es una excepci´on ue e, y se ep esen a a a ´es de la egla:
-amigos(ma a,manuel).
De es a mane a, el p og ama ya no es inconsis en e y se ob iene la si-
guien e salida:
% -amigos(ma a,manuel) -amigos(manuel,ma a) amigos( ocio,ma a)
% amigos(ma a, ocio)
Ob eniendo as´ı in o maci´on ace ca de qui´enes de los suje os son amigos:
Ma a y Roc´ıo son amigas.
Modelizaci´on de nue a in o maci´on.
Se dispone aho a de la siguien e in o maci´on:
1. Se sabe si algunas de las pe sonas del ba io se conocen en e ellas.
2. Se sabe que dos pe sonas que no se conocen no pueden se amigas.
Pa a modeliza es a in o maci´on, se usa el p edicado conocidos/2, que
ep esen a que X conoce a Y e Y conoce a X.
63

La elaci´on “se conocidos” es sim´e ica: si se e i ica que X e Y son cono-
cidos, an o X conoce a Y como Y conoce a X, luego ambi´en se e i ica que
Y y X son conocidos. Rep esen amos el ca ´ac e sim´e ico de la in o maci´on
a a ´es de:
conocidos(X,Y) :- conocidos(Y,X).
Po mo i os simila es, si no se e i ica que X e Y sean conocidos, ampoco
puede e i ica se que Y y X sean conocidos, lo que ep esen amos con la egla:
-conocidos(X,Y) :- -conocidos(Y,X).
Rep esen emos aho a la excepci´on ue e: si X e Y no se conocen, en onces
no pueden se amigos.
-amigos(X,Y) :- -conocidos(X,Y).
De es e modo, si no se iene cons ancia de que X e Y se conozcan, en on-
ces no debe aplica se el de ec o 1 ya que X e Y pueden se una excepci´on.
Rep esen amos es a excepci´on d´ebil a a ´es de la egla:
ab(d amigos(X,Y)) :- no conocidos(X,Y), pe sona(X), pe sona(Y).
Veamos en onces qu´e nue o conocimien o ob enemos seg´un la in o maci´on
sob e el p edicado conocidos/2 de la que se disponga:
Ejemplo 1.
Se posee la siguien e in o maci´on ace ca de conocidos/2:
Ma a y Manuel se conocen.
Ma a y Manuel no son amigos.
Rep esen amos es a in o maci´on con las eglas:
conocidos(manuel, ma a).
-amigos(ma a, manuel).
Ob enemos la salida ( ij´andonos en el p edicado amigos/2 y-amigos/2):
% -amigos(ma a,manuel) -amigos(manuel,ma a)
Como no enemos cons ancia de que Ma a y Roc´ıo se conozcan, no ob-
enemos in o maci´on sob e si son o no amigas.
64
Ejemplo 2.
Se posee la siguien e in o maci´on:
Ma a y Manuel se conocen.
Ma a y Manuel no son amigos.
Ma a y Roc´ıo se conocen.
A˜nadimos a las dos eglas an e io es la egla:
conocidos(ma a, ocio).
Ob enemos as´ı:
% -amigos(ma a,manuel) -amigos(manuel,ma a) amigos( ocio,ma a)
% amigos(ma a, ocio)
Luego disponemos de nue a in o maci´on: Ma a y Roc´ıo son amigas.
Ejemplo 3.
Se posee la siguien e in o maci´on:
Ma a y Manuel se conocen.
Ma a y Manuel no son amigos.
Ma a y Roc´ıo no se conocen.
CLINGO nos p opo ciona el conjun o de espues a:
% -amigos(ma a,manuel) -amigos(ma a, ocio) -amigos( ocio,ma a)
% -amigos(manuel,ma a)
Y conseguimos de es e modo nue a in o maci´on: Ma a y Roc´ıo no son
amigas.
Modelizaci´on de una excepci´on ue e usando el axioma de cance-
laci´on.
Aunque an es se haya modelizado una excepci´on ue e sin el axioma de
cancelaci´on (pues no e a necesa io), en o as ocasiones debemos
65
implemen a lo ambi´en en el p og ama. Veamos un ejemplo.
Supongamos que poseemos la siguien e in o maci´on:
1. Ma a, Manuel y Roc´ıo i en en el ba io B.
2. Manuel y Roc´ıo i en jun os.
3. De ec o 1: no malmen e, los ecinos el ba io B son amigos.
4. Las pe sonas de la casa c1 y las pe sonas de la casa c2 no son amigas.
5. Manuel i e en la casa c1.
6. Una pe sona no puede i i en m´as de una casa.
7. Se conoce in o maci´on sob e qui´enes de los suje os, apa e de Manuel,
i en en c1 o c2.
Rep esen amos las dos casas usando el p edicado casa/1:
casa(c1).
casa(c2).
Rep esen amos que Manuel i e en la casa c1 con el p edicado i i En/2:
i i En(manuel,c1).
Una p opiedad ace ca de la elaci´on “ i i en” es que si una pe sona X
i e en una casa C y es con i ien e con o a pe sona Y, en onces Y i e en
C:
i i En(Y,C) :- i i En(X,C), con i ien es(X,Y).
Usando la siguien e egla, modelizamos que una pe sona no puede i i
en m´as de una casa:
- i i En(X,C) :- i i En(X,C1), C!=C1, casa(C).
Rep esen emos aho a la excepci´on ue e: si una pe sona i e en c1 y o a
pe sona i e en c2, en onces no son amigas. Se usa pa a ello la egla siguien e:
-amigos(X,Y) :- i i En(X,c1), i i En(Y,c2).
Necesi amos acompa˜na la egla con el axioma de cancelaci´on pa a e-
p esen a que si no enemos cons ancia de que ni X ni Y i en en c1 o c2,
66
en onces puede que X e Y no sean amigos. Po an o, usamos las siguien es
dos eglas:
ab(d amigos(X,Y)) :- no - i i En(X,c1), no - i i En(Y,c2),
pe sona(X), pe sona(Y).
ab(d amigos(X,Y)) :- no - i i En(Y,c1), no - i i En(X,c2),
pe sona(X), pe sona(Y).
Veamos como an es qu´e conocimien o nue o podemos ob ene seg´un la
in o maci´on que poseamos del p edicado i i En/2.
Ejemplo 1.
Se dispone de la siguien e in o maci´on:
Ma a, Manuel y Roc´ıo se conocen en e ellos.
Ma a no i e en c2.
Rep esen amos que Ma a, Manuel y Roc´ıo se conocen en e ellos:
conocidos(ma a,manuel;ma a, ocio;manuel, ocio).
Rep esen amos aho a que Ma a no i e en c2:
- i i En(ma a,c2).
En es e caso, ob enemos la salida:
% amigos(manuel,ma a) amigos( ocio,ma a) amigos(ma a,manuel)
% amigos(ma a, ocio)
Luego hemos ob enido la siguien e in o maci´on:
1. Ma a y Roc´ıo son amigas.
2. Ma a y Manuel son amigos.
Ejemplo 2.
Se dispone de la siguien e in o maci´on:
67
Ma a, Manuel y Roc´ıo se conocen en e ellos.
Ma a i e en c2.
Rep esen amos el conocimien o a a ´es de las eglas:
conocidos(ma a,manuel;ma a, ocio;manuel, ocio).
i i En(ma a,c2).
Ob enemos la salida:
% -amigos(manuel,ma a) -amigos( ocio,ma a) -amigos(ma a,manuel)
% -amigos(ma a, ocio)
Luego ob enemos la siguien e in o maci´on:
1. Ma a y Manuel no son amigos.
2. Roc´ıo y Ma a no son amigas.
Ejemplo 3.
No disponemos in o maci´on ace ca de d´onde i e Ma a.
En es e caso, no ob enemos en el conjun o de espues a nada ace ca de si
Ma a es amiga o no de Manuel y Roc´ıo. Es o es po que se aplica el axioma
de cancelaci´on an e io , que a˜nadimos a la excepci´on ue e.
Si no lo hubi´esemos conside ado, el de ec o se aplica ´ıa y el agen e consi-
de a ´ıa que son amigos en e ellos.
Caso especial: de ec os con in o maci´on comple a.
Sea el de ec o d: “no malmen e, los elemen os de c e i ican la p opiedad
p” y supongamos que se iene un conjun o ede excepciones. Si la in o maci´on
que se iene sob e ees comple a, en onces el axioma de cancelaci´on en las
excepciones d´ebiles se educe a:
ab(d(X)) :- e(X).
y en las excepciones ue es, dicho axioma puede se omi ido.
68

En el ejemplo desc i o an e io men e, si hubi´esemos enido una lis a con
las pe sonas que i en en la casa c1y con las pe sonas que i en en la casa
c2, la excepci´on ue e se hubiese ep esen ado ´unicamen e po la egla:
-amigos(X,Y) :- i i En(X,c1), i i En(Y,c2).
pues una pe sona de la que no se conoce d´onde i e deja de se una posible
excepci´on ya que, al se la in o maci´on sob e las pe sonas que i en en c1o
c2comple a, si i iese en una de es as casas, el agen e lo sab ´ıa.
4.2. Modelizaci´on de la in o maci´on con a-
lo es nulos
Los de ec os pueden usa se ambi´en pa a modeliza in o maci´on en la que
apa ecen alo es nulos, es o es, cons an es que indican que el alo de una
a iable o unci´on es desconocido.
Supongamos que enemos una emp esa con a ios depa amen os, y dis-
ponemos de la siguien e in o maci´on:
1. Nu ia es la enca gada del depa amen o D1.
2. Luis es el enca gado del depa amen o D2.
3. En los depa amen os D3yD4se a a con a a a una pe sona como
enca gado en e las que lo solici en.
4. De ec o 1: no malmen e, si una pe sona no es ´a en la lis a de enca gados
jun o a un depa amen o, no se enca ga de ese depa amen o.
5. Los solici an es de los pues os acan es son Nu ia y Ma cos.
La lis a de los enca gados con sus espec i os depa amen os es la siguien e:
Pe sona Depa amen o
Nu ia D1
Luis D2
Vacan e D3
Vacan e D4
69
En es e ejemplo, “Vacan e” es un alo nulo que nos indica que las pe -
sonas enca gadas de los depa amen os D3yD4es ´an po de e mina .
Veamos c´omo modeliza es a in o maci´on.
En p ime luga , ep esen amos los elemen os que in e ienen en el ejem-
plo con los p edicados pe sona/1 ydepa amen o/1:
pe sona(nu ia;luis;ma cos).
depa amen o(d1;d2;d3;d4).
Rep esen amos la in o maci´on de la lis a de enca gados con el p edicado
enca gado/2:
enca gado(nu ia,d1;luis,d2; acan e,d3; acan e,d4).
y modelizamos ambi´en con el p edicado solici an e/1 los suje os que
han solici ado los pues os acan es:
solici an e(nu ia;ma cos).
Rep esen amos el de ec o 1 a a ´es de la egla:
-enca gado(X,D) :- pe sona(X), depa amen o(D),
no ab(d enca gado(X,D)), no enca gado(X,D).
que se lee como “si no enemos cons ancia de que X pueda se una excepci´on
del de ec o y ampoco enemos cons ancia de que X sea la pe sona enca ga-
da del depa amen o D, es deci , no enemos cons ancia de que X sea una
excepci´on, en onces X no es la pe sona enca gada del depa amen o D”.
Sin emba go, los enca gados de los depa amen os D3yD4es ´an po de-
e mina : se con a a ´a a alg´un solici an e aunque sus nomb es no apa ezcan
en la lis a jun o a es os depa amen os. Es a in o maci´on po an o es una
excepci´on d´ebil del de ec o 1 y se modeliza con la egla:
ab(d enca gado(X,D)) :- solici an e(X), enca gado( acan e,D).
Es a egla ep esen a el siguien e conocimien o: “si X es un solici an e,
en onces puede se un enca gado de los depa amen os D con pues os acan es
aunque su nomb e no apa ezca en la lis a jun o a ellos”.
De es a mane a, ob enemos la siguien e salida:
70
% enca gado(nu ia,d1) enca gado(luis,d2) enca gado( acan e,d3)
% enca gado( acan e,d4) -enca gado(nu ia,d2) -enca gado(luis,d1)
% -enca gado(luis,d3) -enca gado(luis,d4) -enca gado(ma cos,d1)
% -enca gado(ma cos,d2)
As´ı, se dispone de la siguien e in o maci´on nue a:
Nu ia no se enca ga del depa amen o D2.
Luis no se enca ga de los depa amen os D1,D3yD4.
Ma cos no se enca ga de los depa amen os D1yD2.
No ob enemos in o maci´on sob e si Nu ia y Ma cos son o no enca gados de
los depa amen os D3yD4ya que son los solici an es, igu an como posibles
excepciones.
Tambi´en pod ´ıamos habe ep esen ado la in o maci´on del siguien e modo:
Pe sona Depa amen o
Nu ia D1
Luis D2
Vacan e D3
Vacan e D4
{Nu ia, Ma cos}D3
{Nu ia, Ma cos}D4
donde aho a el alo nulo “Vacan e” nos indica que los enca gados de los de-
pa amen os D3yD4es ´an po con a a y el alo nulo “{Nu ia, Ma cos}”
nos indica qui´enes son los posibles enca gados de los susodichos depa amen-
os. Pa a ep esen a es a in o maci´on, sus i uimos las dos ´ul imas eglas del
p og ama:
solici an e(nu ia;ma cos).
ab(d enca gado(X,D)) :- solici an e(X), enca gado( acan e,D).
po las eglas:
enca gado(nu ia,d3) | enca gado(ma cos,d3).
enca gado(nu ia,d4) | enca gado(ma cos,d4).
71
que ep esen an, a a ´es de la disyunci´on epis ´emica, que Nu ia y Ma cos
pod ´ıan se los enca gados de los depa amen os D3yD4.
Se ob ienen cua o posibles soluciones:
%Answe : 1
% enca gado(nu ia,d1) enca gado(luis,d2) enca gado( acan e,d3)
% enca gado( acan e,d4) -enca gado(nu ia,d2) -enca gado(luis,d1)
% -enca gado(luis,d3) -enca gado(luis,d4) -enca gado(ma cos,d1)
% -enca gado(ma cos,d2) enca gado(nu ia,d3) enca gado(ma cos,d4)
%Answe : 2
% enca gado(nu ia,d1) enca gado(luis,d2) enca gado( acan e,d3)
% enca gado( acan e,d4) -enca gado(nu ia,d2) -enca gado(luis,d1)
% -enca gado(luis,d3) -enca gado(luis,d4) -enca gado(ma cos,d1)
% -enca gado(ma cos,d2) enca gado(nu ia,d3) enca gado(nu ia,d4)
%Answe : 3
% enca gado(nu ia,d1) enca gado(luis,d2) enca gado( acan e,d3)
% enca gado( acan e,d4) -enca gado(nu ia,d2) -enca gado(luis,d1)
% -enca gado(luis,d3) -enca gado(luis,d4) -enca gado(ma cos,d1)
% -enca gado(ma cos,d2) enca gado(ma cos,d3) enca gado(ma cos,d4)
%Answe : 4
% enca gado(nu ia,d1) enca gado(luis,d2) enca gado( acan e,d3)
% enca gado( acan e,d4) -enca gado(nu ia,d2) -enca gado(luis,d1)
% -enca gado(luis,d3) -enca gado(luis,d4) -enca gado(ma cos,d1)
% -enca gado(ma cos,d2) enca gado(ma cos,d3) enca gado(nu ia,d4)
Todos los conjun os de espues a nos p opo cionan la siguien e in o ma-
ci´on:
1. Ni Luis ni Ma cos son los enca gados del depa amen o D1.
2. Ni Nu ia ni Ma cos son los enca gados del depa amen o D2.
3. Luis no se enca ga de los depa amen os D3yD4.
En la p ime a soluci´on, ob enemos:
Nu ia es la enca gada del depa amen o D3.
Ma cos es el enca gado del depa amen o D4.
72
-pe enece(X,C2) :- pe enece(X,C1), he manas(C1,C2).
Modelizaci´on de de ec os y excepciones.
Rep esen amos los colo es a a ´es del p edicado colo /1:
colo (na anja;blanco;neg o;azul).
An es de empeza con la ep esen aci´on de los de ec os, modelizamos la
siguien e in o maci´on conocida: un elemen o s´olo puede se de un colo .
-deColo (X,C) :- deColo (X,C1), C1 !=C, colo (C), colo (C1).
Rep esen amos el de ec o 1, “en gene al, las ca a anas son blancas”, como
sigue:
deColo (X,blanco) :- pe enece(X,ca a ana), no ab(d1(X)),
no -deColo (X,blanco).
Rep esen amos el de ec o 2, “los eh´ıculos no ma ´ı imos son habi ual-
men e de colo neg o”, a a ´es de la egla:
deColo (X,neg o) :- pe enece(X,no ma ), no ab(d2(X)),
no -deColo (X,neg o).
Pa a modeliza el de ec o 3: los au obuses no malmen e son na anjas, se
u iliza:
deColo (X, na anja) :- pe enece(X,au obus), no ab(d3(X)),
no -deColo (X,na anja).
Rep esen amos el de ec o 4, “no malmen e, los au obuses u ´ıs icos son
de colo azul”, con la egla:
deColo (X,azul) :- pe enece(X, u is ico), no ab(d4(X)),
no -deColo (X,azul).
Y po ´ul imo, se modeliza el de ec o 5, “en gene al, los eh´ıculos ma ´ı imos
son blancos”, con la egla:
79

deColo (X,blanco) :- pe enece(X,ma ), no ab(d5(X)),
no -deColo (X,blanco).
La in o maci´on ace ca de si X es una ca a ana no es comple a: si no
enemos cons ancia de que X, que es un eh´ıculo no ma ´ı imo, no es una
ca a ana, puede se una excepci´on del de ec o 2 (puede que no sea de colo
neg o). Es o se ep esen a a a ´es de una excepci´on d´ebil:
ab(d2(X)) :- no -pe enece(X,ca a ana), elemen o(X).
De la misma mane a, la in o maci´on sob e si X es un au ob´us o un au ob´us
u ´ıs ico no es comple a. Po es e mo i o, si no enemos cons ancia de que
X no sea alguno de es os eh´ıculos, puede que X sea una excepci´on de los
de ec os 2 y 3 espec i amen e. Rep esen amos de nue o la in o maci´on como
excepciones d´ebiles:
ab(d2(X)) :- no -pe enece(X,au obus), elemen o(X).
ab(d3(X)) :- no -pe enece(X, u is ico), elemen o(X).
Veamos en onces qu´e in o maci´on nos p opo ciona CLINGO sob e los
colo es de la ca a ana Des as e y el eh´ıculo ma ´ı imo Ul ama . Ob enemos
la salida:
% deColo (des as e,blanco) deColo (ul ama ,blanco)
De es e modo, hemos conseguido los siguien es da os ace ca de Ul ama
y Des as e:
Des as e es de colo blanco.
Ul ama es de colo blanco.
Es e conocimien o es consis e pues Des as e e a una ca a ana, luego se
ha aplicado el de ec o 1, y Ul ama e a un eh´ıculo ma ´ı imo, lo que quie e
deci que se ha aplicado el de ec o 5.
Adici´on de un nue o elemen o a la in o maci´on conocida.
Veamos qu´e in o maci´on ob enemos ace ca del colo de un nue o ele-
men o, Le i, que es un eh´ıculo no ma ´ı imo, seg´un la in o maci´on que se
disponga sob e es e.
80
Ejemplo 1.
S´olo conocemos que Le i es un eh´ıculo no ma ´ı imo. Rep esen amos es a
in o maci´on con las eglas:
elemen o(le i).
es un(le i,no ma ).
En la salida, no ob enemos in o maci´on sob e el colo de Le i, pues pue-
de se una excepci´on del de ec o 2 (no hemos especi icado que no es una
ca a ana, au ob´us o au ob´us u ´ıs ico).
Ejemplo 2.
Si especi icamos aho a que Le i es un au ob´us:
es un(le i,au obus).
Seguimos sin ob ene in o maci´on de su colo , ya que no hemos especi i-
cado que no sea un au ob´us u ´ıs ico.
Ejemplo 3.
Si aho a especi icamos que es un au ob´us u ´ıs ico:
es un(le i, u is ico).
Ob enemos:
% deColo (le i,azul)
Luego se ob iene que Le i es azul. Es o es g acias al de ec o 4, que iene
p io idad espec o a los de ec os 2 y 3.
Es deci , aunque an e io men e imos que la p io idad en e de ec os se
pod´ıa ep esen a median e excepciones ue es, en es e caso, se ha ep esen-
ado a a ´es de excepciones d´ebiles (a a ´es de es as, hemos ep esen ado
que el de ec o 4 iene p e e encia sob e el de ec o 3 y que el de ec o 3 iene
p e e encia sob e el de ec o 2).
De es a mane a, se obse a que la in o maci´on m´as espec´ı ica iene p e-
e encia sob e la in o maci´on menos espec´ı ica. En gene al, si enemos C1
subclase de C2, y los de ec os: “no malmen e, los elemen os de C2 ienen la
p opiedad P” y “no malmen e, los elemen os de C1 no ienen la p opiedad
P”, en onces el segundo de ec o p edomina sob e el p ime o. Es o es lo que
81
se conoce como p incipio de especi icidad.
82
Cap´ı ulo 5
El pa adigma de p og amaci´on
ASP
En las secciones an e io es, nos hemos cen ado en la modelizaci´on de
bases de conocimien o en ASP con la inalidad de ob ene elemen os que
e i icasen cie os p edicados o pa a e la e acidad o alsedad de cie as
a i maciones. En es a secci´on, se p e ende mos a c´omo se pueden usa las
bases de conocimien o en ASP pa a encon a soluciones a dis in os p oble-
mas educi´endolos a encon a conjun os de espues as de p og amas de ASP.
El p ocedimien o de esoluci´on de p oblemas a a ´es de educi los a encon-
a conjun os de espues a de p og amas en ASP es lo que se denomina el
pa adigma de p og amaci´on ASP.
En nues o caso, amos a cons ui bases de conocimien o cuyos conjun os
de espues a den soluci´on a los dos p oblemas siguien es: halla los ciclos
hamil onianos de un g a o y encon a la soluci´on de sudokus.
5.1. Ciclos hamil onianos de un g a o
Nues o obje i o es cons ui un p og ama de ASP cuyos conjun os de
espues as sean los ciclos hamil onianos de un g a o di igido G.
Un ciclo hamil oniano de un g a o G es un camino que pasa po odos
los ´e ices o nodos del g a o una sola ez y empieza y e mina en el mismo
´e ice o nodo.
83
Pa a ep esen a el g a o, se usan los p edicados:
inicial/1, donde inicial( 0) nos indica que el nodo 0es el nodo del
que se pa e (y po an o, debe se ambi´en el ´ul imo nodo en isi a se).
nodo/1, pa a ep esen a los nodos del g a o.
a co/2, donde a co( 0, 1) ep esen a el a co del g a o G que pa e del
nodo 0y accede al nodo 1.
Los ciclos hamil onianos (que se ´an los conjun os de espues a del p o-
g ama) se ep esen an po conjun os en( 0, 1), en( 1, 2), . . . , en( k, 0),
donde el p edicado en( i, j) ep esen a que el a co que pa e de iy accede
a jpe enece al ciclo hamil oniano < 0, 1, 2, ... k, 0>.
Pa a que un conjun o en( 0, 1), en( 1, 2), . . . , en( k, 0) o me un ciclo
hamil oniano de G, se debe cumpli :
1. Se accede y se sale de un ´e ice como m´aximo una ez.
2. Debe con ene a odos los nodos del g a o.
Se ep esen a que se accede como m´aximo una ez a cada ´e ice V del
g a o de la siguien e mane a: si el a co que pa e desde uno de los nodos V1
del g a o y accede a V ya es ´a en el ciclo hamil oniano, es deci , se e i ica
en(V1,V), en onces no puede exis i o o ´e ice V2 dis in o de V1 al que
el a co que pa e de V2 y accede a V es ´e en el ciclo hamil oniano. La egla
que modeliza es a in o maci´on es:
-en(V2,V) :- en(V1,V), V1 != V2, nodo(V1), nodo(V2), nodo(V).
De mane a an´aloga, ep esen amos que s´olo se sale de un ´e ice V una
´unica ez: si el a co que pa e de V y llega a V1 es ´a en el ciclo hamil oniano,
en onces cualquie o o a co que pa a de V y llegue a un ´e ice V2 dis in o a
V1 no puede es a en el ciclo hamil oniano. Es a in o maci´on queda ecogida
po la egla:
-en(V,V2) :- en(V,V1), V1 != V2, nodo(V1), nodo(V2), nodo(V).
Rep esen emos la o a condici´on que debe e i ica un ciclo hamil oniano:
debe con ene a odos los nodos del g a o.
84

Pa a ep esen a es e conocimien o, p ime o debemos de ini la elaci´on
alcanzable: el nodo V es alcanzable en el ciclo que se es ´e conside ando si
exis e un a co que pa e del ´e ice inicial y accede a V o si en el ciclo exis e
un a co que pa e de un ´e ice V1 alcanzable y accede a V. Es e conocimien o
se ep esen a a a ´es del p edicado alcanzable/1, que es ecu si o:
alcanzable(V) :- en(V1,V), inicial(V1), nodo(V).
alcanzable(V) :- en(V1,V), alcanzable(V1), nodo(V).
Pa a comple a la in o maci´on sob e los ´e ices que son y no son alcan-
zables, usamos la hip´o esis del mundo ce ado: si no enemos cons ancia de
que un ´e ice sea alcanzable, en onces supond emos que no es alcanzable.
-alcanzable(V) :- no alcanzable(V), nodo(V).
De es a mane a, se ep esen a que el ciclo debe pasa po odos los nodos
con la es icci´on siguien e, que impide la p esencia de nodos no alcanzables
en el conjun o de espues a:
:- -alcanzable(V), nodo(V).
Con es as condiciones, CLINGO es capaz de de e mina cu´ando un ciclo
es hamil oniano y cu´ando no.
Aho a, necesi amos ep esen a los posibles candida os a ciclos hamil o-
nianos, es deci , los posibles caminos que podemos o ma en G. Pa a ello,
siemp e que exis a un a co en G que pa a de V1 y acceda a V2, se consi-
de a ´a la opci´on de inclui lo o no en el ciclo. Modelizamos es a in o maci´on
usando la disyunci´on:
en(V1,V2) | -en(V1,V2) :- a co(V1,V2).
Veamos algunos ejemplos de g a os y sus ciclos hamil onianos.
Ejemplo 1.
Conside emos el g a o di igido G de la igu a 5.1.
Que emos encon a los ciclos hamil onianos que pa en del nodo a.
Pa a desc ibi a es e g a o, usamos los p edicados nodo/1 ya co/2:
nodo(a;b;c;d;e).
a co(a,b;b,a;b,c;c,d;d,e;e,b;e,a;a,c).
85
y con el p edicado inicial/1, indicamos el nodo del que que emos que pa a:
inicial(a).
CLINGO nos de uel e pa a es e g a o dos conjun os de espues a, que
son los ´unicos ciclos hamil onianos que posee el g a o:
%Answe : 1
% en(a,b) en(b,c) en(c,d) en(d,e) en(e,a)
%Answe : 2
% en(b,a) en(c,d) en(d,e) en(e,b) en(a,c)
Figu a 5.1: g a o G
Vemos que ambos conjun os sa is acen los equisi os pa a se ciclos ha-
mil onianos: acceden y pa en de odos los nodos una ´unica ez y empiezan
y e minan en el ´e ice a.
Ejemplo 2.
Conside emos los dos g a os de la igu a 5.2.
De nue o, que emos halla los ciclos hamil onianos de ambos g a os que
pa en del nodo a.
Es os dos g a os son el mismo sal o po un a co: el g a o J1posee un a co
que pa e del nodo c y accede al nodo i y el g a o J2no posee es e a co. Es o
hace que en J2no se pueda accede a los nodos h, i, , g, d y e, luego en es e
caso no debemos ob ene ning´un ciclo hamil oniano.
86
(a) G a o J1(b) G a o J2
Figu a 5.2: g a os J1yJ2
Modelizamos el g a o J1a a ´es de las eglas:
nodo(a;b;c;d;e; ;g;h;i).
a co(a,b;b,a;b,c;c,i;d,a;d,e;e,d;e,a; ,e; ,g;g,h;
g, ;g,d;h, ;h,g;i,g;i,h).
inicial(a).
Pa a es e g a o, ob enemos como soluci´on es ciclos hamil onianos:
%Answe : 1
% en(a,b) en(b,c) en(c,i) en(d,a) en(e,d) en( ,e) en(g, ) en(h,g) en(i,h)
%Answe : 2
% en(a,b) en(b,c) en(c,i) en(d,a) en(e,d) en( ,e) en(g,h) en(h, ) en(i,g)
%Answe : 3
% en(a,b) en(b,c) en(c,i) en(d,e) en(e,a) en( ,g) en(g,d) en(h, ) en(i,h)
Modelizamos aho a el g a o J2:
nodo(a;b;c;d;e; ;g;h;i).
a co(a,b;b,a;b,c;d,a;d,e;e,d;e,a; ,e; ,g;g,h;g, ;g,d;h, ;
h,g;i,g;i,h).
87
inicial(a).
CLINGO nos de uel e:
%UNSATISFIABLE
En e ec o, como dijimos, es e g a o no posee ciclos hamil onianos pues
es os eco en odos los nodos del g a o y J2con iene algunos nodos a los
que no se puede accede .
Pa a gene a los candida os a ciclos hamil onianos, ambi´en podemos
modi ica el p og ama an e io como sigue: se sus i uye la ´ul ima egla que
acabamos de expone , que se u iliza como hemos is o pa a gene a los po-
sibles caminos candida os a se ciclos hamil onianos, po una egla que se
denomina egla de elecci´on.
Las eglas de elecci´on ienen dos o mas:
s1<1{p(X) : q(X)}<2s2:- cue po.
s1<1{p(c1); . . . ;p(c )}<2s2:- cue po.
donde s1ys2son en e os no nega i os los cuales pueden omi i se y <1y
<2son p edicados de compa aci´on.
La p ime a egla a˜nade a los conjun os de espues a del p og ama cie os
conjun os S o mados po ´a omos p( ) de mane a que s1≤ |S| ≤ s2y ales
que si un ´a omo p( )∈S, en onces el co espondien e q( ) debe pe enece al
conjun o de espues a. Es o es, la p ime a egla es ´a gene ando un p edicado p
en unci´on de un p edicado qp e iamen e de inido. La segunda egla pe mi e
la adici´on a los conjun os de epues a de conjun os S o mados po ´a omos
p(ci) en e los que se encuen an en la cabeza de la egla de mane a que
s1≤ |S| ≤ s2.
En nues o caso, eemplazamos la ´ul ima egla del p og ama pa a halla
los ciclos hamil onianos de un g a o po la egla:
{en(V1,V2) : a co(V1,V2)}.
con la que se es ´a de iniendo el p edicado en/2 en unci´on del p edicado
a co/2 de o ma que pa a cada a co de G, se plan ea inclui lo o no en el
ciclo que se es ´e conside ando.
88
si es NP y NP-ha d al mismo iempo. Se puede p oba que el Nu ikabe
es un p oblema NP-ha d, y decidi si exis e soluci´on del Nu ikabe es un
p oblema NP-comple o. Pa a m´as in o maci´on, puede isi a se el siguien e
enlace: enlace.
Las eglas del Nu ikabe son:
1. Todas las celdas nume adas deben pe manece blancas.
2. Toda celda blanca debe pe enece a una isla.
3. Cada isla debe con ene una ´unica celda nume ada.
4. Cada isla debe es a o mada po el n´ume o de celdas blancas que
indique la casilla nume ada que con iene.
5. Las celdas blancas de cada isla deben es a o ogonalmen e conec adas.
6. Dos islas no pueden es a conec adas.
7. Todas las celdas neg as deben es a conec adas o ogonalmen e.
8. Ning´un subconjun o de celdas neg as puede o ma un cuad ado 2x2.
Se puede isi a ambi´en el siguien e enlace pa a encon a m´as in o ma-
ci´on sob e las eglas del Nu ikabe: enlace. Adem´as, es e nos pe mi e juga en
l´ınea, lo que puede esul a de u ilidad pa a gene a m´as ejemplos de puzzles
Nu ikabe apa e de los que amos a expone .
Comencemos pues con la modelizaci´on de los puzzles Nu ikabe.
Supongamos que nos dan una cuad ´ıcula ec angula de dimensi´on nxm
(n ilas y m columnas). Se ep esen a la cuad ´ıcula desc ibiendo las celdas que
es ´an nume adas con el p edicado nume ada/3, donde nume ada(X,Y,A)
se e i ica si la celda que ocupa la posici´on (X,Y) en la cuad ´ıcula, con X la
ila e Y la columna, con iene el n´ume o A (po an o, es a celda a a pe ene
a una isla de ama˜no A).
Pa a ep esen a las ilas y las columnas de la cuad ´ıcula, se usa el p edi-
cado ila/1 ycol/1:
ila(1..n).
col(1..m).
95

Se ep esen an los dos colo es de celdas que podemos ene con el p e-
dicado colo /1, donde b ep esen a el colo blanco y n ep esen a el colo
neg o:
colo (n).
colo (b).
Vamos a gene a odas las posibles cuad ´ıculas que se pueden conside a
seleccionando subconjun os de celdas que pe manece ´an blancas y pin ando
de neg o las celdas es an es.
Pa a gene a las cuad ´ıculas, se usa el p edicado celda/3, de o ma que
celda(C,X,Y) ep esen a que la celda que es ´a en la posici´on (X,Y) es de
colo C. A a ´es de una egla de elecci´on, se gene an los conjun os de celdas
que pe manece ´an blancas:
{celda(b,X,Y)}1 :- ila(X), col(Y).
Pa a pin a las es an es celdas de neg o, usamos la siguien e egla:
celda(n,X,Y) :- no celda(b,X,Y), ila(X), col(Y).
Aho a, amos a implemen a las eglas pa a elimina las cuad ´ıculas que
no las e i iquen.
REGLA 1.
Debemos modeliza la egla 1: “ odas las celdas nume adas deben pe ma-
nece blancas”. Rep esen amos la egla con una es icci´on, de mane a que
pa a e i ica se no puede ocu i que una celda (X,Y) sea neg a y a su ez
es ´e nume ada:
:- nume ada(X,Y,A), celda(n,X,Y).
REGLAS 2 Y 5.
Pa a la implemen aci´on de 2 y 5, usamos la egla 3: po las eglas 2, 3 y 5,
sabemos que cada celda blanca debe pe enece a una isla, que cada isla debe
con ene una ´unica celda nume ada y que las celdas blancas de cada isla se
conec an o ogonalmen e. Po an o, oda celda blanca debe es a conec ada
o ogonalmen e a una celda nume ada.
Pa a ep esen a es e conocimien o, amos a de ini an es algunos con-
cep os.
96
P ime o, amos a de ini la elaci´on “se adyacen es”: las celdas adyacen-
es a una celda (X,Y) son las celdas (X+1,Y), (X-1,Y), (X,Y+1), (X,Y-1).
Rep esen amos que la celda (X,Y) y la celda (U,V) son adyacen es usando
el p edicado ady/4:
ady(X,Y,U,V) :- ila(X), ila(U), col(Y), col(V),
|X-U|+|Y-V| == 1.
No a: ambi´en se puede denomina o ogonal, pues ep esen a que dos
celdas es ´an conec adas o ogonalmen e.
P oseguimos modelizando cu´ando dos celdas se an a conec a o ogonal-
men e a a ´es de un colo .
Pa a ello, in oducimos el p edicado conec adas/4, que se e i ica si:
1. conec adas(C,X,Y,X,Y) se e i ica si (X,Y) es una celda de colo C. Es
deci , amos a conside a que una celda (X,Y) de colo C es ´a conec ada
consigo misma a a ´es del colo C.
2. conec adas(C,X,Y,U,V) se e i ica si la celda (U,V) es de colo C y si
exis e una celda in e media que es adyacen e a (U,V) y es ´a conec ada
o ogonalmen e a a ´es del colo C a (X,Y).
El p edicado es ´a de inido po ecu si´on, as´ı que lo ep esen amos con las
eglas:
conec adas(C,X,Y,X,Y) :- celda(C,X,Y).
conec adas(C,X,Y,U,V) :- celda(C,U,V), conec adas(C,X,Y,X1,Y1),
ady(X1,Y1,U,V).
Finalmen e, pa a ep esen a que oda celda blanca debe es a
conec ada o ogonalmen e a una celda nume ada, se de ine el p edicado
conec adaB/2, donde conec adaB(X,Y) se e i ica si (X,Y) es ´a conec ada
o ogonalmen e a a ´es del colo blanco a una celda nume ada, e imponemos
que oda celda blanca e i ique el p edicado conec adaB/2 a a ´es de una
es icci´on:
97
conec adaB(X,Y) :- conec adas(b,X,Y,U,V), celda(b,X,Y),
nume ada(U,V,A).
:- celda(b,X,Y), no conec adaB(X,Y).
REGLAS 3 Y 6.
Pa a ep esen a las eglas 6 y 3, usamos la egla 2: se iene que cada isla
con iene una ´unica celda nume ada, que oda celda blanca pe enece a una
isla y que dos islas no pueden es a conec adas. Es o implica que dos celdas
nume adas no an pode es a conec adas o ogonalmen e a a ´es del colo
blanco po que sino, dos islas dis in as es a ´ıan conec adas.
:- conec adas(b,X,Y,U,V), nume ada(X,Y,A), nume ada(U,V,M),
(X,Y) != (U,V).
REGLA 4.
Pa a la egla 4: “cada isla debe es a o mada po el n´ume o de celdas
blancas que indique la casilla nume ada que con iene”, amos a de ini qu´e
se conside a po isla.
La isla es a ´a o mada po una casilla nume ada (X,Y), supongamos que
es al que se e i ica nume ada(X,Y,A), y po exac amen e A celdas blancas
que se conec an o ogonalmen e a a ´es del colo blanco a la celda nume-
ada. Es deci , el ca dinal del conjun o de celdas blancas que se conec an
o ogonalmen e a (X,Y) debe se exac amen e A. Como po la egla 3, cada
isla con iene una ´unica celda nume ada, iden i icamos la isla con la celda
nume ada:
isla(X,Y) :- nume ada(X,Y,A), A {conec adas(b,X,Y,U,V)}A,
ila(X), col(Y).
Todas las celdas nume adas deben de ini una isla:
:- nume ada(X,Y,A), no isla(X,Y).
REGLA 7.
Veamos c´omo ep esen a la egla 7: “ odas las celdas neg as deben es a
conec adas o ogonalmen e”. Pa a ello, usamos de nue o una es icci´on: no
pueden exis i dos celdas (X,Y) y (U,V) de colo neg o que no es ´en conec-
98
adas o ogonalmen e a a ´es del colo neg o.
:- celda(n,X,Y), celda(n,U,V), no conec adas(n,X,Y,U,V).
REGLA 8.
Po ´ul imo, ep esen emos la egla 8: “ning´un subconjun o de celdas ne-
g as puede o ma un cuad ado 2x2”. Pa a ello, de inimos p ime o cu´ando
un subconjun o de celdas neg as de ine un cuad ado: si enemos una celda
(X,Y) neg a, es ´a de ine un cuad ado cuando las celdas (X,Y+1), (X+1,Y)
y (X+1,Y+1) ambi´en son neg as.
cuad adoN(X,Y) :- celda(n,X,Y), celda(n,X,Y+1), celda(n,X+1,Y),
celda(n,X+1,Y+1).
Finalmen e, se impide que cualquie celda o me un cuad ado de celdas
neg as usando una es icci´on:
:- cuad adoN(X,Y).
Como al p incipio odas las celdas de la cuad ´ıcula son blancas, la soluci´on
del Nu ikabe se ´a el conjun o de celdas que inalmen e se han pin ado de
neg o. As´ı, de inimos el p edicado celdaNeg a/2, que se e i ica si la celda
es ´a pin ada de neg o:
celdaNeg a(X,Y) :- celda(n,X,Y).
Po an o, la soluci´on a nues o p oblema nos la da ´a el conjun o de li e-
ales de la o ma celdaNeg a(X,Y) que apa ezca en el conjun o de espues a:
#show celdaNeg a/2.
Veamos aho a algunos ejemplos de puzzles Nu ikabe.
Ejemplo 1.
En es e ejemplo, amos a conside a el Nu ikabe de la igu a 6.1.
Vamos a desc ibi es e puzzle con usando el p edicado nume ada/3:
nume ada(2,1,2). nume ada(3,3,2). nume ada(3,5,4). nume ada(5,2,2).
nume ada(5,6,3). nume ada(6,4,2). nume ada(8,4,3). nume ada(9,2,6).
nume ada(10,7,4).
Pa a ca ga el iche o, debemos especi ica le a CLINGO el n´ume o de
99
ilas y columnas de la cuad ´ıcula (lo que denominamos como n y m, espec-
i amen e). Gua dando el c´odigo del Nu ikabe en el a chi o nu ikabe.lp
y el iche o con la desc ipci´on de la cuad ´ıcula en el a chi o con nomb e
nu ikabe1.lp, ca gamos los a chi os como:
clingo nu ikabe.lp nu ikabe1.lp -c n=11 -c m=8
y nos de uel e la soluci´on del puzzle:
%celdaNeg a(1,1) celdaNeg a(4,1) celdaNeg a(5,1) celdaNeg a(6,1)
%celdaNeg a(7,1) celdaNeg a(8,1) celdaNeg a(9,1) celdaNeg a(10,1)
%celdaNeg a(11,1) celdaNeg a(1,2) celdaNeg a(2,2) celdaNeg a(3,2)
%celdaNeg a(4,2) celdaNeg a(7,2) celdaNeg a(11,2) celdaNeg a(1,3)
%celdaNeg a(4,3) celdaNeg a(5,3) celdaNeg a(6,3) celdaNeg a(7,3)
%celdaNeg a(8,3) celdaNeg a(9,3) celdaNeg a(11,3) celdaNeg a(1,4)
%celdaNeg a(2,4) celdaNeg a(3,4) celdaNeg a(4,4) celdaNeg a(7,4)
%celdaNeg a(9,4) celdaNeg a(11,4) celdaNeg a(1,5) celdaNeg a(4,5)
%celdaNeg a(5,5) celdaNeg a(6,5) celdaNeg a(9,5) celdaNeg a(11,5)
%celdaNeg a(1,6) celdaNeg a(3,6) celdaNeg a(4,6) celdaNeg a(6,6)
%celdaNeg a(7,6) celdaNeg a(8,6) celdaNeg a(9,6) celdaNeg a(10,6)
%celdaNeg a(11,6) celdaNeg a(1,7) celdaNeg a(3,7) celdaNeg a(6,7)
%celdaNeg a(11,7) celdaNeg a(1,8) celdaNeg a(2,8) celdaNeg a(3,8)
%celdaNeg a(4,8) celdaNeg a(5,8) celdaNeg a(6,8) celdaNeg a(7,8)
%celdaNeg a(8,8) celdaNeg a(9,8) celdaNeg a(10,8) celdaNeg a(11,8)
(a) Nu ikabe ni el medio (b) Soluci´on
Figu a 6.1: puzzle Nu ikabe y su soluci´on
100

Ejemplo 2.
Es udiemos aho a la soluci´on del Nu ikabe de la igu a 6.2.
Figu a 6.2: puzzle Nu ikabe ni el medio
Desc ibamos el puzzle de nue o con el p edicado nume ada/3:
nume ada(2,2,2). nume ada(2,5,2). nume ada(3,7,2). nume ada(4,3,2).
nume ada(5,4,2). nume ada(6,3,2). nume ada(7,7,6). nume ada(8,1,4).
nume ada(9,5,4). nume ada(10,6,2).
Aho a, gua damos el c´odigo de la desc ipci´on en el iche o nu ikabe2.lp.
Ca gando de nue o los a chi o como:
clingo nu ikabe.lp nu ikabe2.lp -c n=10 -c m=7
nos de uel e la soluci´on del Nu ikabe:
%celdaNeg a(1,1) celdaNeg a(2,1) celdaNeg a(3,1) celdaNeg a(4,1)
%celdaNeg a(5,1) celdaNeg a(6,1) celdaNeg a(1,2) celdaNeg a(3,2)
%celdaNeg a(5,2) celdaNeg a(7,2) celdaNeg a(8,2) celdaNeg a(9,2)
%celdaNeg a(10,2) celdaNeg a(1,3) celdaNeg a(3,3) celdaNeg a(5,3)
%celdaNeg a(7,3) celdaNeg a(10,3) celdaNeg a(1,4) celdaNeg a(2,4)
%celdaNeg a(3,4) celdaNeg a(4,4) celdaNeg a(6,4) celdaNeg a(7,4)
%celdaNeg a(8,4) celdaNeg a(10,4) celdaNeg a(1,5) celdaNeg a(4,5)
%celdaNeg a(6,5) celdaNeg a(8,5) celdaNeg a(10,5) celdaNeg a(1,6)
%celdaNeg a(2,6) celdaNeg a(3,6) celdaNeg a(4,6) celdaNeg a(5,6)
101
%celdaNeg a(6,6) celdaNeg a(8,6) celdaNeg a(9,6) celdaNeg a(1,7)
%celdaNeg a(4,7) celdaNeg a(9,7)
6.2. Puzzle Heyawake
El Heyawake es un puzzle que se juega en una cuad ´ıcula ec angula
di idida en celdas. Adem´as, la cuad ´ıcula se di ide a su ez en habi aciones
ec angula es de di e sos ama˜nos. Al comienzo, las celdas de la cuad ´ıcula
son blancas y algunas habi aciones con ienen una celda nume ada. El obje i o
es decidi qu´e celdas deben pe manece blancas y qu´e celdas se pin an de
neg o de acue do a las eglas que se exponen a con inuaci´on. Al igual que el
Nu ikabe, decidi si exis e una soluci´on del puzzle Heyawake es un p oblema
NP-comple o.
Las eglas del puzzle son las siguien es:
1. Dos celdas neg as no pueden se adyacen es ni e ical ni ho izon al-
men e.
2. Todas las celdas blancas deben es a conec adas o ogonalmen e.
3. En las habi aciones en las que se encuen e una celda nume ada, el
n´ume o de la celda indica c´uan as celdas de la habi aci´on deben pin a se
de neg o.
4. Una habi aci´on sin celda nume ada puede con ene cualquie n´ume o
de celdas neg as.
5. Un camino ec o de celdas blancas no puede a a esa m´as de dos
habi aciones.
De nue o, podemos isi a el siguien e enlace pa a ob ene m´as in o ma-
ci´on sob e las eglas del juego y pode juga en l´ınea: enlace.
Veamos en onces c´omo se puede modeliza el puzzle. P ime o, amos a
desc ibi la cuad ´ıcula dada.
Supongamos que la cuad ´ıcula que conside amos iene dimensiones nxm
(n ilas y m columnas) y es ´a di idida en habi aciones.
102
Pa a desc ibi la cuad ´ıcula, a cada habi aci´on se le asigna una e ique a
y se ep esen a a a ´es del p edicado hab/4: supongamos que enemos una
habi aci´on delimi ada po las celdas (X1,Y1), (X1,Y2), (X2,Y1) y (X2,Y2)
a la que se le asigna una e ique a A, en onces, es o se ep esen a como
hab(A,X1,Y1,X2,Y2). La e ique a A que podemos asigna le a cada habi-
aci´on i ´a de 0 a -1, y se ep esen a po el p edicado e ique a/1.
ila(1..n).
col(1..m).
e ique a(0.. -1).
Algunas de las habi aciones con ienen una celda nume ada y o as no. Pa-
a ep esen a lo, usamos el p edicado con iene/2, de mane a que
con iene(A,N) ep esen a que la habi aci´on cuya e ique a es A con iene una
celda nume ada con el n´ume o N. Pa a ep esen a que la habi aci´on A no
iene celda nume ada, se usa con iene(A,-1).
Es udiemos en onces el p og ama que nos da ´a la soluci´on del Heyawake.
Vamos a gene a las dis in as cuad ´ıculas candida as a se soluci´on a en-
diendo a las eglas 3 y 4, con emplando odas las mane as de pin a celdas de
neg o en cada habi aci´on de la cuad ´ıcula (la celda nume ada ambi´en puede
pin a se de neg o es a ez).
Pa a ello, de inimos p ime o el “ ama˜no de la habi aci´on”: una habi aci´on
con una celda nume ada con el n´ume o N end ´a ama˜no N, y una habi a-
ci´on sin celda nume ada end ´a ama˜no -1. El ama˜no de la habi aci´on nos
indica cu´an as celdas de la habi aci´on pueden pin a se de neg o. Usamos el
p edicado dimHab/4 pa a ep esen a el ama˜no de la habi aci´on:
dimHab(N,X1,Y1,X2,Y2) :- hab(A,X1,Y1,X2,Y2), con iene(A,N).
REGLAS 3 Y 4.
Veamos c´omo ep esen a las eglas 3 y 4. Pa a ello, usamos el
p edicado celdaNeg a/2 donde celdaNeg a(X,Y) indica, como an es, que
la celda (X,Y), donde X es la ila e Y la columna, se ha pin ado de ne-
g o. Usamos ambi´en el p edicado den ohab/3, donde den ohab(X,Y,A)
ep esen a que la celda (X,Y) es ´a den o de la habi aci´on A:
den ohab(X,Y,A) :- hab(A,X1,Y1,X2,Y2), X1<=X, X<=X2, Y1<=Y,
Y<=Y2, ila(X), col(Y).
103
Gene emos odas las posibles mane as de pin a celdas de neg o en una
habi aci´on que con iene una celda nume ada a endiendo a la egla 3. Usamos
una egla de elecci´on:
N{celdaNeg a(X,Y):den ohab(X,Y,A)}N :- hab(A,X1,Y1,X2,Y2),
dimHab(N,X1,Y1,X2,Y2),
N>0.
Aho a, gene amos odas las posibles o mas de pin a celdas de neg o en
una habi aci´on que no iene ninguna celda nume ada de acue do a la egla
4.
{celdaNeg a(X,Y):den ohab(X,Y,A)}:- hab(A,X1,Y1,X2,Y2),
dimHab(-1,X1,Y1,X2,Y2).
Las celdas es an es que no hayamos pin ado de neg o pe manece ´an blan-
cas:
celdaBlanca(X,Y) :- no celdaNeg a(X,Y), ila(X), col(Y).
Implemen emos las eglas que quedan pa a desca a las cuad ´ıculas que
no las e i ican.
REGLA 1.
Tenemos que modeliza la egla 1: “dos celdas neg as no pueden se ad-
yacen es ni e ical ni ho izon almen e”.
Como ya hicimos, usamos el p edicado ady/4 pa a ep esen a que dos
celdas son adyacen es. Dada una celda (X,Y), sus adyacen es son las celdas
(X+1,Y), (X-1,Y),(X,Y+1), (X,Y-1). Po an o, de inimos el p edicado con
la egla:
ady(X1,Y1,X2,Y2) :- ila(X1), ila(X2), col(Y1), col(Y2),
|X1-X2| + |Y1-Y2| == 1.
Rep esen amos que dos celdas neg as no pueden se adyacen es ni e ical
ni ho izon almen e a a ´es de la es icci´on:
104
yblanco/2, donde neg o(X,Y) nos indica que la celda que se encuen a
en la ila X y en la columna Y con iene un c´ı culo neg o y, an´alogamen e,
blanco(X,Y) nos indica que la celda (X,Y) con iene un c´ı culo blanco.
Veamos aho a como gene a la l´ınea soluci´on del puzzle. Pa a ep esen-
a las ilas y las columnas de la cuad ´ıcula, se usa como an e io men e los
p edicados col/1 y ila/1:
col(1..m).
ila(1..n).
Aho a, amos a conside a odos los segmen os posibles que podemos
ene a a esando las celdas del able o. Las di ecciones que pueden lle a
es os segmen os son la ho izon al y la e ical, y lo ep esen amos con el
p edicado di ec/1, donde di ec(h) ep esen a que el segmen o lle a di ecci´on
ho izon al y di ec( ), que lle a di ecci´on e ical.
di ec(h).
di ec( ).
Pa a ep esen a los segmen os, amos a conside a el p edicado seg/3,
donde seg(h,X,Y) se e i ica si se pin a un segmen o ho izon al que a a iesa
las celdas (X,Y) y (X,Y+1), y seg( ,X,Y) se e i ica si se pin a un segmen o
e ical que a a iesa las celdas (X,Y) y (X+1,Y).
Gene amos as´ı los posibles segmen os que pod ´ıamos dibuja en las celdas
de la cuad ´ıcula usando una egla de elecci´on:
{seg(S,X,Y)}:- di ec(S), ila(X), col(Y).
Como seg(S,X,Y) se e i ica si se a a iesa (X,Y) y alguna de las celdas
(X+1,Y) o (X,Y+1), seg´un si el segmen o es e ical u ho izon al espec i-
amen e, en las celdas de la ´ul ima columna no se pod ´an ealiza segmen os
ho izon ales que pa an de ellas, pues no exis i ´an las celdas de la o ma
(X,m+1), y del mismo modo, ampoco se pod ´an ealiza segmen os e ica-
les que pa an de las celdas de la ´ul ima ila, pues no exis i ´an celdas de la
o ma (n+1,Y). Rep esen amos es o a a ´es de las siguien es dos eglas:
:- seg(h,X,m), ila(X).
:- seg( ,n,Y), col(Y).
Es o nos da los posibles conjun os candida os a se soluci´on del puzzle
Masyu. Aho a, debemos implemen a las eglas, que elimina ´an los conjun os
de segmen os que no esuel an el puzzle.
111

P ime o, ep esen emos que la l´ınea soluci´on del puzzle debe pasa po
odos los c´ı culos de la cuad ´ıcula, ya sean blancos o neg os. Pa a ep esen a
es o, amos a usa dos p edicados:
1. Usamos el p edicado ci culo/2 donde ci culo(X,Y) se e i ica si la
celda (X,Y) con iene un c´ı culo blanco o neg o:
ci culo(X,Y) :- blanco(X,Y), ila(X), col(Y).
ci culo(X,Y) :- neg o(X,Y), ila(X), col(Y).
2. Usamos el p edicado pasaPo /2 donde pasaPo (X,Y) ep esen a que
alguno de los segmen os que componen la soluci´on pasa po (X,Y).
pasaPo (X,Y) :- seg(S,X,Y), ila(X), col(Y), di ec(S).
pasaPo (X,Y+1) :- seg(h,X,Y), Y<m, ila(X), col(Y).
pasaPo (X+1,Y) :- seg( ,X,Y), X<n, ila(X), col(Y).
Finalmen e, se ep esen a que la l´ınea soluci´on debe pasa po odas las
celdas que con ienen c´ı culos median e una es icci´on:
:- ci culo(X,Y), no pasaPo (X,Y).
Implemen emos aho a las eglas.
REGLA 1.
Debemos ep esen a que la l´ınea soluci´on o ma un ´unico camino ce ado
que en a y sale de cada celda que a a iesa una ´unica ez.
Pa a ep esen a que en a y sale de cada celda que a a iesa una ´uni-
ca ez, amos a impone que la celda sea a a esada ´unicamen e po dos
segmen os, ya sea alg´un segmen o que pa e de la misma celda en di ecci´on
e ical u ho izon al u o o segmen o que pa a de la celda (X-1,Y) en di ec-
ci´on e ical o de (X,Y-1) en di ecci´on ho izon al. Po an o, el ca dinal del
conjun o o mado po es os cua o segmen os es exac amen e 2.
:- 3 {seg(h,X,Y); seg( ,X,Y); seg( ,X-1,Y); seg(h,X,Y-1)},
pasaPo (X,Y).
:- {seg(h,X,Y); seg( ,X,Y); seg( ,X-1,Y); seg(h,X,Y-1)}1,
pasaPo (X,Y).
112
Se debe pin a una ´unica l´ınea que sea la soluci´on del puzzle. Es o quie e
deci que si la l´ınea soluci´on pasa po dos celdas, podemos llega de una a
o a eco i´endola.
Pa a ep esen a es o, debemos de ini an es el p edicado ady/4, que e-
p esen a cu´ando dos celdas an a se adyacen es: una celda a a se adyacen e
a (X,Y) si podemos llega a la celda a a ´es de un segmen o que pa e de
(X,Y) y que o ma pa e de la l´ınea soluci´on. As´ı, se de ine ady/4 a a ´es
de las eglas:
ady(X,Y,X+1,Y) :- seg( ,X,Y), X<n.
ady(X,Y,X,Y+1) :- seg(h,X,Y), Y<m.
Si (X,Y) es adyacen e a una celda (W,Z), la celda (W,Z) se ´a adyacen e
a (X,Y). Pa a ep esen a la sime ´ıa de la elaci´on, usamos:
ady(X,Y,W,Z) :- ady(W,Z,X,Y).
Rep esen a emos que si la l´ınea soluci´on a a iesa dos celdas, se puede
llega de una a o a eco iendo la l´ınea usando el p edicado alcanzable/4,
que se de ine como sigue:
1. Supond emos que oda celda que a a iesa la l´ınea soluci´on es alcanza-
ble desde ella misma.
alcanzable(X,Y,X,Y) :- pasaPo (X,Y), ila(X), col(Y).
2. Supond emos que la celda (W,Z) es alcanzable desde la celda (X,Y) si
exis e una celda (X1,Y1) de mane a que (X,Y) y (X1,Y1) son adyacen-
es y (W,Z) es alcanzable desde (X1,Y1).
alcanzable(X,Y,W,Z) :- ady(X1,Y1,X,Y), alcanzable(X1,Y1,W,Z),
ila(X), col(Y), ila(X1), col(Y1),
ila(W), col(Z).
Finalmen e, pa a ep esen a que dada dos celdas po las que la l´ınea
soluci´on pasa, siemp e debemos llega de una a o a eco i´endola, usamos
una es icci´on:
:- pasaPo (X,Y), pasaPo (W,Z), no alcanzable(X,Y,W,Z).
113
REGLA 2.
El camino debe a a esa las celdas con c´ı culos blancos en l´ınea ec a,
es deci , supongamos que (X,Y) es una celda que con iene un c´ı culo blanco,
en onces si de (X,Y) pa e un segmen o ho izon al, a (X,Y) lo debe a a esa
o o segmen o ho izon al, que debe pa i de (X,Y-1), y si de (X,Y) pa e
un segmen o e ical, a (X,Y) lo debe a a esa un segmen o e ical, es a
ez pa iendo de (X-1,Y). Pa a ep esen a es o, se usa una es icci´on, que
impedi ´a que se d´e cualquie o a posibilidad que no sean las que acabamos
de expone :
:- 1 {seg(h,X,Y); seg(h,X,Y-1)}, 1 {seg( ,X,Y); seg( ,X-1,Y)},
blanco(X,Y).
Adem´as, la l´ınea soluci´on debe gi a 90 g ados en la celda an e io o
pos e io en el camino a la celda que con iene el c´ı culo blanco. Es deci , si la
celda (X,Y) con iene un c´ı culo blanco, de ella pa e un segmen o ho izon al
y adem´as es a a esada po o o segmen o ho izon al que pa e de (X,Y-1),
no puede ocu i que (X,Y-1) sea a a esada po un segmen o ho izon al a
la ez que de (X,Y+1) pa a un segmen o ho izon al.
:- blanco(X,Y), seg(h,X,Y), seg(h,X,Y-1), seg(h,X,Y-2),
seg(h,X,Y+1).
De la misma mane a, si la celda (X,Y) que con iene el c´ı culo blanco uese
a a esada po un segmen o e ical que pa e de (X-1,Y) y adem´as, de ella
pa iese un segmen o e ical, no pod ´ıa pa i a la ez un segmen o e ical
de (X-2,Y) y de (X+1,Y). Usamos pa a ep esen a lo la es icci´on:
:- blanco(X,Y), seg( ,X,Y), seg( ,X-1,Y), seg( ,X+1,Y),
seg( ,X-2,Y).
REGLA 3.
Po ´ul imo, amos a modeliza la egla 3. P ime o, ep esen emos que el
camino debe ealiza gi os de 90 g ados en las celdas que con engan c´ı culos
neg os. Pa a ello, supongamos que (X,Y) es una celda que con iene un c´ı culo
neg o. En onces, si de (X,Y) pa e un segmen o e ical, no puede ocu i que
de (X-1,Y) pa a o o segmen o e ical, po que si no la celda queda eco ida
en l´ınea ec a. De igual modo, si de (X,Y) pa e un segmen o ho izon al, no
puede ocu i que de (X,Y-1) pa a un segmen o ho izon al, po el mismo
114
mo i o. Usando es icciones, lo ep esen amos a a ´es de las eglas:
:- neg o(X,Y), seg( ,X,Y), seg( ,X-1,Y), ila(X), col(Y).
:- neg o(X,Y), seg(h,X,Y), seg(h,X,Y-1), ila(X), col(Y).
Pa a ep esen a que las celdas an e io y pos e io en el camino a la celda
que con iene el c´ı culo neg o (que es amos suponiendo que es (X,Y)) deben
se a a esadas en l´ınea ec a, se usan cua o es icciones:
1. Si de la celda (X,Y) pa e un segmen o ho izon al, en onces la celda
siguien e en el camino a (X,Y) es (X,Y+1) y pa a que sea po an-
o a a esada el l´ınea ec a, de ella no debe pa i ni accede nig´un
segmen o e ical:
:- neg o(X,Y), seg(h,X,Y), 1 {seg( ,X,Y+1); seg( ,X-1,Y+1)}.
2. Si de la celda (X,Y-1) pa e un segmen o ho izon al que a a iesa a
(X,Y), en onces (X,Y-1) es la celda an e io en el camino a (X,Y) y po
an o, ni de ella ni de (X-1,Y-1) deben pa i segmen os e icales pa a
que la l´ınea soluci´on a a iese (X,Y-1) en l´ınea ec a.
:- neg o(X,Y),seg(h,X,Y-1), 1 {seg( ,X,Y-1); seg( ,X-1,Y-1)}.
3. Si de la celda (X,Y) pa e un segmen o e ical, la celda siguien e a
(X,Y) en el camino es (X+1,Y), luego pa a que es a se eco a en l´ınea
ec a, no puede ocu i que pa a de ella un segmen o ho izon al o pa a
de (X+1,Y-1) un segmen o ho izon al.
:- neg o(X,Y), seg( ,X,Y), 1 {seg(h,X+1,Y); seg(h,X+1,Y-1)}.
4. Si de la celda (X-1,Y) pa e un segmen o e ical, es a es la celda
an e io a la celda (X,Y) en el camino, luego no puede ocu i que sea
a a esada po un segmen o ho izon al ni que de ella pa a un segmen o
ho izon al.
:- neg o(X,Y),seg( ,X-1,Y), 1 {seg(h,X-1,Y-1); seg(h,X-1,Y)}.
La soluci´on del Masyu end ´a dada po los segmen os que inalmen e se
pin en en la cuad ´ıcula y cumplan las eglas, luego nos ijamos ´unicamen e
en los li e ales o mados po el p edicado seg/3 en el conjun o de espues a:
#show seg/3.
Como hemos hecho en los puzzles an e io es, amos a e algunos ejemplos
de puzzle Masyu y sus soluciones.
115
(a) Masyu ni el no mal (b) Soluci´on
Figu a 6.5: puzzle Masyu y su soluci´on
Ejemplo 1.
Es udiemos p ime o la soluci´on del puzzle Masyu de la igu a 6.5.
Desc ibimos la cuad ´ıcula ep esen ando las celdas que poseen un c´ı culo
blanco o neg o con los p edicados neg o/2 yblanco/2:
blanco(1,4). neg o(2,5). blanco(3,1). blanco(3,6). neg o(4,2).
neg o(5,7). blanco(6,2). blanco(7,5). neg o(8,3).
blanco(8,5). neg o(8,7).
Gua dando el c´odigo del puzzle Masyu en el a chi o masyu.lp, la desc ip-
ci´on de la cuad ´ıcula en el a chi o masyuNo mal.lp y ejecu ando CLINGO
de la siguien e mane a:
clingo masyu.lp masyuNo mal.lp -c n=8 -c m=8
ob enemos la soluci´on del puzzle:
%seg(h,1,3) seg(h,1,4) seg(h,1,5) seg(h,1,6) seg(h,1,7) seg(h,2,1) seg(h,2,3)
%seg(h,2,4) seg(h,2,6) seg(h,4,2) seg(h,4,3) seg(h,4,5) seg(h,5,1) seg(h,5,4)
%seg(h,5,5) seg(h,5,6) seg(h,6,3) seg(h,6,4) seg(h,6,5) seg(h,6,7) seg(h,7,1)
%seg(h,7,4) seg(h,7,5) seg(h,8,1) seg(h,8,2) seg(h,8,4) seg(h,8,5) seg(h,8,6)
%seg( ,1,3) seg( ,1,8) seg( ,2,1) seg( ,2,2) seg( ,2,5) seg( ,2,6) seg( ,2,7)
%seg( ,2,8) seg( ,3,1) seg( ,3,2) seg( ,3,5) seg( ,3,6) seg( ,3,7) seg( ,3,8)
%seg( ,4,1) seg( ,4,4) seg( ,4,7) seg( ,4,8) seg( ,5,2) seg( ,5,8) seg( ,6,2)
%seg( ,6,3) seg( ,6,6) seg( ,6,7) seg( ,7,1) seg( ,7,3) seg( ,7,4) seg( ,7,7)
116

Ejemplo 2.
Aho a, es udiamos la soluci´on del puzzle de la igu a 6.6.
Figu a 6.6: puzzle Masyu ni el di ´ıcil
Desc ibimos el puzzle a a ´es de las eglas:
blanco(1,9). neg o(2,1). blanco(2,3). blanco(2,6). blanco(2,7).
blanco(3,8). blanco(4,2). blanco(4,3). blanco(4,4). neg o(4,6).
blanco(5,6). blanco(5,7). neg o(6,1). blanco(7,3). blanco(7,5).
blanco(7,7). blanco(7,10). blanco(8,2). blanco(8,6). neg o(9,5).
blanco(9,6). neg o(9,9). blanco(10,2).
Gua dando es a desc ipci´on en masyuDi icil.lp y ejecu ando CLINGO:
clingo masyu.lp masyuDi icil.lp -c n=10 -c m=10
se ob iene la soluci´on siguien e del puzzle:
%seg(h,1,4) seg(h,1,5) seg(h,1,7) seg(h,1,8) seg(h,1,9) seg(h,2,1) seg(h,2,2)
%seg(h,2,3) seg(h,3,2) seg(h,3,4) seg(h,3,7) seg(h,3,8) seg(h,4,6) seg(h,4,7)
%seg(h,4,8) seg(h,5,1) seg(h,5,3) seg(h,5,5) seg(h,5,6) seg(h,5,7) seg(h,5,9)
%seg(h,6,1) seg(h,6,2) seg(h,6,3) seg(h,6,5) seg(h,6,6) seg(h,6,7) seg(h,6,9)
%seg(h,7,2) seg(h,7,3) seg(h,7,6) seg(h,7,7) seg(h,7,8) seg(h,9,2) seg(h,9,3)
%seg(h,9,4) seg(h,9,7) seg(h,9,8) seg(h,10,1) seg(h,10,2) seg(h,10,3)
%seg(h,10,4) seg(h,10,5) seg(h,10,7) seg(h,10,8) seg(h,10,9) seg( ,1,4)
%seg( ,1,6) seg( ,1,7) seg( ,1,10) seg( ,2,1) seg( ,2,6) seg( ,2,7) seg( ,2,10)
117
%seg( ,3,1) seg( ,3,2) seg( ,3,3) seg( ,3,4) seg( ,3,5) seg( ,3,6) seg( ,3,9)
%seg( ,3,10) seg( ,4,1) seg( ,4,2) seg( ,4,3) seg( ,4,4) seg( ,4,5) seg( ,4,10)
%seg( ,5,8) seg( ,5,9) seg( ,6,1) seg( ,6,4) seg( ,6,5) seg( ,6,10) seg( ,7,1)
%seg( ,7,2) seg( ,7,5) seg( ,7,6) seg( ,7,9) seg( ,7,10) seg( ,8,1) seg( ,8,2)
%seg( ,8,5) seg( ,8,6) seg( ,8,9) seg( ,8,10) seg( ,9,1) seg( ,9,6) seg( ,9,7)
%seg( ,9,10)
118
Bibliog a ´ıa
[CKK+07] Me e Cayli, Ayse G¨ul Ka a op, Ahme Em ah Ka lak, Hakan
Kayna , Fe han Tu e, and E. E dem, Sol ing challenging g id
puzzles wi h answe se p og amming, 2007.
[GK14] Michael Gel ond and Yulia Kahl, Knowledge ep esen a ion,
easoning, and he design o in elligen agen s, Camb idge Uni-
e si y P ess, New Yo k, 2014, The answe -se p og amming ap-
p oach.
[GKK+19] Ma in Gebse , Roland Kaminski, Benjamin Kau mann, Ma ius
Lindaue , Max Os owski, Ja ie Rome o, To s en Schaub, S en
Thiele, and Philipp Wanko, Po assco use guide, 2019.
[GL88] Michael Gel ond and Vladimi Li schi z, The s able model seman-
ics o logic p og amming, P oceedings o In e na ional Logic
P og amming Con e ence and Symposium (Robe Kowalski, Bo-
wen, and Kenne h, eds.), MIT P ess, 1988, pp. 1070–1080.
[HD21] Ma ´ıa Jos´e Hidalgo Doblado, L´ogica compu acional y eo ´ıa
de modelos,h ps://www.glc.us.es/~mjoseh/LCyTM2020/
index.php/L%C3%B3gica_compu acional_y_ eo %C3%ADa_de_
modelos_(cu so_2020-21), Cu so 2020-2021.
[Li 08] Vladimi Li schi z, Wha is answe se p og amming?, ol. 3,
2008, pp. 1594–1597.
[Li 19] Vladimi Li schi z, Answe se p og amming, Sp inge In e na io-
nal Publishing, 2019.
119