Il 15-puzzle è stato un benchmark per gli algoritmi di ricerca in IA dagli anni ’60. Ogni generazione di algoritmo è stata inventata per superare il muro contro cui la precedente aveva sbattuto. Questo articolo li percorre in ordine di invenzione, mostrando a cosa serviva ciascuno e cosa ha reso necessario il successivo.
Anni ’60 — Ricerca in ampiezza (BFS)
Il primo algoritmo che tutti provano. Esplora gli stati livello per livello: profondità 1 ha 4 stati, profondità 2 ha 16, profondità 3 ha 64, e così via. Continua a esplorare finché non trovi l’obiettivo.
Per l’8-puzzle, BFS finisce in fretta — la profondità nel caso peggiore è 31, quindi al massimo 4³¹ stati (molti meno in pratica per via delle rivisitazioni). Per il 15-puzzle, la profondità più difficile è 80, quindi 4⁸⁰ stati. Sono più stati degli atomi nell’universo osservabile. BFS non finisce.
Il muro: esplosione esponenziale. Risolvere con ricerca non informata è senza speranza oltre il 3×3.
1968 — Ricerca A*
Hart, Nilsson e Raphael pubblicano A Formal Basis for the Heuristic Determination of Minimum Cost Paths. L’idea: invece di esplorare gli stati in ordine di distanza dalla partenza, esplorarli in ordine di f = g + h, dove h è una stima inferiore della distanza rimanente.
Per il 15-puzzle, h è la distanza di Manhattan — somma delle distanze in riga+colonna di ogni tessera dalla sua destinazione. Manhattan è ammissibile (non sovrastima mai) e consistente (soddisfa una disuguaglianza triangolare). Con queste proprietà, A* trova la soluzione ottimale.
Prestazioni sul 15-puzzle: risolve qualsiasi griglia, ma sulle istanze più difficili esplora milioni di stati e consuma centinaia di megabyte di memoria. Il muro: la memoria.
1985 — IDA*
Depth-first iterative-deepening: An optimal admissible tree search di Richard Korf. L’intuizione: invece della coda di priorità di A* (che mantiene tutti gli stati esplorati), fare DFS a profondità iterativa dove il limite di profondità è il costo f anziché la profondità.
IDA* esplora gli stessi stati di A*, approssimativamente nello stesso ordine, ma senza ricordarli tra le iterazioni. Ogni "passata in profondità" usa O(profondità) di memoria invece di O(stati esplorati).
Prestazioni sul 15-puzzle: risolve qualsiasi griglia in secondi su hardware del 1985, sta in pochi kilobyte di memoria. Il muro: l’euristica è ancora Manhattan. Per accelerare la ricerca serve un’euristica più stretta.
Anni ’90 — Conflitto lineare
Criticizing solutions to relaxed models yields powerful admissible heuristics di Hansson, Mayer e Yung. L’euristica di Manhattan assume che le tessere possano attraversarsi. Non possono.
Il conflitto lineare aggiunge 2 mosse all’euristica per ogni coppia di tessere nella stessa riga, entrambe appartenenti a quella riga, ma in ordine errato — una dovrà essere spostata fuori dalla riga per lasciar passare l’altra. Analogamente per le colonne.
Effetto: tipicamente una riduzione del 5–15% dei nodi espansi sui 15-puzzle difficili. Miglioramento netto rispetto a Manhattan puro; nessun vero svantaggio.
1996 — Walking distance
Un’euristica che cattura più a fondo la struttura del puzzle. Per ogni disposizione di tessere proiettata solo sulle righe (ignorando le posizioni all’interno della riga), precalcola il numero minimo di operazioni di scambio di riga per portare ogni tessera nella riga corretta. Lo stesso per le colonne.
La walking distance è ammissibile e considerevolmente più stretta di Manhattan + conflitto lineare — tipicamente 1,5–2× il valore di Manhattan, il che significa che IDA* espande molti meno nodi.
Costo di implementazione: una piccola tabella precalcolata (~500 KB per un 4×4). Punto di equilibrio per il 15-puzzle.
2002 — Database di pattern additivi e disgiunti
Disjoint pattern database heuristics di Korf e Felner. L’euristica più forte conosciuta per i puzzle scorrevoli.
L’idea: partizionare le tessere in gruppi disgiunti (per il 15-puzzle è standard una partizione 7+8). Per ogni gruppo, precalcola il costo ottimale di spostare solo le tessere di quel gruppo nelle loro posizioni finali, ignorando tutte le altre tessere. Tabula ogni possibile disposizione del gruppo.
Al momento della ricerca, consulta il contributo di ogni gruppo e somma. Poiché i gruppi sono disgiunti e le mosse necessarie per ciascuno non confliggono (con un argomento attento), la somma è ammissibile.
Costo di memoria: circa 1 GB per il 15-puzzle. Prestazioni: risolve il 15-puzzle più difficile in poche migliaia di espansioni di nodo — millisecondi.
2005+ — database di pattern più grandi per puzzle più grandi
La stessa tecnica si estende al 24-puzzle (5×5) e oltre. Una partizione 5+5+5+9 per il 24-puzzle occupa circa 4 GB. Con essa, qualsiasi 24-puzzle casuale si risolve in secondi.
Il 35-puzzle (6×6) è al limite di ciò che è trattabile. Le istanze 6×6 più difficili sono ancora oggetto di ricerca aperta nel 2026.
Anni 2010+ — euristiche con reti neurali
Le reti neurali sono state addestrate a predire una quantità simile alla distanza di Manhattan per i puzzle scorrevoli, producendo a volte euristiche più strette di quelle ingegnerizzate a mano. Il problema: le euristiche NN di solito non sono dimostrabilmente ammissibili, quindi i solver costruiti su di esse forniscono risposte probabilmente ottimali anziché garantite ottimali.
Per gli articoli di ricerca, è interessante. Per il software in produzione dove conta l’ottimalità (calibrazione della difficoltà nei giochi), i classici database di pattern restano lo strumento giusto.
Perché questa storia conta
Ogni ondata di ricerca sugli algoritmi per puzzle scorrevoli è stata guidata dalla stessa pressione: il puzzle è abbastanza piccolo da poter essere benchmarkato, abbastanza grande perché gli algoritmi cattivi vadano in timeout. Il 15-puzzle è stato il banco di prova per i progressi generali nella ricerca euristica — A*, IDA*, database di pattern — che oggi alimentano la pianificazione di percorsi, la dimostrazione di teoremi e molti altri ambiti.
Quando risolvi un 15-puzzle in un’app premendo il pulsante suggerimento, stai usando algoritmi sviluppati esattamente per questo gioco e poi generalizzati ovunque.
Una tabella riassuntiva
| Anno | Algoritmo | Tempo per risolvere un 15-puzzle difficile | Memoria | Cosa lo ha reso possibile |
|---|---|---|---|---|
| Anni ’60 | BFS | Non finisce | Enorme | — |
| 1968 | A* + Manhattan | Minuti | Centinaia di MB | Ricerca euristica |
| 1985 | IDA* + Manhattan | Secondi | KB | Iterative deepening |
| 1996 | IDA* + walking distance | < 1 sec | + 500 KB precalcolati | Euristica migliore |
| 2002 | IDA* + DB di pattern 7+8 | Millisecondi | + 1 GB precalcolati | Enumerazione di sottoinsiemi |
Ogni riga è un vero salto qualitativo, non un miglioramento marginale. La storia della risoluzione del 15-puzzle è anche la storia della moderna ricerca euristica.