La programació lògica amb restriccions (CLP, per les seves sigles en anglès) és una extensió de la programació lògica que permet treballar amb restriccions en lloc de simples fets i regles. Aquesta tècnica és especialment útil per a problemes d'optimització, planificació i altres problemes que impliquen restriccions complexes.

Una restricció és una condició que ha de ser satisfeta per a que una solució sigui vàlida. En el context de CLP, les restriccions es poden expressar com a relacions entre variables.

El domini d'una variable és el conjunt de valors que aquesta variable pot prendre. En CLP, els dominis poden ser finits o infinits.

Un solucionador de restriccions és un algorisme que troba valors per a les variables que satisfan totes les restriccions imposades.

El problema de les N-reines consisteix a col·locar N reines en un tauler de N x N de manera que cap reina pugui atacar una altra. Això significa que no hi pot haver dues reines en la mateixa fila, columna o diagonal.

1. Importació del Mòdul CLP(FD): :- use_module(library(clpfd)). importa el mòdul de restriccions sobre dominis finits.
2. Definició del Problema: n_reines/2 defineix el problema de les N-reines.
   • length(Reines, N): Crea una llista de longitud N.
   • Reines ins 1..N: Defineix el domini de les variables.
   • totes_diferents(Reines): Assegura que totes les reines estan en diferents columnes.
   • no_ataca(Reines): Assegura que les reines no es poden atacar entre elles.
   • labeling([], Reines): Troba una solució que satisfaci totes les restriccions.
3. Restriccions de Diferència: totes_diferents/1 assegura que totes les reines estan en diferents columnes.
4. Restriccions de No Atac: no_ataca/1 assegura que les reines no es poden atacar en les diagonals.

El problema de la mochila consisteix a seleccionar un subconjunt d'objectes amb pesos i valors donats per maximitzar el valor total sense excedir un pes màxim.

1. Importació del Mòdul CLP(FD): :- use_module(library(clpfd)). importa el mòdul de restriccions sobre dominis finits.
2. Definició del Problema: mochila/5 defineix el problema de la mochila.
   • length(Pesos, N): Obté el nombre d'objectes.
   • length(Seleccio, N): Crea una llista de selecció de longitud N.
   • Seleccio ins 0..1: Defineix el domini de les variables de selecció (0 o 1).
   • scalar_product(Pesos, Seleccio, #=<, Capacitat): Assegura que el pes total no excedeixi la capacitat.
   • scalar_product(Valors, Seleccio, #=, ValorTotal): Calcula el valor total dels objectes seleccionats.
   • labeling([maximize(ValorTotal)], Seleccio): Troba una solució que maximitzi el valor total.

Implementa un solucionador de Sudoku utilitzant CLP.

Solució

Implementa un solucionador per al problema de la coloració de grafs utilitzant CLP.

Solució

En aquesta secció, hem après sobre la programació lògica amb restriccions (CLP) i com utilitzar-la per resoldre problemes complexos. Hem vist exemples pràctics com el problema de les N-reines i el problema de la mochila, i hem proporcionat exercicis per practicar. La CLP és una eina poderosa que amplia les capacitats de la programació lògica tradicional, permetent treballar amb restriccions i dominis de variables de manera eficient.