Solución:
Este sitio está dedicado a resolver este tipo de acertijos con CLP (FD). Pero todo el poder de CLP (FD) es exagerado aquí: su tarea puede resolverse de manera efectiva buscando en todo el espacio de la solución cuando haya descrito adecuadamente las restricciones.
La solución estará compuesta por 5 casas, donde cada atributo satisfará todas las restricciones impuestas por la descripción.
Tenga en cuenta que debe utilizar el mismo símbolo para cada atributo (es decir, verde y invernadero está mal, elija uno de ellos).
También next_to parece incorrecto: si numera del 1 al 5, esto se puede calcular o enumerar, pero se refiere al vecino inmediato.
Así que complete la representación de datos del ‘espacio de búsqueda de soluciones’, algo como
Problem = [
house(1, Nationality1, Color1, Pet1, Drinks1, Smokes1),
house(2, Nationality2, Color2, Pet2, Drinks2, Smokes2),
...
],
% place constraints
member(house(_, englishman, red, _, _, _), Problem),
member(house(_, spaniard, _, dog, _, _), Problem),
...
member / 2 es el Prolog incorporado más simple, pero en este caso es suficiente para resolver el problema: cuando se han publicado todas las restricciones, las variables se unirán a los valores apropiados. La clave es la capacidad del miembro para no determinista seleccione un miembro (duh) de la solución.
Entonces, cuando necesite expresar una restricción entre 2 elementos diferentes, invoque 2 veces el miembro y coloque las restricciones entre las variables apropiadas: es decir
el hombre que fuma Chesterelds vive en la casa al lado del hombre con el zorro
será traducido a
....,
member(house(N, _, _, _, _, chesterelds), Problem),
member(house(M, _, _, fox, _, _), Problem),
next_to(N, M),
...
Al expresar muchas restricciones de esta manera, tenga cuidado con la identidad de los símbolos: podría ser útil codificar cada predicado en un procedimiento separado, para evitar el alias indebido. Pero la contraparte también es cierta: si el mismo símbolo está involucrado en más de una restricción, será necesario pasar el símbolo para acotar la búsqueda.
Le dejaré pensar en la representación correcta de los predicados ‘geométricos’: next_to y right_of podrían enumerarse o expresarse mediante aritmética.
Este rompecabezas (también conocido como Zebra Puzzle) se ha discutido muchas veces en Stackoverflow antes, ver por ejemplo:
- ¿Resolver “¿Quién es el propietario de Zebra” mediante programación?
- ¿Por qué no puedo obtener la respuesta al acertijo de cebra en el prólogo?
- Resolviendo acertijos de lógica en Prolog
- El acertijo de Einstein
Una traducción de Prolog puede ser sencilla, regla por regla, siguiendo aún el paradigma de instanciar el dominio seleccionándolo. Aquí está el dominio de los atributos de la casa; en la respuesta vinculada, los atributos de las casas son fijados por un programador humano y el dominio son las casas habitadas reales, lo que permite una codificación muy sucinta.
En otras palabras, la diferencia está en el notación: una notación sofisticada ya nos lleva a la mitad del camino, pero fue un humano quien la inventó y la siguió (como el programador tener que escribir norwegian en el primero la especificación de la casa directamente, en el argumento apropiado posición) – no una computadora.
Aquí tratamos de inyectar tan poco humano conocimiento en el código como sea posible, siguiendo las limitaciones de la tarea. (aunque cualquier cosa es discutible, por supuesto, y lo último en evitar la interferencia humana sería un programa de computadora que toma el texto en inglés como su entrada … que nuevamente estaría abierto a críticas sobre cuán específicamente diseñado está ese programa para encontrar soluciones a este problema. rompecabezas específico, o tipo de rompecabezas, etc., etc.)
Lo codificamos en el De arriba hacia abajo estilo. Al parecer, falta la pregunta. Debería ser “¿Quién bebe agua? ¿Quién es el dueño de la cebra?”:
zebra( Z, W ,HS) :-
length( HS, 5), % nation? color? what's that? define it later...
member( H1, HS), nation( H1, eng ), color( H1, red ),
member( H2, HS), nation( H2, spa ), owns( H2, dog ),
member( H3, HS), drink( H3, coffee ), color( H3, green ),
member( H4, HS), nation( H4, ukr ), drink( H4, tea ),
right_of(B, A, HS), color( A , ivory ), color( B , green ),
member( H5, HS), smoke( H5, oldgold), owns( H5, snails ),
member( H6, HS), smoke( H6, kools ), color( H6, yellow ),
middle( C, HS), drink( C , milk ),
first( D, HS), nation( D , nor ),
next_to( E, F, HS), smoke( E , chester), owns( F , fox ),
next_to( G, H, HS), smoke( G , kools ), owns( H , horse ),
member( H7, HS), smoke( H7, lucky ), drink( H7, orange ),
member( H8, HS), nation( H8, jpn ), smoke( H8, parlamt),
next_to( I, J, HS), nation( I , nor ), color( J , blue ),
member( W, HS), drink( W , water ),
member( Z, HS), owns( Z , zebra ).
right_of( B, A, HS) :- append( _, [A, B | _], HS).
next_to( A, B, HS) :- right_of( B, A, HS) ; right_of( A, B, HS).
middle( A, [_,_,A,_,_]).
first( A, [A | _]).
nation(H, V) :- attr( H, nation-V).
owns( H, V) :- attr( H, owns-V). % select an attribute
smoke( H, V) :- attr( H, smoke-V). % from an extensible record H
color( H, V) :- attr( H, color-V). % of house attributes
drink( H, V) :- attr( H, drink-V). % which *is* a house
attr(House, Attr-Value) :-
memberchk( Attr-X, House), % unique attribute names
X = Value.
Probar, realizar una búsqueda exhaustiva con un bucle impulsado por fallas,
3 ?- time((zebra(Z,W,_), maplist(nation,[Z,W],R), writeln(R), false ; true)).
[jpn,nor]
% 180,974 inferences, 0.016 CPU in 0.020 seconds (78% CPU, 11600823 Lips)
true.
Así es como se terminan definiendo las casas:
5 ?- zebra(_, _, HS), maplist( writeln, HS),
false.
[smoke-kools, color-yellow, nation-nor, owns-fox, drink-water |_G859]
[nation-ukr, drink-tea, smoke-chester, owns-horse, color-blue |_G853]
[nation-eng, color-red, smoke-oldgold, owns-snails, drink-milk |_G775]
[nation-spa, owns-dog, color-ivory, smoke-lucky, drink-orange|_G826]
[drink-coffee, color-green, nation-jpn, smoke-parlamt, owns-zebra |_G865]
false.
o, con las listas de atributos “congeladas” fijando su longitud y luego ordenadas,
7 ?- zebra( _, _, HS), maplist( length, HS, _), !, maplist( sort, HS, S),
maplist( writeln, S), false.
[color-yellow, drink-water, nation-nor, owns-fox, smoke-kools ]
[color-blue, drink-tea, nation-ukr, owns-horse, smoke-chester]
[color-red, drink-milk, nation-eng, owns-snails, smoke-oldgold]
[color-ivory, drink-orange, nation-spa, owns-dog, smoke-lucky ]
[color-green, drink-coffee, nation-jpn, owns-zebra, smoke-parlamt]
false.
También es fácil hacer attr/2 predicado aceptar liza de Name-Value pares, lo que permite un estilo de codificación de aspecto más alto y que fluye naturalmente con una especie de “registros extensibles” – incluso se podría decir “objetos” – especificaciones, como
zebra( Z, W ,HS):-
length( HS, 5),
member( H1, HS), attr( H1, [nation-eng, color-red ] ),
member( H2, HS), attr( H2, [nation-spa, owns-dog ] ),
member( H3, HS), attr( H3, [drink-coffee, color-green] ),
......
etc.