Soddisfacimento di vincoli: backtracking, propagazione dei vincoli e AC-3 su un sudoku e una mappa delle regioni ceche

Variabili, domini e vincoli, il grafo dei vincoli, il backtracking, le euristiche MRV e LCV, il forward checking, AC-3 e min-conflicts — colorando le regioni della Cechia, con un sudoku e con otto regine.

15 minuti Matěj Žalmánek 2026-10-15

Serie Basi di IA Parte 23 di 52

1. Mappa dell’intelligenza artificiale: che cos’è ciascuna cosa e come si incastra tutto
2. Breve storia dell’intelligenza artificiale: da Turing ai modelli linguistici
3. Dati, modello, addestramento, inferenza: i concetti di base su un unico esempio
4. Come leggere la notazione matematica: simboli, indici, sommatorie e quantificatori
5. Insiemi e relazioni: i mattoncini con cui si costruiscono le definizioni nell’IA
6. Funzioni e applicazioni: perché ogni modello di IA è una funzione
7. Logica e dimostrazioni: le regole con cui si ragiona nell’IA
8. Grafi e alberi: la struttura su cui poggiano la ricerca e le reti neurali
9. Algebra lineare per l’apprendimento automatico: vettori, matrici e perché l’IA soprattutto moltiplica
10. Derivate, gradiente e regola della catena: come un modello capisce in quale direzione imparare
11. Discesa del gradiente: come impara un modello
12. Che cos’è la probabilità: dal lancio di un dado agli assiomi di Kolmogorov
13. Probabilità condizionata e teorema di Bayes: come cambiare una stima quando scopri qualcosa di nuovo
14. Variabile aleatoria e funzione di ripartizione: una sola funzione che dice tutto sulla distribuzione
15. Funzione di densità e funzione di massa: perché una variabile continua ha probabilità zero in un punto
16. Valore atteso, varianza e covarianza: dove si trova una distribuzione, quanto è larga e che cosa è legato a che cosa
17. Panoramica delle distribuzioni di probabilità: Bernoulli, binomiale, Poisson, uniforme, normale ed esponenziale
18. Legge dei grandi numeri e teorema del limite centrale: perché le medie si comportano in modo così prevedibile
19. Statistica e stima dei parametri: massima verosimiglianza, MAP e intervalli di confidenza
20. Teoria dell’informazione: entropia, entropia incrociata e divergenza KL — da dove vengono le funzioni di perdita
21. Ricerca nello spazio degli stati: BFS, DFS, UCS e A* con animazioni
22. Giochi e avversari: minimax, potatura alfa-beta e Monte Carlo tree search
23. Soddisfacimento di vincoli: backtracking, propagazione dei vincoli e AC-3 su un sudoku e una mappa delle regioni ceche
24. Logica e sistemi basati sulla conoscenza: concatenazione in avanti e all’indietro, risoluzione e sistemi esperti
25. Pianificazione: STRIPS, il mondo dei blocchi, euristiche dal rilassamento e pianificazione negli agenti IA
26. Ricerca locale e ricottura simulata: un commesso viaggiatore tra i capoluoghi di regione cechi
27. Algoritmi genetici: popolazione, incrocio, mutazione e selezione su uno zaino per l’escursione
28. Strategie evolutive e programmazione genetica: dalla regola di un quinto alla legge di Keplero
29. Ottimizzazione con colonie di formiche: come una traccia di feromone trova un percorso breve
30. Ottimizzazione a sciame di particelle: inerzia, esperienza propria ed esperienza dello sciame
31. Neuroevoluzione: evoluzione dei pesi e della forma delle reti neurali e l’algoritmo NEAT
32. Insiemi fuzzy e funzioni di appartenenza: come scrivere «un po’ caldo»
33. Logica fuzzy e probabilità: perché «un po’ caldo» non significa «probabilmente caldo»
34. Logica fuzzy: t-norme, implicazioni e regole SE–ALLORA
35. Controllo fuzzy: Mamdani e Sugeno, dal ventilatore al pendolo inverso su un carrello
36. Clustering fuzzy: l’algoritmo fuzzy c-means e i punti tra i cluster
37. Sistemi neuro-fuzzy (ANFIS): regole fuzzy che imparano dai dati
38. Catene di Markov: matrice di transizione, distribuzione stazionaria e PageRank
39. Modelli di Markov nascosti: l’algoritmo di Viterbi e il casinò disonesto
40. Reti bayesiane: perché l’erba è bagnata e che cosa significa per l’irrigatore
41. Filtro di Kalman: come stimare da misure imprecise dove si trova un’auto e a che velocità va
42. Tipi di apprendimento automatico: supervisionato, non supervisionato, semi-supervisionato e altri
43. Prompt, contesto e RAG: come dare a un modello le informazioni giuste
44. Autoencoder variazionali (VAE): immagini nuove da uno spazio latente continuo
45. Reti generative avversarie (GAN): il falsario contro il detective
46. Modelli di diffusione: come il rumore puro diventa un’immagine
47. Processi decisionali di Markov: stati, azioni, ricompense ed equazioni di Bellman
48. Q-learning e DQN: imparare il valore delle azioni, dalla tabella alla rete neurale
49. Policy gradient e PPO: imparare direttamente la politica
50. Come funziona un agente IA: un modello linguistico in un ciclo con strumenti
51. Programmare con agenti IA: incarico, test e controllo
52. Valutazione e sicurezza dei sistemi di IA: come misurare e come sorvegliare

Programma completo della serie 52 di 83 argomenti pubblicati

Un orario scolastico in cui nessun insegnante ha due classi allo stesso tempo. Il sudoku. La disposizione dei componenti su una scheda, i turni in ospedale, l’assegnazione degli aerei ai gate. Tutti questi problemi hanno in comune il fatto che non cerchiamo un percorso, ma un assegnamento: dare a ogni variabile un valore in modo che valgano tutte le regole contemporaneamente. Un problema del genere si chiama problema di soddisfacimento di vincoli e, a differenza della ricerca generica, ha un grande vantaggio — le regole si vedono, quindi l’algoritmo può ragionarci sopra, non solo provare.

Riprende le parti Ricerca nello spazio degli stati e Grafi e alberi.

1. Che cos’è un problema di soddisfacimento di vincoli

Definizione — CSP

Un problema di soddisfacimento di vincoli (constraint satisfaction problem, CSP) è una terna (X, D, C), dove

• X = {X₁, …, X_n} è l’insieme delle variabili,
• D = {D₁, …, D_n}, dove D_i è il dominio — l’insieme dei valori che X_i può assumere,
• C è l’insieme dei vincoli. Ogni vincolo è una coppia (ambito, relazione): l’ambito è un elenco di variabili, la relazione dice quali combinazioni dei loro valori sono ammesse.

Un vincolo con due variabili nell’ambito è binario, per esempio X₁ ≠ X₂.

Definizione — assegnamento e soluzione

Un assegnamento dà ad alcune variabili un valore del loro dominio. È consistente se non viola alcun vincolo, e completo se ogni variabile ha un valore.

Una soluzione del CSP è un assegnamento completo e consistente.

Perché non trattarlo come una normale ricerca? Si potrebbe — lo stato è l’assegnamento iniziato, l’azione è «dai un valore alla variabile successiva». Solo che la ricerca guarderebbe lo stato come una scatola nera. Il CSP dentro la scatola ci vede: sa quali regole valgono e quali variabili riguardano. Su questo si reggono tutti i trucchi di questa parte.

2. Il grafo dei vincoli: colorare una mappa di regioni

Un problema classico: colorare una mappa in modo che due stati confinanti non abbiano mai lo stesso colore. Prendiamo le quattordici regioni della Cechia. Le variabili sono le regioni, il dominio è un insieme di colori e per ogni confine comune c’è il vincolo «colori diversi».

Definizione — grafo dei vincoli

Il grafo dei vincoli di un CSP binario ha come vertici le variabili e un arco tra X_i e X_j se e solo se le collega un vincolo.

Con quattro colori va liscio. Con tre non va affatto — e il grafo mostra perché. La Boemia Centrale confina con Praga e con sette regioni che intorno a essa formano un anello chiuso. Un anello con un numero dispari di vertici richiede da solo tre colori (due dovrebbero alternarsi regolarmente, e con un numero dispari non torna). La Boemia Centrale confina con tutte e sette, quindi per lei deve restare un quarto colore:

Che quattro colori bastino per ogni mappa è il famoso teorema dei quattro colori. Lo dimostrarono Appel e Haken nel 1976 — come primo grande teorema matematico con l’aiuto di un computer, che verificò quasi duemila casi.

3. Backtracking

Definizione — backtracking

Il backtracking è una ricerca in profondità che a ogni passo assegna un valore a una variabile in più. Un valore che viola un vincolo con le variabili già assegnate non lo prova nemmeno. Quando per una variabile non resta alcun valore, torna alla variabile precedente e prova il suo valore successivo.

Nel caso peggiore esamina O(dⁿ) assegnamenti, dove d è la dimensione del dominio e n il numero di variabili. Il CSP generico è NP-difficile, quindi nel caso peggiore non sappiamo fare di meglio.

def backtracking(assignment, csp):
    if len(assignment) == len(csp.variables):
        return assignment                     # tutto ha un valore: soluzione
    p = select_variable(assignment, csp)
    for h in csp.domains[p]:
        if consistent(p, h, assignment, csp):
            assignment[p] = h
            result = backtracking(assignment, csp)
            if result:
                return result
            del assignment[p]                 # vicolo cieco: torna indietro
    return None

Sulle regioni con quattro colori il backtracking fa 14 assegnamenti, uno per regione, e non torna indietro nemmeno una volta. Con tre colori deve dimostrare che la soluzione non esiste — e questo significa provare tutto: 93 assegnamenti prima di arrendersi.

4. Quale variabile e quale valore

Lo scheletro del backtracking lascia aperte due domande: quale variabile prendere come successiva e in quale ordine provare i suoi valori. Le risposte contano più di quanto sembri.

Definizione — MRV, grado, LCV

MRV (minimum remaining values): scegli la variabile con il minor numero di valori che non sono ancora in conflitto con l’assegnamento.

Euristica del grado: in caso di parità scegli la variabile che ha più vincoli con le variabili non ancora assegnate.

LCV (least constraining value): prova i valori di una variabile a partire da quello che toglie meno possibilità ai vicini.

Con tre colori sulle regioni, MRV insieme al forward checking del prossimo capitolo riduce il numero di assegnamenti da 93 a 45 — parte dalla regione a cui restano meno colori e trova la contraddizione due volte più in fretta.

5. Forward checking

Definizione — forward checking

Dopo l’assegnamento X_i = v esamina ogni variabile non assegnata X_j collegata a X_i da un vincolo e rimuovi da D_j i valori incompatibili con v. Se qualche dominio resta vuoto, annulla subito l’assegnamento.

La differenza si vede sul sudoku qui sotto. Il semplice backtracking sulle caselle per righe ha bisogno di oltre 14 milioni di assegnamenti. Con il forward checking sono 11 400. E se ci aggiungiamo MRV, si scende a 81 — 30 numeri dati e 51 completati, senza un solo ritorno indietro.

6. Arc-consistenza e AC-3

Il forward checking guarda solo un passo più in là: ai vicini della variabile che abbiamo appena assegnato. Si può fare in modo più approfondito — cancellare anche tra variabili che un valore non ce l’hanno ancora.

Definizione — arc-consistenza

La variabile X_i è arc-consistente rispetto a X_j se per ogni valore x ∈ D_i esiste y ∈ D_j tale che la coppia (x, y) soddisfa il vincolo tra di esse. Un CSP è arc-consistente se questo vale per ogni arco orientato (X_i, X_j) del grafo dei vincoli.

Algoritmo — AC-3

1. Inserisci nella coda tutti gli archi orientati (X_i, X_j).
2. Prendi un arco dalla coda e rimuovi da D_i ogni valore che in D_j non ha un partner.
3. Se D_i si è ridotto, rimetti nella coda tutti gli archi (X_k, X_i) per i vicini X_k ≠ X_j — i loro valori potrebbero aver appena perso il partner. Se D_i è vuoto, il CSP non ha soluzione.
4. Ripeti finché la coda non è vuota.

Per c vincoli binari e domini di dimensione al massimo d, AC-3 richiede O(c · d³).

from collections import deque

def ac3(csp):
    queue = deque((xi, xj) for xi in csp.variables for xj in csp.neighbors[xi])
    while queue:
        xi, xj = queue.popleft()
        if revise(csp, xi, xj):
            if not csp.domains[xi]:
                return False                  # dominio vuoto: la soluzione non esiste
            for xk in csp.neighbors[xi]:
                if xk != xj:
                    queue.append((xk, xi))
    return True

def revise(csp, xi, xj):
    before = len(csp.domains[xi])
    csp.domains[xi] = [x for x in csp.domains[xi]
                       if any(csp.allowed(xi, x, xj, y) for y in csp.domains[xj])]
    return len(csp.domains[xi]) < before

7. Sudoku: la propagazione in pratica

Il sudoku è un CSP da manuale: 81 variabili, domini {1, …, 9} e il vincolo «valori diversi» per ogni coppia di caselle nella stessa riga, colonna o quadrato 3 × 3. Ogni casella ha così 20 vicini nel grafo dei vincoli.

Lanciamo su uno schema con 30 numeri il solo AC-3, senza un solo assegnamento alla cieca. Cancella 408 valori — e a ognuna delle 51 caselle vuote ne resta esattamente uno. Il sudoku è risolto con il puro ragionamento:

Con i sudoku facili va così; con quelli più difficili la propagazione da qualche parte si blocca e subentra la ricerca — un backtracking che dopo ogni assegnamento rilancia la propagazione. Questa combinazione (mantenimento dell’arc-consistenza, MAC) è la base della maggior parte dei risolutori reali. Per confronto, sullo stesso schema:

Da quattordici milioni a zero. La forza bruta e il ragionamento intelligente risolvono lo stesso problema — solo uno dei due legge le regole.

8. Ricerca locale: min-conflicts

Una strategia completamente diversa: non costruire la soluzione pezzo per pezzo, ma partire da un assegnamento completo che viola un sacco di vincoli e correggerlo man mano. È la ricerca locale della parte sulla ricerca, solo che la funzione obiettivo è il numero di vincoli violati.

Algoritmo — min-conflicts

1. Parti da un assegnamento completo casuale.
2. Finché qualche vincolo non vale: scegli a caso una variabile in conflitto e dalle il valore con cui viola meno vincoli (in caso di parità a caso).

La prova classica è il problema delle n regine: disporre n regine degli scacchi su una scacchiera n × n in modo che nessuna coppia si minacci. La variabile è la riga della regina in ogni colonna. Per otto regine la nostra esecuzione è partita con sei coppie che si minacciavano ed è finita dopo 8 passi:

Nota i passi centrali: il numero di conflitti resta per quattro passi a uno — l’algoritmo sposta le regine «di lato» lungo un plateau, prima di trovare la mossa che elimina il conflitto. Sorprende quanto bene scali: un milione di regine min-conflicts lo risolve in media in circa cinquanta passi. Con lo stesso procedimento si pianificavano le osservazioni del telescopio spaziale Hubble.

9. I vincoli in pratica

• Orari e pianificazione. Orari scolastici, turni, assegnazione delle aule e piani di produzione si descrivono come variabili, domini e vincoli. Risolutori come Google OR-Tools combinano propagazione, ricerca e miglioramento locale.
• I risolutori SAT risolvono CSP in cui ogni variabile è vero/falso. Verificano progetti di chip, cercano errori nel software e i gestori di pacchetti (per esempio su Linux) li usano per mettere insieme versioni di librerie che funzionano tra loro.
• I compilatori assegnano le variabili del programma ai registri del processore colorando un grafo: due variabili che vivono nello stesso momento non possono condividere un registro — esattamente come le regioni confinanti un colore.
• I configuratori negli e-shop e nella produzione controllano che i componenti scelti stiano bene insieme.
• Gli agenti IA e i modelli linguistici nei CSP spesso non eccellono: per un sudoku o un orario è più affidabile un risolutore. Un buon agente quindi non ragiona sul problema «a mente» — lo traduce in variabili e vincoli e ci chiama sopra uno strumento.

10. Riepilogo

• Un CSP è una terna (X, D, C): variabili, domini e vincoli. Una soluzione è un assegnamento completo che non viola alcun vincolo.
• Il backtracking assegna le variabili una dopo l’altra e torna indietro dai vicoli ciechi; nel caso peggiore è esponenziale.
• Le euristiche MRV e LCV scelgono la variabile più difficile e il valore più accomodante; il forward checking scopre un vicolo cieco un passo prima.
• AC-3 propaga le cancellazioni nel grafo dei vincoli finché ogni valore non ha un partner; un sudoku facile lo risolve del tutto senza ricerca.
• Min-conflicts corregge un assegnamento completo e se la cava anche con problemi enormi, come un milione di regine.

Vuoi toccarlo con mano? Fai scrivere a un agente IA un risolutore di sudoku con il backtracking e poi aggiungici forward checking, MRV e AC-3 — e conta quanti assegnamenti si risparmiano.

La vedi diversamente? Scrivi a support@coden-app.com.