Tema 2: Soluciones lógicas de problemas lógicos

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% § Enunciado                                                        %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% En este ejercicio vamos a resolver el siguiente rompecabezas lógico
% propuesto por Lewis Carroll: 
%
% Cinco hombres de distintas nacionalidades viven en las cinco primeras
% casa de una calle. Cada uno tiene una profesión, un animal favorito y
% una bebida favorita (todas distintas de la de los otros). Sabemos que
%     1. El inglés vive en la casa roja.
%     2. El español tiene un perro.
%     3. El propietario de la casa verde bebe café.
%     4. El italiano bebe té.
%     5. La casa verde está a la derecha de la blanca.
%     6. El escultor cría caracoles.
%     7. El diplomático vive en la casa amarilla.
%     8. En la casa central beben leche.
%     9. El Noruego vive en la primera casa de la izquierda.
%    10. El zorro está en la casa vecina de la del médico.
%    11. El caballo está en la casa vecina de la del diplomático.
%    12. El violinista bebe zumo de fruta.
%    13. El japonés es pintor.
%    14. La casa del noruego está al lado de la casa azul.
% Determinar dónde está la cebra y quién bebe agua. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% § Solución                                                         %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% solución_carroll(L)
%    se verifica si L es una solución al rompecabezas; esto es, L debe
%    ser una presolución que verifique todas las condiciones del
%    enunciado. 
solución_carroll(L) :-
   presolución(L),
   % 1. El inglés vive en la casa roja:
   member(casa(roja,inglés,_,_,_),L),
   % 2. El español tiene un perro:
   member(casa(_,español,perro,_,_),L),
   % 3. El propietario de la casa verde bebe café:
   member(casa(verde,_,_,café,_),L),
   % 4. El italiano bebe té:
   member(casa(_,italiano,_,té,_),L),
   % 5. La casa verde está a la derecha de la blanca:
   vecina_derecha(casa(verde,_,_,_,_),casa(blanca,_,_,_,_),L),
   % 6. El escultor cría caracoles:
   member(casa(_,_,caracol,_,escultor),L),
   % 7. El diplomático vive en la casa amarilla:
   member(casa(amarilla,_,_,_,diplomático),L),
   % 8. En la casa central beben leche:
   L = [_,_,casa(_,_,_,leche,_),_,_],
   % 9. El Noruego vive en la primera casa de la izquierda:
   L = [casa(_,noruego,_,_,_)|_],
   % 10. El zorro está en la casa vecina de la del médico:
   vecina(casa(_,_,_,_,médico),casa(_,_,zorro,_,_),L),
   % 11. El caballo está en la casa vecina de la del diplomático:
   vecina(casa(_,_,_,_,diplomático),casa(_,_,caballo,_,_),L),
   % 12. El violinista bebe zumo de fruta:
   member(casa(_,_,_,zumo,músico),L),
   % 13. El japonés es pintor:
   member(casa(_,japonés,_,_,pintor),L),
   % 14. La casa del noruego está al lado de la casa azul:
   vecina(casa(_,noruego,_,_,_),casa(azul,_,_,_,_),L),
   % La cebra está en alguna casa:
   member(casa(_,_,cebra,_,_),L),
   % Alguien bebe agua:
   member(casa(_,_,_,agua,_),L).

% presolución(?L) 
%     se verifica si L es una presolución; es decir, una lista de 5
%     elementos de la forma casa(E1,E2,E3,E4,E5) donde
%     + E1 es el color de la casa,
%     + E2 la nacionalidad del que vive en la casa,
%     + E3 el animal que hay en la casa,
%     + E4 la bebida favorita del que vive en la casa y
%     + E5 la profesión del que vive en la casa.
presolución([casa(_,_,_,_,_),
             casa(_,_,_,_,_),
             casa(_,_,_,_,_),
             casa(_,_,_,_,_),
             casa(_,_,_,_,_)]).

% vecina_derecha(A,B,L)
%    se verifica si A está a la derecha de B en la lista L; es decir, B
%    es el siguiente elemento de A en L. Por ejemplo,
%        ?- vecina_derecha(X,Y,[a,b,c]).
%        X = b     Y = a ;
%        X = c     Y = b ;
%        false.
%        ?- length(L,3), vecina_derecha(a,b,L).
%        L = [b, a, _G384] ;
%        L = [_G378, b, a] ;
%        false.
vecina_derecha(A,B,[B,A|_]).
vecina_derecha(A,B,[_|RL]) :-
   vecina_derecha(A,B,RL).

% vecina(A,B,L)
%    se verifica si A y B son vecinas en L; es decir, son elementos
%    consecutivos en L. Por ejemplo,
%        ?- vecina(X,Y,[a,b,c]).
%        X = a   Y = b ;
%        X = b   Y = a ;
%        X = b   Y = c ;
%        X = c   Y = b ;
%        false.
%        ?- length(L,3), vecina(a,b,L).
%        L = [a, b, _G336] ;
%        L = [b, a, _G336] ;
%        L = [_G330, a, b] ;
%        L = [_G330, b, a] ;
%        false.
vecina(A,B,[A,B|_]).
vecina(A,B,[B,A|_]).
vecina(A,B,[_|RL]) :-
    vecina(A,B,RL).

/* Cálculo de las soluciones del rompecabeza.
 ?- solución_carroll(L).
 L = [casa(amarilla, noruego,  zorro,   agua,  diplomático),
      casa(azul,     italiano, caballo, té,    médico),
      casa(roja,     inglés,   caracol, leche, escultor),
      casa(blanca,   español,  perro,   zumo,  músico),
      casa(verde,    japonés,  cebra,   café,  pintor)] ;
 false.

 Por tanto, la cebra está en la casa verde y bebe agua el diplomático.
*/

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% § Enunciado                                                        %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% En una conversación, Santiago, Cristina y Pablo descubren que tienen
% distintas profesiones y que tocan diferentes intrumentos
% musicales. Sus profesiones son médico, abogado e ingeniero. Los
% instrumentos que tocan son piano, flauta y violín. Además,
%    1. Cristina está casada con el médico.
%    2. El abogado toca el piano.
%    3. Cristina no es ingeniero.
%    4.Santiago es paciente del violinista.
% ¿Quién toca la flauta?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% § Solución                                                         %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

solucion(Flauta) :-
   % Tienen distintas profesiones.
   personas_distintas(Medico,Abogado,Ingeniero),
   % Tocan distintos instrumentos.
   personas_distintas(Piano,Violin,Flauta),
   % Cristina está casada con el médico.
   \+ cristina = Medico,
   % El abogado toca el piano.
   Abogado = Piano,
   % Cristina no es ingeniero.
   \+ Ingeniero = cristina,
   % Santiago es paciente del violinista.
   Violin = Medico,                              
   \+ santiago = Violin.     

% personas_distintas(A,B,C) se verifica si A, B y C son tres personas
% distintas. 
personas_distintas(A,B,C) :-
   persona(A), persona(B), persona(C),  
   \+ A=B, \+ A=C, \+ B=C. 

% persona(X) se verifica si X es una persona.
persona(cristina).
persona(santiago).
persona(pablo).

% Cálculo de la solución:
%    ?- solucion(F).
%    F = santiago ;
%    false.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% § Enunciado                                                        %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Se sabe que
% 1. Una banda está compuesta por tres músicos de distintos paises y que
%    tocan distintos instrumentos. 
% 2. El pianista toca primero.
% 3. Juan toca el saxo y toca antes que el australiano.
% 4. Marcos es francés y toca antes que el violinista.
% 5. Hay un músico japonés.
% 6. Un músico se llama Saúl.
% Determinar el nombre, el país y el instrumento que toca cada uno de
% los músicos de la banda. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% § Solución                                                         %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% solucion(S) :- S es una solución del problema de los músicos.
solucion(S) :-
   componentes_de_la_banda(S),  % 1
   primero(X,S),                % 2
   instrumento(X,piano),
   antes(Y,Z,S),                % 3
   nombre(Y,juan),
   instrumento(Y,saxo),
   pais(Z,australia),
   antes(Y1,Z1,S),              % 4
   nombre(Y1,marco),
   pais(Y1,francia),
   instrumento(Z1,violin),
   pertenece(U,S),              % 5
   pais(U,japon),
   pertenece(V,S),              % 6
   nombre(V,saul).

% componentes_de_la_banda(B) :- B son los componentes de la banda (donde
% cada componente es de la forma musico(N,P,I) con N su nombre, P su
% país e I su instrumento).
componentes_de_la_banda(banda(musico(_,_,_),
                              musico(_,_,_),
                              musico(_,_,_))).

% primero(X,B) :- X es el primer músico de la banda B
primero(X,banda(X,_,_)).

% instrumento(X,I) :- el músico X toca el instrumento I.
instrumento(musico(_,_,I),I).

% antes(X,Y,B) :- X toca antes que Y en la banda B
antes(X,Y,banda(X,Y,_)).
antes(X,Z,banda(X,_,Z)).
antes(Y,Z,banda(_,Y,Z)).

% nombre(X,N) :- el nombre del músico X es N.
nombre(musico(N,_,_),N).

% pais(X,P) :- el país del músico X s P.
pais(musico(_,P,_),P).

% pertenece(X,B) :- X es un músico de la banda B.
pertenece(X,banda(X,_,_)).
pertenece(Y,banda(_,Y,_)).
pertenece(Z,banda(_,_,Z)).

% Cálculo de la solución:
% ?- solucion(S).
% S = banda(musico(marco, francia,   piano),
%           musico(juan,  japon,     saxo),
%           musico(saul,  australia, violin)) ;
% false

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% § Enunciado                                                        %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Se tiene un tablero de 4x4, donde algunas celdas están vacías y otras
% contienen números entre 1 y 4. El problema consiste en llenar todas
% las celdas con números entre 1 y 4 tales que
% * los números en cada una de las 4 filas sean distintos,
% * los números en cada una de las 4 columnas sean distintos y
% * los números en cada uno de las 4 submatrices 2x2 son distintos.
% Por ejemplo, para el sudoku de la izquierda la solución es el de la
% derecha:
%    1 4 _ _                1 4 3 2
%    _ _ 4 _                3 2 4 1
%    2 _ _ _                2 3 1 4
%    _ _ _ 3                4 1 2 3

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% § Solución                                                         %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% sudoku(E,L) se verifica si L es la lista que representa el sudoku E.
sudoku(ej1,[1,4,_,_,
            _,_,4,_,
            2,_,_,_,
            _,_,_,3]).

% solucion_sudoku(S,L) se verifica si L es la solución del sudoku del
% ejemplo S.
solucion_sudoku(S,L) :-
   length(L,16),
   sudoku(S,L),
   es_solucion(L).

% es_solucion(L) se verifica si L es una solución del sudoku.
es_solucion([R11,R12,R13,R14,
             R21,R22,R23,R24,
             R31,R32,R33,R34,
             R41,R42,R43,R44]) :-
   numeros([R11,R12,R13,R14]), numeros([R21,R22,R23,R24]), % filas 1,2 
   numeros([R31,R32,R33,R34]), numeros([R41,R42,R43,R44]), % filas 3,4
   numeros([R11,R21,R31,R41]), numeros([R12,R22,R32,R42]), % columnas 1,2
   numeros([R13,R23,R33,R43]), numeros([R14,R24,R34,R44]), % columnas 3,4
   numeros([R11,R12,R21,R22]), numeros([R13,R14,R23,R24]), % NO y NE
   numeros([R31,R32,R41,R42]), numeros([R33,R34,R43,R44]). % SO y SE

% numeros(L) se verifica si L es una lista de números distintos entre 1
% y 4. Por ejemplo,
%    ?- numeros([A,B,C]).
%    A = 3, B = 2, C = 1 ;
%    A = 4, B = 2, C = 1 ;
%    A = 2, B = 3, C = 1 
numeros([]).
numeros([X|Xs]) :-
   numeros(Xs),
   numero(X),
   \+ member(X,Xs).

% numero(X) se verifica si X es un número entre 1 y 4.
numero(X):-
   member(X,[1,2,3,4]).

% Para no resumir las listas (ya que por defecto sólo escribe los 10
% primeros elementos). Si no se cambia el valor de answer_write_options,
% se puede ver todos los elementos escribiendo w a continuación de la
% respuesta resumida.
:- set_prolog_flag(answer_write_options,
                   [ quoted(true),
                     portray(true),
                     spacing(next_argument)
                   ]).

% Cálculo de la solución:
%   ?- solucion_sudoku(ej1,L).
%   L = [1,4,3,2,3,2,4,1,2,3,1,4,4,1,2,3] ;
%   false.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% § Enunciado                                                        %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% El problema consiste en sustituir cada una de las letras por un dígito
% de forma que a letras distintas les correspondan dígitos distintos y
% se verifique la siguiente suma
%     SEND
%   + MORE
%   ------
%    MONEY

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% § Solución                                                         %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% solucion(S) se verifica si S es una solución del problema
solucion([[S,E,N,D],[M,O,R,E],[M,O,N,E,Y]]) :-
   digito(D), digito(E), 
   Y is (D+E) mod 10, C1 is (D+E) // 10, 
   digito(N), digito(R), 
   E is (N+R+C1) mod 10, C2 is (N+R+C1) // 10,
   digito(E), digito(O), 
   N is (E+O+C2) mod 10, C3 is (E+O+C2) // 10,
   digito(S), S > 0, digito(M), M > 0, 
   O is (S+M+C3) mod 10, M is (S+M+C3) // 10,
   digitos_distintos([S,E,N,D,M,O,R,Y]).

% digito(X) se verifica si X es un dígito.
digito(X) :-
   member(X,[0,1,2,3,4,5,6,7,8,9]).

% digitos_distintos(L) se verifica si L es una lista de dígitos
% distintos. Por ejemplo,
%    ?- digitos_distintos([A,B,C]).
%    A = 2, B = 1, C = 0 ;
%    A = 3, B = 1, C = 0 ;
%    A = 4, B = 1, C = 0 
digitos_distintos([]).
digitos_distintos([X|Xs]) :-
   digitos_distintos(Xs),
   digito(X), 
   \+ member(X,Xs).

% Cálculo de la solución:
%    ?- solucion(S).
%    S = [[9,5,6,7],[1,0,8,5],[1,0,6,5,2]] ;
%    false.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% § Enunciado                                                        %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Colocar los números 1,2,3,4,5,6,7,8,9 en un cuadrado 3x3 de forma que
% todas las líneas (filas, columnas y diagonales) sumen igual.
%
% (Idea: Buscar los valores para las variables A,B,C,D,E,F,G,H,I
%    +---+---+---+
%    | A | B | C |
%    +---+---+---+      
%    | D | E | F |
%    +---+---+---+
%    | G | H | I |
%    +---+---+---+
% tales que
%    {A,B,C,D,E,F,G,H,I} = {1,2,3,4,5,6,7,8,9},
%    A+B+C = 15,
%    D+E+F = 15,
%    G+H+I = 15,
%    A+D+G = 15,
%    B+E+H = 15,
%    C+F+I = 15,
%    A+E+I = 15,
%    C+E+G = 15.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% § Solución 1                                                       %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

solucion_1([A,B,C,D,E,F,G,H,I]) :-
   permutacion([1,2,3,4,5,6,7,8,9],[A,B,C,D,E,F,G,H,I]),
   A+B+C =:= 15,
   D+E+F =:= 15,
   G+H+I =:= 15,
   A+D+G =:= 15,
   B+E+H =:= 15,
   C+F+I =:= 15,
   A+E+I =:= 15,
   C+E+G =:= 15.

% permutacion(L1,L2) se verifica si L2 es una permutación del L1. Por
% ejemplo,
%    ?- permutacion([a,b,c],L).
%    L = [a,b,c] ;
%    L = [b,a,c] ;
%    L = [b,c,a] ;
%    L = [a,c,b] ;
%    L = [c,a,b] ;
%    L = [c,b,a] ;
%    false.
permutacion([],[]).
permutacion([X|L1],L2) :-
   permutacion(L1,L3),
   selecciona(X,L2,L3).

% selecciona(X,L1,L2) se verifica si X es un elemento de L1 y L2 son los
% restantes elementos. Por ejemplo,
%    ?- selecciona(X,[a,b,c],L).
%    X = a,
%    L = [b,c] ;
%    X = b,
%    L = [a,c] ;
%    X = c,
%    L = [a,b] ;
%    false.
selecciona(A,[A|L1],L1).
selecciona(B,[A|L1],[A|L2]) :-
   selecciona(B,L1,L2).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% § Solución 2                                                       %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

solucion_2([A,B,C,D,E,F,G,H,I]) :-
   selecciona(A,[1,2,3,4,5,6,7,8,9],L1),
   selecciona(B,L1,L2),
   selecciona(C,L2,L3),
   A+B+C =:= 15,
   selecciona(D,L3,L4),
   selecciona(G,L4,L5),
   A+D+G =:= 15,
   selecciona(E,L5,L6),
   C+E+G =:= 15,
   selecciona(I,L6,L7),
   A+E+I =:= 15,
   selecciona(F,L7,[H]),
   C+F+I =:= 15,
   D+E+F =:= 15.   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% § Cálculo de las soluciones                                        %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% ?- solucion_1(L).
% L = [6, 1, 8, 7, 5, 3, 2, 9, 4] ;
% L = [8, 1, 6, 3, 5, 7, 4, 9, 2] 
% 
% ?- solucion_2(L).
% L = [2, 7, 6, 9, 5, 1, 4, 3, 8] ;
% L = [2, 9, 4, 7, 5, 3, 6, 1, 8] 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% § Comparación de eficiencia                                        %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% ?- time(solucion_1(_X)).
% % 161,691 inferences, 0.030 CPU in 0.030 seconds (100% CPU, 5308569 Lips)
% _X = [6, 1, 8, 7, 5, 3, 2, 9, 4] 
% ?- time(solucion_2(_X)).
% % 1,096 inferences, 0.000 CPU in 0.000 seconds (100% CPU, 4977135 Lips)
% _X = [2, 7, 6, 9, 5, 1, 4, 3, 8]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% § Enunciado                                                        %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% La sucesión de Lanford es una lista de longitud 27 en la cual 
% aparecen 3 veces cada uno de los dígitos del 1 al 9 y que además cumple
% la propiedad de que entre dos "1" siempre hay un dígito, entre dos "2"
% hay dos dígitos, entre dos "3" hay tres digitos, etc.
%
% Definir el predicado langford(L) que devuelva una sucesión de
% Langford. por ejemplo
%   ?- langford(L).
%   L = [1,9,1,2,1,8,2,4,6,2,7,9,4,5,8,6,3,4,7,5,3,9,6,8,3,5,7] 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% § Solución                                                         %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

langford(L):-
   langford_aux(L),
   sublista([1,_,1,_,1],L),
   sublista([2,_,_,2,_,_,2],L),
   sublista([3,_,_,_,3,_,_,_,3],L),
   sublista([4,_,_,_,_,4,_,_,_,_,4],L),
   sublista([5,_,_,_,_,_,5,_,_,_,_,_,5],L),
   sublista([6,_,_,_,_,_,_,6,_,_,_,_,_,_,6],L),
   sublista([7,_,_,_,_,_,_,_,7,_,_,_,_,_,_,_,7],L),
   sublista([8,_,_,_,_,_,_,_,_,8,_,_,_,_,_,_,_,_,8],L),
   sublista([9,_,_,_,_,_,_,_,_,_,9,_,_,_,_,_,_,_,_,_,9],L).

langford_aux([_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_]).

% sublista(L1,L2) se verifica si L1 es una sublista de L2. 
sublista(L1,L2):-
   append(_,L3,L2),
   append(L1,_,L3).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% § Enunciado                                                        %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Calcular las forma de colorear el siguiente mapa con los colores rojo,
% blanco y azul de forma que las regiones vecinas tengan colores
% distintos. 
%       +----------+----------+       
%       |    A     |     B    |       
%       +----+-----+-----+----+       
%       |    |           |    |       
%       | C  |     D     | E  |       
%       |    |           |    |       
%       +----+-----+-----+----+       
%       |    F     |     G    |       
%       +----------+----------+

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% § Solución                                                         %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

solucion(A,B,C,D,E,F,G) :-
   colores([A,B,C,D,E,F,G]),
   A \= B, A \= C, A \= D,
   B \= D, B \= E,
   C \= D, C \= F,
   D \= E, D \= F, D \= G,
   E \= G,
   F \= G.

% colores(Xs) se verifica si Xs es una lista de colores.
colores([]).
colores([X|Xs]) :-
   color(X),
   colores(Xs).

% color(X) se verifica si X es uno de los tres colores.
color(rojo).
color(blanco).
color(azul).

% Cálculo de soluciones:
%    ?- solucion(A,B,C,D,E,F,G).
%    A = rojo,
%    B = C, C = blanco,
%    D = azul,
%    E = F, F = rojo,
%    G = blanco ;
%    A = rojo,
%    B = C, C = azul,
%    D = blanco,
%    E = F, F = rojo,
%    G = azul ;
%    A = blanco,
%    B = C, C = rojo,
%    D = azul,
%    E = F, F = blanco,
%    G = rojo 
%    ?-

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% § Enunciado                                                        %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Un mapa puede representarse mediante la relación mapa(N,L) donde N es
% el nombre del mapa y L es la lista de los pares formados por cada una
% de las regiones del mapa y la lista de sus regiones vecinas. Por
% ejemplo, os mapas siguientes 
%     +---+   +----------+----------+       +----+-----+-----+----+   
%     | 1 |   |    1     |     2    |       | 1  |  2  |  3  | 4  |   
%     +---+   +----+-----+-----+----+       +----+-----+-----+----+    
%     | 2 |   |    |           |    |       | 5  |           | 6  |    
%     +---+   | 3  |     4     | 5  |       +----+     11    +----+    
%             |    |           |    |       | 7  |           | 8  |    
%             +----+-----+-----+----+       +----+-----+-----+----+     
%             |    6     |     7    |       |    9     |     10    |    
%             +----------+----------+       +----------+----------+
% se pueden representar por
%    mapa(1,[1-[2],2-[1]]). 
%    mapa(2,[1-[2,3,4],2-[1,4,5],3-[1,4,6],4-[1,2,3,5,6,7],
%            5-[2,4,7],6-[3,4,7],7-[4,5,6]]). 
%    mapa(3,[1-[2,5,11],2-[1,3,5,11],3-[2,4,6,11],4-[3,6,11],
%            5-[1,2,7,11],6-[3,4,8,11],7-[5,9,11],8-[6,10,11],
%            9-[7,10,11], 10-[9,8,11],11-[1,2,3,4,5,6,7,8,9,10]]).
% 
% Definir la relación coloración(+M,+LC,-S) que se verifica si S es una
% lista de pares formados por una región del mapa M y uno de los colores
% de la lista de colores LC tal que las regiones vecinas tengan colores
% distintos. Por ejemplo,
%    ?- coloración(ejemplo_1,[1,2,3],S).
%    S = [a-1, b-2, c-2, d-3, e-1, f-1, g-2]
% ¿Qué número de colores se necesitan para colorear el segundo
% mapa?. ¿De cuántas formas distintas puede colorearse con dicho
% número?. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% § Solución                                                         %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

mapa(ej1,[1-[2],2-[1]]). 
mapa(ej2,[1-[2,3,4],2-[1,4,5],3-[1,4,6],4-[1,2,3,5,6,7],
          5-[2,4,7],6-[3,4,7],7-[4,5,6]]). 
mapa(ej3,[1-[2,5,11],2-[1,3,5,11],3-[2,4,6,11],4-[3,6,11],
          5-[1,2,7,11],6-[3,4,8,11],7-[5,9,11],8-[6,10,11],
          9-[7,10,11], 10-[9,8,11],11-[1,2,3,4,5,6,7,8,9,10]]).

% 1ª definición (por generación y prueba):
coloraciones_1(M,LC,L) :-
   findall(S,coloración_1(M,LC,S),L).

coloración_1(M,LC,S) :-
   mapa(M,L),
   coloración_1_aux(L,LC,S).

coloración_1_aux([],_,[]).
coloración_1_aux([R-V|L],LC,[R-C|S]) :-
   member(C,LC),
   coloración_1_aux(L,LC,S),
   not((member(R1,V), member(R1-C,S))).

% 2ª definición (por generación y prueba con acumulador):
coloraciones_2(M,LC,L) :-
   findall(S,coloración_2(M,LC,S),L).

coloración_2(M,LC,S) :-
   mapa(M,L), 
   coloración_2_aux(L,LC,[],S).

coloración_2_aux([],_,S,S).
coloración_2_aux([R-V|L],LC,A,S) :-
   member(C,LC),
   not((member(R1,V), memberchk(R1-C,A))),  
   coloración_2_aux(L,LC,[R-C|A],S).


% Comprobaciones:
%    ?- coloración_2(ej1,[a],L).
%    false.
%    
%    ?- coloración_2(ej1,[a,b],L).
%    L = [2-b, 1-a] ;
%    L = [2-a, 1-b] ;
%    false.
%    
%    ?- coloración_2(ej2,[a,b],L).
%    false.
%    
%    ?- coloraciones_2(ej2,[a,b,c],_L), length(_L,N).
%    N = 6.
%    
%    ?- coloraciones_2(ej3,[a,b,c],_L), length(_L,N).
%    N = 0.
%    
%    ?- coloraciones_2(ej3,[a,b,c,d],_L), length(_L,N).
%    N = 1032.

% Comparación de eficiencia:
% ?- time((coloraciones_1(ej2,[a,b,c,d],L), length(L,N))).
% % 932,733 inferences, 0.074 CPU in 0.074 seconds (100% CPU, 12610608 Lips)
% L = [[1-a, 2-b, 3-b, 4-c, 5-a, 6-a, 7-b], ...
% N = 264.
% 
% ?- time((coloraciones_2(ej2,[a,b,c,d],L), length(L,N))).
% % 13,970 inferences, 0.002 CPU in 0.002 seconds (100% CPU, 5594030 Lips)
% L = [[7-b, 6-a, 5-a, 4-c, 3-b, 2-b, 1-a], ...
% N = 264.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Enunciado                                                          %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Un mono se encuentra en la puerta de una habitación. En el centro de
% la habitación hay un plátano colgado del techo. El mono está
% hambriento y desea coger el plátano, pero no lo alcanza desde el
% suelo. En la ventana de la habitación hay una silla que el mono puede
% usar. El mono puede realizar las siguientes acciones:
% * pasear de un lugar a otro de la habitación,
% * empujar la silla de un lugar a otro de la habitación (si está en el
%   mismo lugar que la silla),
% * subirse en la silla (si está en el mismo lugar que la silla) y
% * coger el plátano (si está encima de la silla en el centro de la
%   habitación).  
%
% Definir el predicado
%    solucion(E,S)
% de forma que S sea una sucesión de acciones que aplicadas al estado S
% permiten al mono coger el plátano. Por ejemplo,
%    ?- solucion(estado(puerta,suelo,ventana,sin),L).
%    L = [pasear(puerta, ventana), empujar(ventana, centro), subir, coger]
% donde 
%    estado(PM,EM,PS,X)
% significa que el mono se encuentra en la posición PM (puerta, centro o
% ventana) encima de EM (suelo o silla), la silla se encuentra en la
% posición PS (puerta, centro o ventana) y el mono tiene (X=con) o no
% (X=sin) el plátano. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% § Solución                                                         %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

solucion(estado(_,_,_,con),[]).
solucion(E1,[A|L]) :-
   movimiento(E1,A,E2),
   solucion(E2,L).

% movimiento(estado(PM1,EM1,PS1,X1),A,estado(PM2,EM2,PS2,X2)) se
% verifica si en el estado(PM1,EM1,PS1,X1) se puede aplicar la acción A
% y se pasa al estado(PM2,EM2,PS2,X2) 
movimiento(estado(centro,silla,centro,sin),
           coger,
           estado(centro,silla,centro,con)).
movimiento(estado(X,suelo,X,U),
           subir,
           estado(X,silla,X,U)).
movimiento(estado(X1,suelo,X1,U),
           empujar(X1,X2),
           estado(X2,suelo,X2,U)).
movimiento(estado(X,suelo,Z,U),
           pasear(X,Z),
           estado(Z,suelo,Z,U)).