Contenido
PalancaProgramación lógica de restricciones
Esta página presenta ejercicios corregidos detallados del problema de programación lógica por restricciones, que es una mezcla natural de programación lógica y programación de restricciones.
Ejercicio 1
Considere el siguiente rompecabezas:
Cada región de la cuadrícula debe llenarse con un número entre 0 y 9 para que
- los números en dos regiones adyacentes (vertical u horizontalmente) son diferentes
- siempre que haya cuatro regiones que se encuentren en un punto (indicado por un pequeño círculo), la suma de sus números es igual a 20.
Resuelva este problema mediante la programación lógica de restricciones.
Vamos a nombrar de arriba a la izquierda a abajo a la derecha (por línea) los cuadrados vacíos por una letra. Cada dominio tiene un valor entre 0 y 9. A partir de entonces, las dos restricciones deben completarse manualmente.
Para cada cuadrado, su puntuación debe ser diferente a la de sus vecinos.
Para cada círculo, la suma debe ser igual a 20.
Por lo tanto, tenemos la siguiente programación lógica de restricciones:
L = [A,B,C,D,E,F,G,H,I,J,K,M],
L::[0..9],
En #\= 7, En #\= 8, En #\= 6,
B #\= 8, B #\= 4,
C #\= 7, C #\= 6, C #\= 9,
D #\= 6, D #\= 8,
E #\= 6, E #\= 8, E #\= 4, E #\= 5,
F #\= 9, F #\= 6, F #\= G, F #\= Y,
GRAMO #\= 6, GRAMO #\= 5, GRAMO #\= K,
H #\= 5, H #\= 4, H #\= M,
Yo #\= 9, Yo #\= J, J #\= K,
K #\= 5, K #\= M,
7+6+A+C #= 20, A+6+8+D #= 20, 6+8+D+E #= 20, 4+8+B+E #= 20,
9+6+C+F #= 20, 5+6+E+G #= 20, 4+5+E+H #= 20,
9+F+I+J #= 20, F+G+J+K #= 20, 5+H+K+M #= 20,
etiquetado (L).
Ejercicio 2
Considere el juego Bokkusu. El objetivo del juego es marcar ciertos cuadrados de la cuadrícula dada en negro.
Cada cuadro tiene dos valores: un valor A y un valor B. Los números a la derecha indican los valores A de los cuadros en cada fila correspondiente y los números en la parte inferior indican los valores B de los cuadros en cada fila correspondiente. columna (Estos valores siempre van desde 1 hasta el tamaño de la cuadrícula aumentando en 1 de izquierda a derecha o de arriba a abajo).
Los valores de la izquierda indican la suma de los valores B de los recuadros negros de cada fila y los valores de la parte superior indican la suma de los valores A de los recuadros negros de cada columna. En la figura se muestra un ejemplo de una cuadrícula y su solución. En la solución de este ejemplo tenemos por ejemplo 7 = 1 + 2 + 4 (las casillas con valor B de 1, 2 y 4 están marcadas en negro) y 6 = 2 + 4 (las casillas con valores A de 2 y 4 están marcados).
Resuelva este problema mediante la programación lógica de restricciones.
Nombraremos cada cuadrado en la cuadrícula en forma de matriz. Para las restricciones, la suma de las variables binarias (blanco=0 o negro=1) multiplicada por los coeficientes de la izquierda o de la parte superior debe ser igual al valor opuesto.
L = [X11,X12,X13,X14,
X21,X22,X23,X24,
X31,X32,X33,X34,
X41,X42,X43,X44],
fd_dominio(L,0,1),
X11 + 2*X12 + 3*X13 + 4*X14 #= 3,
X21 + 2*X22 + 3*X23 + 4*X24 #= 7,
X31 + 2*X32 + 3*X33 + 4*X34 #= 1,
X41 + 2*X42 + 3*X43 + 4*X44 #= 2,
X11 + 2*X21 + 3*X31 + 4*X41 #= 5,
X12 + 2*X22 + 3*X32 + 4*X42 #= 6,
X13 + 2*X23 + 3*X33 + 4*X43 #= 1,
X14 + 2*X24 + 3*X34 + 4*X44 #=2
Ejercicio 3
Consideramos el problema de generar un horario. Hay 7 clases y 4 espacios. Un espacio puede acomodar un máximo de 2 lecciones. Existen las siguientes restricciones:
– El curso 4 debe ser anterior al curso 6.
– El curso 5 debe ser anterior al curso 7.
– El curso 6 debe ser anterior al curso 2.
– El curso 1 no puede estar en paralelo con los cursos 2, 3, 4 y 7.
– El curso 2 no puede estar en paralelo con los cursos 3 y 6.
– El curso 3 no puede estar en paralelo con los cursos 4, 5 y 6.
– El curso 4 no puede estar en paralelo con los cursos 5 y 6.
– El curso 5 no puede estar en paralelo con el curso 7.
Resuelva este problema mediante la programación lógica de restricciones.
Consideraremos que los cursos son dominios, y que pueden tomar un valor de 1 a 4 correspondiente al nicho que se elija. La programación lógica de restricciones es la siguiente:
L = [C1, C2, C3, C4, C5, C6, C7],
fd_dominio(L,1,4),
C4 #< C6, C5 #< C7, C6 #< C2,
C1 #\= C2, C1 #\= C3, C1 #\= C4, C1 #\= C7,
C2 #\= C3, C2 #\= C6,
C3 #\= C4, C3 #\= C5, C3 #\= C6,
C4 #\= C5, C4 #\= C6,
C5 #\= C7,
fd_cardinalidad(1,[C1#=1,C2#=1,C3#=1,C4#=1,C5#=1,C6#=1,C7#=1],2),
fd_cardinalidad(1,[C1#=2,C2#=2,C3#=2,C4#=2,C5#=2,C6#=2,C7#=2],2),
fd_cardinalidad(1,[C1#=3,C2#=3,C3#=3,C4#=3,C5#=3,C6#=3,C7#=3],2),
fd_cardinalidad(1,[C1#=4,C2#=4,C3#=4,C4#=4,C5#=4,C6#=4,C7#=4],2),
fd_etiquetado(L)
Ejercicio 4
Inshi no heya es un juego de lógica japonés. Se juega en una cuadrícula rectangular de celdas que están separadas en rectángulos. Una dimensión de cada rectángulo es 1 mientras que la otra dimensión varía.
Cada rectángulo se coloca horizontal o verticalmente y contiene un número. La meta es
llene todas las celdas con números del 1 al 9 para que:
– Si multiplicamos todos los dígitos de cada rectángulo obtenemos el número indicado en el rectángulo
– Ningún número aparece más de una vez en una columna.
– Ningún número aparece más de una vez en una línea.
A continuación se muestra un ejemplo de una cuadrícula original y una solución:
Resuelva este problema mediante la programación lógica de restricciones.
Cada casilla de la matriz se considera como un dominio, cada casilla puede tomar un valor de 1 a 5. Las restricciones son simples ya que la suma de las casillas de un determinado perímetro debe ser igual a un número dado.
L = [X11,X21,X31,X41,X51,
X12,X22,X32,X42,X52,
X13,X23,X33,X43,X53,
X14,X24,X34,X44,X54,
X15,X25,X35,X45,X55],
fd_dominio(L,1,9),
fd_todos_diferentes([X11,X12,X13,X14,X15]),
fd_todos_diferentes([X21,X22,X23,X24,X25]),
fd_todos_diferentes([X31,X32,X33,X34,X35]),
fd_todos_diferentes([X41,X42,X43,X44,X45]),
fd_todos_diferentes([X51,X52,X53,X54,X55]),
fd_todos_diferentes([X11,X21,X31,X41,X51]),
fd_todos_diferentes([X12,X22,X32,X42,X52]),
fd_todos_diferentes([X13,X23,X33,X43,X53]),
fd_todos_diferentes([X14,X24,X34,X44,X54]),
fd_todos_diferentes([X15,X25,X35,X45,X55]),
X11 #= 5, X31*X41 #= 2, X32*X42 #= 4, X33 #= 4,
X43*X53 #= 15, X34*X44 #= 15, X15*X25*X35*X45 #= 120,
X21*X22 #= 15, X51*X52 #= 12, X12*X13*X14 #= 8,
X23*X24 #= 2, X54*X55 #= 2,
fd_etiquetado(L)
Ejercicio 5
Los rascacielos se construyen en una cuadrícula NxN. Cada rascacielos tiene un número de plantas correspondiente a su tamaño (del 1 al N). En cada columna y cada fila cada tamaño aparece exactamente una vez. Los números en los bordes de la cuadrícula indican cuántos rascacielos se pueden ver cuando se mira desde ese punto hacia la fila o columna correspondiente. Un rascacielos es visible si todos los rascacielos que tiene delante son más pequeños. Aquí hay un ejemplo de una grilla y su solución:
Por ejemplo, en la segunda línea desde abajo mirando desde la izquierda podemos ver 2 rascacielos: el de altura 3 y el de altura 4. Aquí hay un segundo problema de una cuadrícula (5×5) para resolver:
Resuelva este problema mediante la programación lógica de restricciones.
Puede usar el predicado predefinido fd_cardinality(+List, ?Count)
donde List es una lista de restricciones y Count es el número de restricciones de List satisfechas.
restricción ([A1, A2, A3, A4, A5], C): -
fd_cardinalidad([A5 #>A4 #/\A5 #>A3 #/\A5 #>A2 #/\A5 #>A1,
A4 #>A3 #/\A4 #>A2 #/\A4 #>A1,
A3 #> A2 #/\A3 #> A1, A2 #> A1],C).
rascacielos (L): -
L = [Línea1,Línea2,Línea3,Línea4,Línea5],
Línea1 = [X11,X12,X13,X14,X15],
Línea2 = [X21,X22,X23,X24,X25],
Línea3 = [X31,X32,X33,X34,X35],
Línea4 = [X41,X42,X43,X44,X45],
Línea5 = [X51,X52,X53,X54,X55],
fd_dominio(Línea1,1,5),fd_dominio(Línea2,1,5),
fd_dominio(Línea3,1,5),fd_dominio(Línea4,1,5),
fd_domain(Línea5,1,5),
fd_todos_diferentes(Línea1), fd_todos_diferentes(Línea2),
fd_todos_diferentes(Línea3), fd_todos_diferentes(Línea4),
fd_todos_diferentes(Línea5),
fd_todos_diferentes([X11,X21,X31,X41,X51]),
fd_todos_diferentes([X12,X22,X32,X42,X52]),
fd_todos_diferentes([X13,X23,X33,X43,X53]),
fd_todos_diferentes([X14,X24,X34,X44,X54]),
fd_todos_diferentes([X15,X25,X35,X45,X55]),
% Todavía se ve el primer rascacielos. Así que tienes que quitar 1
% de cada número de rascacielos visibles.
restricción (Línea1,0), restricción (Línea2,3), restricción (Línea3,2),
restricción (Línea4,1),
restricción ([X12, X22, X32, X42, X52], 2),
restricción([X13,X23,X33,X43,X53],2),
restricción([X15,X14,X13,X12,X11],2),
restricción([X25,X24,X23,X22,X21],1),
restricción([X35,X34,X33,X32,X31],2),
restricción([X55,X54,X53,X52,X51],0),
restricción([X52,X42,X32,X22,X12],1),
restricción([X53,X43,X33,X23,X13],1),
restricción([X54,X44,X34,X24,X14],1),
restricción([X55,X45,X35,X25,X15],0),
fd_labeling(Línea1),fd_labeling(Línea2),fd_labeling(Línea3),
fd_labeling(Línea4),fd_labeling(Línea5).