b"\n_START_ARTICLE_\nProblema di soddisfacimento di vincoli\n_START_PARAGRAPH_\nMolti problemi nell'ambito dell'Intelligenza Artificiale sono classificabili come Problemi di Soddisfacimento di Vincoli (Constraint Satisfaction Problem o CSP); fra questi citiamo problemi di complessit\xc3\xa0 combinatorica, di allocazione di risorse, pianificazione e ragionamento temporale. Questi problemi possono essere risolti efficientemente attraverso tecniche ben note di risoluzione di CSP.\n_START_SECTION_\nDefinizione formale\n_START_PARAGRAPH_\nFormalmente, un CSP pu\xc3\xb2 essere definito su un insieme finito di variabili_NEWLINE__NEWLINE_i cui valori appartengono a domini finiti di definizione  e su un insieme di vincoli (constraints) . Un vincolo su un insieme di variabili \xc3\xa8 una restrizione dei valori che le variabili possono assumere simultaneamente. Concettualmente, un vincolo pu\xc3\xb2 essere visto come un insieme che contiene tutti i valori che le variabili possono assumere contemporaneamente: un vincolo tra k variabili _NEWLINE__NEWLINE_\xc3\xa8 un sottoinsieme del prodotto cartesiano dei domini delle variabili coinvolte  che specifica quali valori delle variabili sono compatibili con le altre. Questo insieme pu\xc3\xb2 essere rappresentato in molti modi, per esempio per mezzo di matrici, equazioni, disuguaglianze o relazioni._NEWLINE_Si definisce grado della variabile il numero di vincoli a cui \xc3\xa8 sottoposta._NEWLINE_Un problema di soddisfacimento di vincoli presuppone un assegnamento iniziale, ovvero un insieme di variabili gi\xc3\xa0 vincolate. L'assegnamento iniziale pu\xc3\xb2 anche essere vuoto. La risoluzione del problema prosegue estendendo l'assegnamento iniziale, ovvero assegnando via via valori alle variabili ancora libere._NEWLINE_La soluzione di un CSP \xc3\xa8 un assegnamento completo e coerente di valori alle variabili (ovvero un assegnamento che soddisfi tutti i vincoli e non lasci variabili libere), ottenuto estendendo l'assegnamento iniziale.\n_START_SECTION_\nProblema delle otto regine\n_START_PARAGRAPH_\nUn classico esempio di problema che pu\xc3\xb2 essere visto come CSP \xc3\xa8 il Rompicapo delle otto regine. Il problema consiste nel disporre su una scacchiera otto regine che non si attacchino a vicenda; naturalmente, non \xc3\xa8 possibile disporne pi\xc3\xb9 di otto, perch\xc3\xa9 questo implicherebbe posizionarne due su una stessa riga. Per formalizzare il problema come CSP dobbiamo identificare un insieme di variabili, un insieme di domini ed un insieme di vincoli. Poich\xc3\xa9 su ogni riga e su ogni colonna della scacchiera dovr\xc3\xa0 essere posta esattamente una regina, una possibile formalizzazione del problema \xc3\xa8 quella di considerare come variabili ciascuna delle otto righe della scacchiera; l'insieme delle variabili sar\xc3\xa0 quindi . Ciascuna di queste variabili pu\xc3\xb2 assumere un valore che rappresenta la colonna su cui si trova la regina corrispondente, per cui i domini delle variabili sono le otto possibili colonne: . Abbiamo quindi gi\xc3\xa0 inserito in questa formalizzazione il concetto che due regine non possono trovarsi sulla stessa riga; resta da imporre che due regine non possono trovarsi n\xc3\xa9 sulla stessa colonna, n\xc3\xa9 sulla stessa diagonale. L'insieme dei vincoli sar\xc3\xa0 dunque:_NEWLINE_ad indicare che due regine non possono trovarsi sulla stessa colonna e:_NEWLINE_, se  e , allora  e _NEWLINE_per imporre che due regine non possono trovarsi sulla stessa diagonale.\n_START_SECTION_\nSudoku\n_START_PARAGRAPH_\nAltro esempio classico \xc3\xa8 la risoluzione di un sudoku. In questo caso le variabili sono le 81 caselle della griglia, il dominio di ogni variabile sono i numeri da 1 a 9 e i vincoli sono la non ripetizione delle cifre in righe, colonne, sottogriglie. In questo caso \xc3\xa8 dato anche un assegnamento iniziale (i numeri gi\xc3\xa0 presenti nella griglia) che rende unica la soluzione allo schema.\n_START_SECTION_\nInferenza\n_START_PARAGRAPH_\nCi\xc3\xb2 che maggiormente differenzia i CSP dai normali problemi di ricerca \xc3\xa8 la possibilit\xc3\xa0 di fare inferenza sfruttando la propagazione dei vincoli: nel caso del sudoku, ad esempio, se a una casella \xc3\xa8 assegnato un certo numero \xc3\xa8 possibile scartare quel numero da tutte le caselle nella stessa riga, colonna e sottogriglia. Questo porta in alcuni casi a poter risolvere interi problemi senza dover ricorrere ad algoritmi di ricerca, come appunto nel caso del sudoku. Nel caso delle otto regine, invece, si predilige una strategia che intervalli ricerca a inferenza: ogni volta che ad una variabile \xc3\xa8 assegnato un valore, si scartano dai domini delle variabili ad essa correlate tutti i valori non pi\xc3\xb9 disponibili, in modo da preservare la coerenza ogni volta che una scelta viene effettuata."