Prototipo di un constraint solver – Introduzione

In questi giorni mi sto cimentando nella creazione di un semplice constraint solver in C#. Esistono per la risoluzione di CSP (Constraint Satisfaction Problems) per diversi linguaggi, ma non ne ho trovata nessuna di gratuita per C#. Così mi è presa la voglia di creare una semplice libreria per risolvere semplici CSP, e già che ci sono pubblicare la mia esperienza con relativo codice sorgente. Poiché non è così frequente, o almeno così mi sembra, sentire parlare di Constraint Programming, penso sia ottimale introdurre l’argomento nel primo post della serie.

Il Constraint Programming è un paradigma di programmazione dove le relazioni tra le variabili sono espresse sotto forma di vincoli (constraints) che devono essere soddisfatti. Un Constraint Satisfaction Problem è dato da un insieme di variabili (V1, V2, …, Vn), ciascuna con il suo dominio Di di valori che può assumere, e da un insieme di vincoli tra le variabili (C1, C2, …,Cm) che devono essere rispettati. Una soluzione ad un Constraint Satisfaction Problem è un assegnamento delle variabili che rispetti tutti i vincoli esistenti.

Detta così può sembrare difficile, ma basta un esempio per chiarire tutto. Supponiamo di avere:

• Tre variabili intere: V1, V2 e V3
• Sappiamo che V1 è compresa tra 4 e 6, V2 è compreso tra 4 e 7 e V3 può essere 5 o 6 (questi sono i domini delle variabili)
• Sappiamo inoltre che V1 < V2 < V3 (cioè i vincoli tra le variabili)

Questo è un CSP (Constraint Satisfaction Problem). L’unica soluzione possibile è data da V1 = 4, V2 = 5 e V3 = 6, ma ci possono tranquillamente essere problemi dotati di più di una soluzione (se ad esempio V3 fosse compreso tra 5 e 7 ci sarebbero due soluzioni al problema). Un altro esempio carino di CSP è il Sudoku: ogni casella della griglia (variabile) può assumere un valore compreso tra 1 e 9 (dominio), e ogni riga, ogni colonna e ogni sottoquadrante della griglia ha il vincolo della diversità dei valori delle variabili.

Ma cosa ha di tanto interessante il constraint programming? Semplice: è un paradigma dichiarativo, cioè con una libreria di constraint programming non devo indicare come risolvere il problema, ma semplicemente indico cosa voglio ottenere e la libreria si occupa di trovare la soluzione (in modo efficiente, of course). Nel caso del Sudoku, ad esempio, indicherei solo le regole del gioco e lo stato iniziale della griglia (ed eventualmente qualche politica da adottare per risolvere il problema).

Ma questa è solo l’introduzione, nel prossimo articolo scriverò della basi per costruire una libreria capace di risolvere questi problemi (almeno avendo per dominio dei valori interi).

Se si fosse interessati ad approfondire la teoria:

• Krzysztof Apt – Principles of Constraint Programming [Cambridge University Press]