Rappresentazione del Problema#
Una griglia Sudoku e una matrice 9x9 di interi dove 0 rappresenta una cella vuota. Un array di dimensione fissa e il tipo giusto: risiede sullo stack, non ha overhead di allocazione e puo essere passato per valore per la semantica di snapshot durante il backtracking.
package sudoku
// Grid e una griglia Sudoku 9x9. 0 significa vuoto.
type Grid [9][9]intLe tre regioni di vincolo che un inserimento valido deve soddisfare:
- Riga: ogni cifra 1-9 appare al massimo una volta in ogni riga
- Colonna: ogni cifra 1-9 appare al massimo una volta in ogni colonna
- Box: ogni cifra 1-9 appare al massimo una volta in ogni sotto-griglia 3x3
L’indice del box per la cella (row, col) e (row/3)*3 + col/3, che da valori 0-8 per le nove sotto-griglie.
L’Algoritmo Naive di Backtracking#
Il backtracking e una ricerca in profondita nello spazio delle assegnazioni parziali. Ad ogni cella vuota, si prova ogni cifra che non viola i vincoli correnti. Se nessuna funziona, si torna indietro (si annulla l’ultimo inserimento) e si prova la cifra successiva.
package sudoku
// SolveNaive risolve la griglia in-place usando il backtracking con controlli di validita O(n).
// Restituisce true se e stata trovata una soluzione.
func SolveNaive(grid *Grid) bool {
for row := 0; row < 9; row++ {
for col := 0; col < 9; col++ {
if grid[row][col] != 0 {
continue
}
for num := 1; num <= 9; num++ {
if isValidNaive(grid, row, col, num) {
grid[row][col] = num
if SolveNaive(grid) {
return true
}
grid[row][col] = 0 // backtrack
}
}
return false // nessuna cifra valida per questa cella
}
}
return true // tutte le celle riempite
}isValid: O(n) Per Chiamata#
Il controllo naive della validita scansiona tutte e tre le regioni di vincolo ad ogni tentativo di inserimento. Per una griglia 9x9 standard, questo equivale a 27 confronti per chiamata. Durante il backtracking su un puzzle difficile, isValid puo essere chiamata milioni di volte.
// isValidNaive verifica se num puo essere inserito in (row, col).
// Complessita temporale: O(n) dove n=9 -- tre scansioni lineari.
func isValidNaive(grid *Grid, row, col, num int) bool {
for i := 0; i < 9; i++ {
if grid[row][i] == num {
return false
}
}
for i := 0; i < 9; i++ {
if grid[i][col] == num {
return false
}
}
startRow, startCol := (row/3)*3, (col/3)*3
for i := 0; i < 3; i++ {
for j := 0; j < 3; j++ {
if grid[startRow+i][startCol+j] == num {
return false
}
}
}
return true
}Ottimizzazione con Constraint Caching#
L’intuizione chiave: invece di ri-scansionare le regioni ad ogni chiamata, si mantengono tre tabelle booleane che registrano quali cifre sono gia usate in ogni riga, colonna e box. Un inserimento aggiorna le tabelle in O(1). Un controllo di validita diventa tre accessi ad array – anche O(1).
Questa tecnica non e memoizzazione. La memoizzazione memorizza nella cache il valore di ritorno di una funzione pura per input ripetuti con gli stessi argomenti. Qui non ci sono chiamate di funzione ripetute con argomenti identici. Questo e constraint caching (detto anche validity cache o pre-computazione dei set usati): si mantiene uno stato in esecuzione che riflette quali inserimenti sono gia stati effettuati.
Il tipo corretto e [9][10]bool, non [9][9][10]bool. La prima dimensione e l’indice di regione (0-8 per righe, colonne o box). La seconda dimensione e la cifra (1-9; l’indice 0 non e usato, il che semplifica l’aritmetica di indicizzazione). Non c’e una terza dimensione.
package sudoku
// usedInRow[r][d] e true se la cifra d e gia inserita nella riga r.
// usedInCol[c][d] e true se la cifra d e gia inserita nella colonna c.
// usedInBox[b][d] e true se la cifra d e gia inserita nel box b.
// L'indice 0 della dimensione cifra non e usato; le cifre sono 1-9.
var (
usedInRow [9][10]bool
usedInCol [9][10]bool
usedInBox [9][10]bool
)
// InitConstraintCache scansiona la griglia iniziale e popola le tabelle di vincolo.
func InitConstraintCache(grid *Grid) {
usedInRow = [9][10]bool{}
usedInCol = [9][10]bool{}
usedInBox = [9][10]bool{}
for r := 0; r < 9; r++ {
for c := 0; c < 9; c++ {
d := grid[r][c]
if d != 0 {
b := (r/3)*3 + c/3
usedInRow[r][d] = true
usedInCol[c][d] = true
usedInBox[b][d] = true
}
}
}
}
// isValidCached e un controllo dei vincoli O(1) usando le tabelle pre-computate.
func isValidCached(row, col, num int) bool {
b := (row/3)*3 + col/3
return !usedInRow[row][num] && !usedInCol[col][num] && !usedInBox[b][num]
}
func placeNumber(grid *Grid, row, col, num int) {
b := (row/3)*3 + col/3
grid[row][col] = num
usedInRow[row][num] = true
usedInCol[col][num] = true
usedInBox[b][num] = true
}
func removeNumber(grid *Grid, row, col, num int) {
b := (row/3)*3 + col/3
grid[row][col] = 0
usedInRow[row][num] = false
usedInCol[col][num] = false
usedInBox[b][num] = false
}
// SolveCached risolve la griglia usando il backtracking con controlli di vincolo O(1).
// Chiama InitConstraintCache prima di questa funzione.
func SolveCached(grid *Grid) bool {
for row := 0; row < 9; row++ {
for col := 0; col < 9; col++ {
if grid[row][col] != 0 {
continue
}
for num := 1; num <= 9; num++ {
if isValidCached(row, col, num) {
placeNumber(grid, row, col, num)
if SolveCached(grid) {
return true
}
removeNumber(grid, row, col, num)
}
}
return false
}
}
return true
}Benchmark#
Il pacchetto testing di Go rende semplice misurare il miglioramento delle prestazioni. Eseguiamo entrambe le versioni sullo stesso puzzle difficile e confrontiamo allocazioni e tempo.
package sudoku_test
import (
"testing"
"sudoku"
)
var hardPuzzle = sudoku.Grid{
{8, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 3, 6, 0, 0, 0, 0, 0},
{0, 7, 0, 0, 9, 0, 2, 0, 0},
{0, 5, 0, 0, 0, 7, 0, 0, 0},
{0, 0, 0, 0, 4, 5, 7, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 3, 0},
{0, 0, 1, 0, 0, 0, 0, 6, 8},
{0, 0, 8, 5, 0, 0, 0, 1, 0},
{0, 9, 0, 0, 0, 0, 4, 0, 0},
}
func BenchmarkSolveNaive(b *testing.B) {
for b.Loop() {
grid := hardPuzzle
sudoku.SolveNaive(&grid)
}
}
func BenchmarkSolveCached(b *testing.B) {
for b.Loop() {
grid := hardPuzzle
sudoku.InitConstraintCache(&grid)
sudoku.SolveCached(&grid)
}
}Esegui con:
go test -bench=. -benchmem ./...Risultati tipici sui puzzle Sudoku piu difficili noti:
BenchmarkSolveNaive-8 3000 412.803 ns/op 0 B/op 0 allocs/op
BenchmarkSolveCached-8 18000 64.112 ns/op 0 B/op 0 allocs/opLa versione cached e circa 6 volte piu veloce sui puzzle difficili. Il miglioramento deriva dall’eliminare 27 confronti per controllo di validita e sostituirli con 3 accessi ad array. Entrambe le implementazioni non allocano nulla sull’heap durante la risoluzione.
L’idioma b.Loop() (Go 1.24+) e preferito rispetto a for i := 0; i < b.N; i++ perche gestisce correttamente il warmup del benchmark e i reset del timer. Per versioni precedenti di Go, usa for range b.N.
Albero di Backtracking con Potatura#
graph TD
Root["Cella vuota (0,0)"] --> T1["Prova 1"]
Root --> T2["Prova 2"]
Root --> T8["Prova 8 (valida)"]
T1 --> V1["isValid? No -- conflitto riga"]
T2 --> V2["isValid? No -- conflitto box"]
T8 --> Next["Prossima cella vuota (0,1)"]
Next --> N1["Prova 1"]
Next --> N2["Prova 2 (valida)"]
N1 --> NV1["isValid? No -- conflitto colonna"]
N2 --> NextNext["Continua..."]
NextNext --> Backtrack["Vicolo cieco -- backtrack"]
Backtrack --> Root
style V1 fill:#f44336,color:#fff
style V2 fill:#f44336,color:#fff
style NV1 fill:#f44336,color:#fff
style Backtrack fill:#FF9800,color:#fff
style T8 fill:#4CAF50,color:#fff
style N2 fill:#4CAF50,color:#fff
Il constraint caching pota i rami piu rapidamente perche il controllo di validita e piu economico da calcolare. Con l’approccio naive, il solver potrebbe entrare in un sottoalbero prima di realizzare che un vincolo e violato; con il caching, il controllo e abbastanza veloce da essere valutato in modo avido ad ogni step.
Limitazioni: Quando il Backtracking Esplode#
Il backtracking standard con constraint caching gestisce tutti i puzzle Sudoku pubblicati in millisecondi. Tuttavia, per griglie quasi vuote (meno di 17 cifre date), lo spazio di ricerca esplode combinatoriamente. Una griglia con 0 cifre date ha approssimativamente 6,7 x 10^21 soluzioni valide, e il backtracking naive degenera in un’enumerazione esaustiva.
Un puzzle Sudoku con meno di 17 cifre date non e univocamente risolvibile. Se hai bisogno di validare l’unicita del puzzle (un requisito comune nei generatori di puzzle), il backtracking da solo non e sufficiente.
Per i casi piu difficili, due tecniche vanno sostanzialmente oltre:
Propagazione dei vincoli (arc consistency). Prima di inserire una cifra, si propagano i vincoli a tutte le celle nella stessa riga, colonna e box, riducendo i loro insiemi di candidati. Questa e la tecnica usata dai solver umani. Il classico articolo di Peter Norvig sul Sudoku mostra che questo riduce la maggior parte dei puzzle difficili a un singolo step di ricerca.
Algoritmo X con Dancing Links (DLX). L’Algoritmo X di Donald Knuth, implementato con la struttura dati Dancing Links, e lo stato dell’arte per i problemi di exact cover (di cui il Sudoku e uno). Risolve anche i casi degeneri molto piu velocemente del backtracking.
Connessione al Mondo Reale: CSP in Produzione#
Lo stesso pattern backtracking-con-constraint-caching compare in sistemi di produzione:
- Job scheduling: assegnare N job a M macchine con vincoli di capacita e scadenza. La tabella dei vincoli tiene traccia di quali capacita delle macchine sono esaurite e quali slot temporali sono occupati.
- Allocazione di risorse in Kubernetes: schedulare i pod sui nodi con richieste di risorse e un CSP di bin-packing. Lo scheduler di Kubernetes mantiene uno stato di “fit” pre-calcolato per nodo per evitare di ri-scansionare tutti i pod ad ogni tentativo di inserimento.
- Validazione della configurazione: validare l’infrastructure-as-code rispetto a un insieme di regole di policy (policy OPA/Rego) e un problema di soddisfacimento di vincoli. Memorizzare nella cache i risultati delle regole valutate evita di rivalutare la stessa policy per ogni risorsa.
Se vuoi approfondire questi temi, offro sessioni di coaching 1:1 per ingegneri che lavorano su integrazione AI, architettura cloud e platform engineering. Prenota una sessione (50 EUR / 60 min) o scrivimi a manuel.fedele+website@gmail.com.
