El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Programación Lógica con Restricciones

Siguiente ►
►

La Programación Lógica con Restricciones (CLP, por sus siglas en inglés) es una extensión de la programación lógica que permite trabajar con restricciones en lugar de simples hechos y reglas. En Prolog, esto se logra mediante el uso de bibliotecas específicas que permiten definir y resolver restricciones sobre variables.

Conceptos Clave

  1. Restricciones: Condiciones que deben ser satisfechas por las variables.
  2. Dominios: Conjunto de valores posibles que una variable puede tomar.
  3. Solvers: Algoritmos que encuentran soluciones que satisfacen las restricciones.

Instalación de la Biblioteca CLP

Para utilizar CLP en Prolog, es necesario instalar la biblioteca correspondiente. En SWI-Prolog, se puede hacer de la siguiente manera:

?- pack_install(clpfd).

Uso Básico de CLP

Definiendo Restricciones

Las restricciones se definen utilizando predicados específicos de la biblioteca CLP. A continuación, se muestra un ejemplo básico:

:- use_module(library(clpfd)).

ejemplo_basico(X, Y) :-
    X #> 0,
    Y #> 0,
    X + Y #= 10.

En este ejemplo:

  • X #> 0 y Y #> 0 son restricciones que indican que X y Y deben ser mayores que 0.
  • X + Y #= 10 es una restricción que indica que la suma de X y Y debe ser igual a 10.

Consultas con Restricciones

Para realizar consultas con restricciones, se utiliza el predicado label/1 que asigna valores a las variables de acuerdo con las restricciones definidas:

?- ejemplo_basico(X, Y), label([X, Y]).
X = 1,
Y = 9 ;
X = 2,
Y = 8 ;
...

Ejemplo Práctico: Problema de las N-Reinas

El problema de las N-reinas consiste en colocar N reinas en un tablero de ajedrez de NxN de manera que ninguna reina pueda atacar a otra. A continuación, se muestra cómo resolver este problema utilizando CLP en Prolog:

:- use_module(library(clpfd)).

n_reinas(N, Reinas) :-
    length(Reinas, N),
    Reinas ins 1..N,
    todas_diferentes(Reinas),
    no_atacan(Reinas),
    label(Reinas).

todas_diferentes([]).
todas_diferentes([Cabeza|Cola]) :-
    all_different(Cola),
    todas_diferentes(Cola).

no_atacan([]).
no_atacan([Cabeza|Cola]) :-
    no_atacan(Cabeza, Cola, 1),
    no_atacan(Cola).

no_atacan(_, [], _).
no_atacan(Y, [Y1|Y1s], Distancia) :-
    Y #\= Y1,
    abs(Y - Y1) #\= Distancia,
    Distancia1 #= Distancia + 1,
    no_atacan(Y, Y1s, Distancia1).

En este ejemplo:

  • Reinas ins 1..N define que cada reina debe estar en una fila diferente.
  • todas_diferentes(Reinas) asegura que las reinas no están en la misma columna.
  • no_atacan(Reinas) asegura que las reinas no se atacan en las diagonales.

Ejercicio Práctico

Ejercicio: Implementa un predicado sudoku/1 que resuelva un tablero de Sudoku utilizando CLP.

Solución:

:- use_module(library(clpfd)).

sudoku(Filas) :-
    length(Filas, 9),
    maplist(same_length(Filas), Filas),
    append(Filas, Elementos),
    Elementos ins 1..9,
    maplist(all_distinct, Filas),
    transpose(Filas, Columnas),
    maplist(all_distinct, Columnas),
    Filas = [A,B,C,D,E,F,G,H,I],
    bloques(A, B, C),
    bloques(D, E, F),
    bloques(G, H, I),
    maplist(label, Filas).

bloques([], [], []).
bloques([A,B,C|R1], [D,E,F|R2], [G,H,I|R3]) :-
    all_distinct([A,B,C,D,E,F,G,H,I]),
    bloques(R1, R2, R3).

En este ejercicio:

  • Elementos ins 1..9 define que cada celda del Sudoku debe contener un número del 1 al 9.
  • maplist(all_distinct, Filas) asegura que cada fila contiene números distintos.
  • transpose(Filas, Columnas) y maplist(all_distinct, Columnas) aseguran que cada columna contiene números distintos.
  • bloques/3 asegura que cada subcuadro 3x3 contiene números distintos.

Conclusión

La Programación Lógica con Restricciones en Prolog permite resolver problemas complejos de manera declarativa, especificando restricciones en lugar de algoritmos detallados. Este enfoque es poderoso para problemas de optimización y búsqueda, como el problema de las N-reinas y Sudoku. En el siguiente módulo, exploraremos cómo aplicar estos conceptos en aplicaciones prácticas y cómo depurar programas Prolog.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2024. Todos los derechos reservados